24
votes
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
18
votes
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
17
votes
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
16
votes
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
16
votes
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
15
votes
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
14
votes
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
13
votes
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 ...
- 21.1k
12
votes
NP-complete decision problems on deterministic automata
The decision version of the DFA identification problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:
Input: Integer $k$ and sets $...
- 23.1k
10
votes
Accepted
Is the maximum independent set in cubic planar graphs NP-complete?
A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.
Bojan Mohar:
"Face Covers and the Genus Problem for Apex Graphs"
Journal of ...
- 5,782
10
votes
Accepted
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
This is unlikely to be NP-complete, as it can be solved in coRP, using a few calls to PIT. (It follows that this problem is not NP-complete unless $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{PH} = \...
- 37.8k
9
votes
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
9
votes
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
8
votes
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
8
votes
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
8
votes
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
8
votes
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
8
votes
"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
8
votes
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
8
votes
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
8
votes
Accepted
Unary language examples between L and NP
Classes of unary languages (above DLOGTIME) are just trivial variants of classes of usual, binary languages. Say, let us enumerate $\{0,1\}^*$ by natural numbers using the function $N(w_0\dots w_{n-1})...
- 18.2k
8
votes
Accepted
Lexicographic Boolean satisfiability
This problem is not in $NP$ (unless $PH$ collapses), since it is already $P^{NP}$-hard, see e.g. [1].
[1] K.W. Wagner. More Complicated Questions about Maxima and Minima, and some Closures of NP. ...
- 1,099
7
votes
NP-complete problems where the inputs are prime numbers
There are no known NP-complete problems whose input would consist of primes (or, say, $k$-tuples of primes, or even more complicated structures as long as they contain at least one prime of length $\...
- 18.2k
6
votes
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 ...
- 396
6
votes
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
6
votes
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
6
votes
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
6
votes
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
6
votes
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
5
votes
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$ ...
- 5,782
Only top scored, non community-wiki answers of a minimum length are eligible