26
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some ...
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.
...
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 ...
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 ...
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 ...
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 ...
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.
...
14
votes
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 ...
12
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 ...
12
votes
NP-hardness on Cayley graphs
Because the input size (a description of the group and its generators) can be so much smaller than the graph itself, even standard polynomial-time graph optimization problems can become hard on Cayley ...
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 $...
11
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
Computing VC dimension seems unlikely to be in polynomial time, but has a quasipolynomial time algorithm.
Also, it seems hard to detect a planted clique of size $O(\log n)$ in a random graph, but ...
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 ...
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} = \...
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 ...
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. ...
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 ...
8
votes
Accepted
Problem of graph bi-partition (related to graph isomorphism)
Your problem is NP-complete. Two-colorable perfect matching (which is NP-complete even when restricted to cubic planar graphs) is reducible to your problem. Take $H_1$ and $H_2$ to be perfect ...
8
votes
Accepted
Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis
First of all, Mahaney's Theorem says that merely assuming $\mathsf{P} \neq \mathsf{NP}$, there are no sparse $\mathsf{NP}$-complete sets. (Historically, Mahaney was motivated to study this precisely ...
8
votes
Accepted
Does p-isomorphism preserve phase transition?
Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L_1, L_2$, and $L_1$ exhibits a phase transition with ...
8
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
If the exponential time hypothesis is correct (or even weaker versions), then one can not solve 3SAT for instances with polyglog number of variables in polynomial time. Of course, quasi-polynomial ...
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 ...
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
...
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 ...
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 ...
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
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. (...
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})...
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. ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
np-complete × 169cc.complexity-theory × 61
np-hardness × 50
np × 20
graph-theory × 18
graph-algorithms × 15
reference-request × 13
reductions × 13
complexity-classes × 11
subset-sum × 10
sat × 8
time-complexity × 6
polynomial-time × 6
ds.algorithms × 4
approximation-algorithms × 4
p-vs-np × 4
complexity × 4
partition-problem × 4
factoring × 4
big-picture × 3
planar-graphs × 3
nt.number-theory × 3
polynomials × 3
integer-programming × 3
clique × 3