Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
22 votes
Accepted

Implications of proving NP=RP on complexity theory

Prelude: the below is just one consequence of $\mathsf{RP}=\mathsf{NP}$ and probably not the most important, e.g. compared to collapse of the polynomial hierarchy. There was a great and more ...
usul's user avatar
  • 7,615
19 votes
Accepted

Euclidean TSP in NP and square root complexity

Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as ...
Sasho Nikolov's user avatar
18 votes
Accepted

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM ...
Andrej Bauer's user avatar
  • 29.1k
17 votes
Accepted

Algorithm whose running time depends on P vs. NP

If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following: ...
Marzio De Biasi's user avatar
15 votes

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

At the request of Andrej and PhD, I am turning my comment into an answer, with apologies for self-advertising. I recently wrote a paper in which I look at how to prove the Cook-Levin theorem ($\...
Damiano Mazza's user avatar
15 votes
Accepted

Status of András Faragó’s (second) claimed proof that NP=RP

It seems to me that Theorem 1 in the paper is false for essentially the same reasons as the Peres example showed in the last version. Theorem 1 seems to say the following, at least in a special case. ...
Jason Gaitonde's user avatar
14 votes

Questions regarding SETH

The subtlety comes in where we introduce the notion of "harder". The reduction showing that SAT can be reduced to Hamiltonian Cycle shows that the latter is "harder" up to polynomial factors. In doing ...
Yonatan N's user avatar
  • 1,642
14 votes
Accepted

When was co-NP introduced for the first time?

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space"...
Hermann Gruber's user avatar
12 votes
Accepted

Are There Highly Symmetric NP- or P-complete Languages?

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-...
Joshua Grochow's user avatar
11 votes

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = ...
Lance Fortnow's user avatar
11 votes
Accepted

Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below). We want ...
Mikhail Rudoy's user avatar
9 votes
Accepted

Enumerating finite set of words with Hamming distance $1$

This problem is NP-complete. The class of graphs in the question is equivalent to the cubical graphs *1, but this class contains grid graphs. Because the Hamiltonian path problem in grid graphs is NP-...
pcpthm's user avatar
  • 206
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

Is there any relationship of hardness between the two problems?

No, you cannot infer hardness of P1. (And your question looks suspiciously close to homework.) Consider the special case where $D$ is an undirected graph $G=(V,E)$ $x$ is a subset $E_x\subseteq E$ $...
Gamow's user avatar
  • 5,772
8 votes
Accepted

List of NP-Complete graph problems/ properties?

A general list of NP-complete problems can be found in Garey & Johnson's book "Computers and Intractability". It contains an appendix that lists roughly 300 NP-complete problems, and despite its ...
Mark Schultz-Wu's user avatar
7 votes

Problems in NP with non-trivial certificate

I feel like problems $P\in\mathsf{NP}\cap\mathsf{coNP}$ are good examples for your question. Typically, for $P\not\in\mathsf{P}$, at least one of the witnesses is non-trivial. For example, the closest ...
Mark Schultz-Wu's user avatar
7 votes

is SUBEXP contained within PSPACE?, NP?

SUBEXP is neither known or widely believed to lie in PSPACE (and -- contrary to one of the comments -- this is not known to have any connection to SETH). It is not known whether the containment "...
Eric Allender's user avatar
6 votes

Questions regarding SETH

Cygan, Kratsch and Nederlof give a $(2+\sqrt{2})^{\texttt{pw}} n^{O(1)}$ algorithm for hamiltonicity on graphs with $n$ vertices and pathwidth $\texttt{pw}$ (assuming you are given the pathwidth ...
Yuval Filmus's user avatar
  • 14.5k
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 ...
Sasho Nikolov's user avatar
6 votes

Implications of proving NP=RP on complexity theory

A simple answer is that we're "pretty sure" that $\mathsf{P} \neq \mathsf{NP}$, and we're "pretty sure" that $\mathsf{P} = \mathsf{RP}$, so we're "pretty sure" that $\...
Mahdi Cheraghchi's user avatar
6 votes
Accepted

Conversion between NP certificates

For general $L\in\mathrm{NP}$, this is equivalent to $\mathrm{FP=TFNP}$, hence likely false: On the one hand, if $V$ and $V'$ are verifiers of $L$, then “given $x$ and $u$ such that $V(x,u)$, find $u'$...
Emil Jeřábek's user avatar
5 votes
Accepted

NP completeness of classes of spanning trees

Lemke has shown that it is NP-hard to decide whether a cubic graph on $n=2k$ vertices has a spanning tree in which $k+1$ vertices have degree $1$ and $k-1$ vertices have degree $3$. P. Lemke: "...
Gamow's user avatar
  • 5,772
5 votes

Are There Highly Symmetric NP- or P-complete Languages?

My intuition is that an NP-complete language of this type would cause a collapse of the polynomial hierarchy much like the one in the Karp–Lipton theorem. More specifically, if you go up to the ...
David Eppstein's user avatar
5 votes

List of NP-Complete graph problems/ properties?

You may also have a look at the Compendium of Parameterized Problems by Marco Cesati (http://cesati.sprg.uniroma2.it/research/compendium/) which contains a list of many hard graph problems. The ...
Christian Komusiewicz's user avatar
5 votes

Problems in NP with non-trivial certificate

Kuperberg's certificate of knottedness of a knot is not entirely trivial, and (I believe still) contingent on the Generalized Riemann Hypothesis. It includes lots of not super-difficult, but not ...
Mark S's user avatar
  • 1,125
4 votes

Euclidean TSP in NP and square root complexity

You wrote: On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although ...
Gamow's user avatar
  • 5,772
4 votes
Accepted

Complexity of a satisfiability problem

This is NP-hard. Here is a reduction from SAT. Suppose you have a CNF formula $\varphi$ with variables $x_1,\dots,x_n$. Add variables $x'_1,\dots,x'_n$ and clauses of the form $x_i \to \neg x'_i$ ...
D.W.'s user avatar
  • 12.1k
4 votes
Accepted

END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node

This class was defined in Papadimitriou's original 1994 paper, that also introduced the class PPAD, and it is known as PPADS. There is an oracle separation between the two classes. For a recent paper ...
domotorp's user avatar
  • 14k

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