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
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 ...
- 7,768
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 ...
- 18.2k
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 ...
- 29.4k
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:
...
- 23.1k
16
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. ...
- 995
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 ($\...
- 5,598
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 ...
- 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"...
- 6,665
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-...
- 37.8k
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 = ...
- 8,741
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 ...
- 2,883
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-...
- 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 ...
- 37.8k
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$
$...
- 5,782
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 ...
- 978
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 ...
- 978
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 "...
- 2,271
7
votes
Accepted
References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$
Here are some papers that have results similar to the ones you ask about.
Ronald V. Book, On Languages Accepted in Polynomial Time, SIAM J. Comput. 1, 1972, pp. 281-287.
In this paper, we find Theorem ...
- 2,271
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 ...
- 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 ...
- 18.2k
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 $\...
- 4,041
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'$...
- 18.2k
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:
"...
- 5,782
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 ...
- 51.1k
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 ...
- 1,934
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 ...
- 1,145
5
votes
Accepted
CVP to SVP reduction?
The short answer is "yes," but with several caveats, maybe the most important of which is that all known such reductions from CVP to SVP in the Euclidean norm are randomized. Self promotion: ...
- 5,083
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 ...
- 5,782
Only top scored, non community-wiki answers of a minimum length are eligible