Questions tagged [np]
In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.
135 questions
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
6
votes
2
answers
276
views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
- 3,029
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
0
votes
1
answer
161
views
How to determine if a set is a sumset
Let $G$ be a commutative group (assume whatever you want on $G$ if needed. I am mainly interested in $G = \mathbb{Z}/n\mathbb{Z}$).
Let $k$ be a fixed integer.
Let $(a_1, \dots, a_{k^2})$ be a list of ...
- 527
1
vote
0
answers
32
views
Any updates on "The minimum cost perfect matching problem with conflict pair constraints"?
The subject of the paywalled article The minimum cost perfect matching problem with conflict pair constraints (MCPMPC) are perfect matchings of minimum cost that do not contain certain pairs of edges; ...
- 13.2k
1
vote
0
answers
106
views
Quasi polynomial algorithm for NP complete problem [closed]
I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
- 29
0
votes
0
answers
39
views
Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points
Can anybody help me prove the NP-hardness of the following question:
Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in ...
3
votes
0
answers
255
views
Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?
If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.
But ...
- 31
0
votes
0
answers
16
views
Complexity of finding single source paths with capacity constraints and length constraints
Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
- 21
1
vote
0
answers
51
views
Hardness of an optimization problem when some variables are fixed
Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed.
With the two (related) examples, it is clear that ...
- 11
2
votes
1
answer
273
views
Can we say this nonlinear integer programming problem is NP-hard?
I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...
- 21
2
votes
2
answers
1k
views
Using Kolmogorov complexity to measure difficulty of problems?
We call the natural number $n$ a partition number $\iff$
$$
\exists d | n: \gcd\left(d,\frac{n}{d}\right)=1 \text{ and } \Omega(d) = \Omega\left(\frac{n}{d}\right)\;,
$$
where $\Omega$ counts the ...
- 3,032
2
votes
2
answers
235
views
Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?
Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$
a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$.
Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...
- 21
2
votes
1
answer
534
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...
- 13.9k
1
vote
1
answer
66
views
Path cover with sets of nodes
I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...
0
votes
2
answers
251
views
Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)
Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...
- 143
0
votes
1
answer
117
views
Traveling salesperson problem algorithm [closed]
I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...
5
votes
2
answers
308
views
Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?
It was shown in
P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short
vectors in a lattice
that the construction of a shortest nonzero vector of a Euclidean ...
- 457
0
votes
0
answers
21
views
Complexity of reporting solutions to a decision problems
Suppose we have an oracle that tells us whether an instance of the Hamilton cycle problem contains a Hamilton cycle or not.
Question:
what is the complexity of e.g. finding the edges constituting to a ...
- 13.2k
0
votes
0
answers
65
views
Validity of an argument for an implication of NP-Completeness
Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges
As I see it the setting is a constrained bipartite matching and thus, ...
- 13.2k
1
vote
0
answers
76
views
cut a path from DAG that has minimal conductance
Given a directed acyclic graph $G=(V,E)$, a source node $s$ and a sink node $t$, we want to find a path $P$ from $s$ to $t$ such that if we separate all the nodes in $V$ to two parts $P$ (all the ...
- 143
1
vote
0
answers
55
views
What is an approximation algorithm in the context of NP completeness in general
In theorem 4 of Approximability of Minimum-weight Cycle Covers Bodo Manthey proves that:
Then no approximation algorithm
for $\operatorname{Min-L-DCC}$ achieves an approximation ratio of $o(n)$, ...
- 13.2k
1
vote
1
answer
119
views
Problem NP-completeness on a specific graph class
Consider the class of simple connected n/2-regular graphs, n even. Are the maximum clique problem and/or maximum independent set problem NP-complete on such graphs? Is there any known result which ...
- 105
3
votes
1
answer
1k
views
Root of polynomials in a finite field
I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number.
For example : $p=2^{2020}-69$ ...
- 4,074
22
votes
2
answers
6k
views
$\mathbf{P} = \mathbf{NP}$, what's the problem?
Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$.
We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
- 4,074
4
votes
1
answer
362
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 1,207
1
vote
1
answer
182
views
Boolean function : approximation by a linear function
Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...
- 4,074
10
votes
3
answers
1k
views
Is there a website or a survey collecting all NP-complete problems on graph theory?
I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
- 557
0
votes
0
answers
128
views
What does it mean to find an efficient algorithm for NP complete problems
Suppose I have a problem $P$, an instance $I$ and an algorithm $A$ that efficently solves $P$ for $I$.
Let $P'$ be $P$ with additional constraints that are violated if $A$ is applied to $I$ and ...
- 13.2k
13
votes
3
answers
834
views
Undecidable infinite analogs of NP-complete problems?
In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...
2
votes
1
answer
120
views
$W[1]$-hard and FPT about the equitable tree-coloring problem
I am confused by the two conclusions in this paper (DOI link behind paywall at Springerlink).
It shows that the equitable tree-coloring problem is $W[1]$-hard when parameterized
by treewidth.
However, ...
- 91
0
votes
1
answer
146
views
Is minimum weight vertex cover problem NP-easy? [closed]
I think that Minimum weight vertex cover problem is NP-easy. However I don't know how to prove that. Does anyone know how to prove it?
- 91
7
votes
1
answer
768
views
$\mathit{NP}$-hard statements which are $\mathit{NP}$-complete under the Riemann Hypothesis
$\newcommand\NP{\mathit{NP}}\newcommand\SAT{\mathit{SAT}}\newcommand\CH{\mathit{CH}}\newcommand\PSPACE{\mathit{PSPACE}}$Are there $\NP$-hard problems which are $\NP$-complete under the Riemann ...
- 13.9k
1
vote
0
answers
75
views
Subgraph isomorphism problem with linear map
I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...
- 101
1
vote
0
answers
46
views
Computational complexity of rate $\frac{1}{2}$ codes
We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
- 71
1
vote
0
answers
118
views
Promise version of minimum distance
It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...
- 71
3
votes
1
answer
1k
views
Is there an example of converting a mathematical statement into a three color mapping? [closed]
https://youtu.be/5ovdoxnfFVc?t=1118
At this point, prof Wigderson says it is easy to go from a mathematical statement to a graph coloring problem. The video does not provide an example of this, and a ...
1
vote
0
answers
38
views
Finding valuable conjectures from NP-Complete problems [closed]
Let's suppose we've got an NP-Complete problem, such as the subset sum problem. There are conjectures that, if proven true, would place the subset sum problem to the P-Complete problem realm?
If the ...
-1
votes
3
answers
159
views
Are <sum, product, N> triplets unique and hard to solve? [closed]
This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so ...
- 109
15
votes
2
answers
2k
views
How did the Baker-Gill-Solovay paper come to be?
How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...
user44143
2
votes
2
answers
156
views
Transforming an optimization problem to maxmin formulation
Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...
- 367
2
votes
1
answer
187
views
What is the efficiency of this algorithm which decides the answer to the Boolean satisfiability problem? [closed]
I have just written a short javascript program which, given any boolean expression with $N$ variables, completes in N "ticks" of the clock and which makes the decision. I will explain this algorithm, ...
user49545
4
votes
0
answers
201
views
Is the Weber problem a NP-hard problem?
The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...
- 141
0
votes
1
answer
210
views
Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]
Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
- 1
2
votes
0
answers
56
views
Proof for the NP-hardness of the Max-3-DCC Problem
The Max-3-DCC is the variant of vertex cycle cover problem where each of the vertex disjoint oriented cycles consists of at least 3 arcs and every vertex belongs to exactly one of those cycles; ...
- 13.2k
1
vote
0
answers
43
views
Determining the minimum weight maximal oriented subgraph of a complete directed graph
Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights.
Questions:
What is the ...
- 13.2k
1
vote
0
answers
122
views
Is bounded graph isomorphism $NP$ complete?
Fix a matrix $M\in(\mathbb Z\backslash\{0\})^{n\times n}$ where $\|M\|_\infty\leq 2^{poly(n)}$.
Is the bounded graph isomorphism problem
Given symmetric $A,B\in\{0,1\}^{n\times n}$ and $U,V>0$ ...
- 13.9k
19
votes
5
answers
2k
views
Equivalent forms of the P vs. NP problem
Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral ...
- 2,205
2
votes
0
answers
93
views
NP - hardness of school scheduling problem with a restriction
I do have a real-life scheduling problem for a special education school.
Basically, i have a binary variable containing teachers, subject, time slot and rooms as indices.
The goal is to assign each ...
- 21
16
votes
2
answers
713
views
Is this kind of "Gerrymandering" NP-complete?
[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]
Consider the following simplified form of "Gerrymandering": You have $n^2$ ...
- 263