Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
35
votes
1answer
1k views

NP-Completeness of the decision problem for the generalized 15-puzzle

I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block). Now the ...
25
votes
2answers
1k views

Is there an NP-complete language that contains precisely half of the n-bit instances?

Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$ $$|L\cap \{0,1\}^n|=2^{n-1}$$ holds? In other words, $L$ contains precisely half of all $n$-...
23
votes
3answers
911 views

How much would a SAT oracle help speeding up polynomial time algorithms?

Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ ...
20
votes
1answer
687 views

“Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an $A\in$ P, such that $L\Delta A$...
18
votes
1answer
440 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
18
votes
2answers
2k views

Are there any heuristic-free NP complete problems?

Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in ...
17
votes
4answers
2k views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ...
16
votes
1answer
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
14
votes
2answers
353 views

Poly time superset of NP complete language with infinitely many strings excluded from it

For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite? A trivial version which does not stipulate the superset to have infinite ...
14
votes
1answer
426 views

NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is ...
14
votes
2answers
522 views

Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...
13
votes
1answer
245 views

Slowest many-one reduction?

When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. ...
12
votes
1answer
385 views

Which complexity class does this number theory problem belong to?

'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete. Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
12
votes
0answers
433 views

Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?

Question I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. Where $\...
11
votes
0answers
345 views

Error in paper “Some NP-complete geometric problems”?

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems . This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
10
votes
1answer
499 views

Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1]. I am interested in a more fine-grained ...
9
votes
1answer
162 views

Natural candidates for NP-E and E-NP

It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
9
votes
1answer
2k views

Does Memcomputing really solve an NP-complete problem?

I came across an article published in Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states", which makes some pretty astonishing claims. ...
9
votes
0answers
171 views

Complexity question from mathematical music theory

Fix an positive integer $N$. A row means any linear ordering $R=(n_i)_{0\leq i <N}$ of the additive group ${\Bbb Z}/N{\Bbb Z}$. Call $R$ a (generalized) all-interval row if the elements of the ...
8
votes
1answer
253 views

NP-hardness on Cayley graphs

What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
8
votes
1answer
297 views

Can a natural graph problem be universally hard?

Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to any polynomial-time recognizable graph class? To avoid degenerated cases, ...
8
votes
0answers
131 views

Practical interactive proof schemes for NP-hard problems

Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ...
8
votes
0answers
280 views

What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published ...
7
votes
1answer
292 views

Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, ...
7
votes
2answers
382 views

NP-Complete Static Square Puzzles

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...
7
votes
1answer
211 views

What do we know about checking real-stability of multivariate complex polynomials?

Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root ...
7
votes
1answer
272 views

Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

A set is $\mathsf{P}$-immune iff it has no non-trivial $\mathsf{P}$ subset. Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to an $\mathsf{P}$-immune $\mathsf{coNP}$-complete ...
7
votes
0answers
56 views

Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem: Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
7
votes
0answers
189 views

Generalization of SAT, where we replace OR with another symmetric function

Let $\sigma(y_1,\dots,y_k)$ denote some boolean symmetric function on $k$ boolean inputs, $\sigma:\{0,1\}^k\to\{0,1\}$. In $k$-SAT, an instance is a conjunction of clauses, where each clause is the ...
6
votes
1answer
2k views

Magic constant to solve NP-complete problem in polynomial time

Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
6
votes
1answer
576 views

Does the Cook-Levin theorem relativize?

My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes. If you have a proof that the ...
6
votes
2answers
776 views

Isn't it trivial to represent any classical physics problem in a Spin-Glass language which is NP-Complete?

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ...
6
votes
1answer
138 views

What's complexity of this set problem which looks like “Linear Programming”?

I came up with a problem below, which looks like a linear programming problem: Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of : $$ \forall i=1, 2, 3,...,n\space\space \left | S_{i} ...
5
votes
1answer
164 views

Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ ...
5
votes
1answer
163 views

Does p-isomorphism preserve phase transition?

Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other ...
5
votes
2answers
244 views

ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

The PCP theorem can be stated like this : There is a polynomial time reduction from SAT to $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $...
5
votes
1answer
344 views

On Zero sum perfect matching

Fix $c\geq1$. Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order. Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of ...
5
votes
2answers
486 views

Proof for ACYCLIC PARTITION being NP-complete

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers. I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
5
votes
1answer
103 views

$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$. Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, ...
5
votes
1answer
165 views

Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
5
votes
2answers
176 views

Minimising the root-set of a spanning hyperforest of a hypergraph

I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
5
votes
1answer
667 views

Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in ...
5
votes
0answers
50 views

Hardness result or reference for optimal Gaussian elimination process

I'm wondering if the following problem is NP-Complete or has any hardness result. References on related problem are also welcome. Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\...
5
votes
0answers
288 views

On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum. Has this been derandomized?
5
votes
0answers
192 views

When will an NP-complete language remain hard if half of a witness is revealed with the instance?

Let $L$ be an NP-complete language. Let $W(x)$ denote the set of (polynomially length bounded) witnesses that certify $x\in L$. That is, $x\in L$ if and only if there exists a $w$, such that $w\in W(...
5
votes
0answers
160 views

Question about a unary language construction

For any language $L$, let us define another language $Tally(L)$, as follows: $$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$ That is, $Tally(L)$ encodes whether there is ...
4
votes
2answers
235 views

Partition graph into 2 or more claw-free subgraphs

Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
4
votes
1answer
230 views

Is the problem NP-C or polynomially solvable?

I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the ...
4
votes
1answer
172 views

Verifying that a reduction is correct

Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on ...
4
votes
1answer
106 views

NP-Complete Convergent Reductions?

A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the ...