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 ...
Pasin Manurangsi's user avatar
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. ...
Ryan O'Donnell's user avatar
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 ...
D.W.'s user avatar
  • 12k
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 ...
Antti Röyskö's user avatar
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 ...
David Eppstein's user avatar
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 ...
Lance Fortnow's user avatar
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. ...
usul's user avatar
  • 7,615
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 ...
Michael Lampis's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
David Eppstein's user avatar
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 $...
Marzio De Biasi's user avatar
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 ...
Joe Bebel's user avatar
  • 2,295
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 ...
Gamow's user avatar
  • 5,772
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} = \...
Joshua Grochow's user avatar
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 ...
David Eppstein's user avatar
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. ...
David Eppstein's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Sariel Har-Peled's user avatar
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 ...
Shaull's user avatar
  • 5,571
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 ...
Gamow's user avatar
  • 5,772
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 ...
Jan Johannsen's user avatar
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 ...
Gamow's user avatar
  • 5,772
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 ...
Denis's user avatar
  • 8,833
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. (...
David Eppstein's user avatar
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})...
Emil Jeřábek's user avatar
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. ...
Reijo Jaakkola's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible