# Tag Info

## Hot answers tagged np-complete

Accepted

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

I asked this question a few years ago and Boaz Barak positively answered it. The statement is equivalent to the existence of an NP-complete language $L$ where $|L_n|$ is polynomial-time computable. ...
• 1,811
Accepted

### Password hashing using NP complete problems

Unfortunately, this doesn't seem to work (see below for details), and it seems hard to find a way to make this kind of idea yield a provably secure scheme. The problem with your general idea You're ...
• 12.3k
Accepted

### Relationship between two graph optimization problems

One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the ...
• 551
Accepted

### Are there any heuristic-free NP complete problems?

See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. According to that answer, under some natural cryptographic assumptions, for every ...
• 51.1k
Accepted

### Natural candidates for NP-E and E-NP

TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE. A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of ...
• 8,741
Accepted

### Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

L(2,1)-labeling is such a problem. The input is (just) a graph and we want to color it using the minimum number of colors so that neighboring vertices have colors that differ by at least 2 and ...
• 3,722

### Does Memcomputing really solve an NP-complete problem?

I feel this has been answered sufficiently in the comments, so to just sum everything up: The authors do not claim P=NP, which is a statement about deterministic and nondeterministic Turing machines. ...
• 7,768
Accepted

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

No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NP-complete problem. For all known NP-complete ...

• 37.8k

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

Yes, there is a natural NP-complete problem for which uniqueness makes it easy: $k$-edge coloring for $k\ge 4$. Here, to make uniqueness possible, a coloring is defined as a partition of the edges ...
• 51.1k

### Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. ...
• 51.1k

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

Solving Parity games has recently been shown to be in QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf Parity games arise naturally in many formal verification contexts, such as LTL synthesis ...
• 5,616

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

Here's a suggestion of why it might be difficult to come up with an example of such, though I agree with Kaveh's comment that it would be surprising if it didn't exist. [Not an answer, but too long ...
• 37.8k
Accepted

### NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

The following paper shows that the Hamiltonian cycle problem is NP-complete in maximal planar graphs: A. Wigderson The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs ...
• 5,782
Accepted

### NP-Complete Static Square Puzzles

Two such puzzles that I know about are: Unruly. This website has an online library of puzzles and solutions and a generator for puzzles of arbitrary size. Masyu. This website has a library of puzzles ...
• 4,640

### "Relatives" of the shortest path problem

Here is an answer to the first problem: Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest and smallest edge weights on the path is minimum. A paper ...
• 5,782

### NP-complete decision problems on deterministic automata

Minimizing deterministic Büchi automata is NP-complete, see Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata. Deciding whether a ...
• 8,923
Accepted

### NP-completeness: sum of "some" paths in a spanning tree

You are asking for the minimum weight fundamental cycle basis (in an unweighted graph). I think the standard reference for its NP-hardness is: Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (...
• 51.1k
Accepted

• 18.2k
Accepted

### Fixed parameter tractable Integer Programming and $FPP$

You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are ...
Accepted

### Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

Consider the following reduction from coNP-complete problem $k$-UNSAT to your language $L$ (where $k$-UNSAT is the language of all unsatisfiable $k$-CNF formulas): On input a $k$-CNF formula $\psi$, ...
• 2,883

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

Yes, there is such a problem. While the problem is arguably not "natural", it is certainly NP-complete. The problem is: for a degree 3 graph $G$, is $G$ either planar or Hamiltonian (i.e., ...
• 24.9k

### Does Memcomputing really solve an NP-complete problem?

I would like to add some additional information to Daniel Primosch's answer from above. The figure with the results from the paper he cited is accurate. We got in touch with the authors a while back ...
• 83
Accepted

### Reduction of graph chromatic number to hypergraph 2-colorability

As the other answer points out, the reduction in the original paper seems to have a bug: $H$ will not be two-colorable unless $G$ is bipartite. I couldn't quite see how to prove the reduction in the ...
• 18.2k
Accepted

### Complexity of Maximizing Hamming Distances Below a Threshold

Lemma 1. The problem is NP-hard, by reduction from Max-2-SAT. Proof sketch. The reduction is in two steps. Consider the variant of the problem in which $d$ is even and the coverage requirement is ...
• 10.9k
### Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known
The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete: Instance: An integer $k$; a $k$-partite graph $G=(V,E)$ Question: Does $G$ ...