33
I don't really have references for these results--they aren't hard to prove once you understand Ladner's theorem.
No, for any NP-incomplete set A there is another set B strictly between A and SAT.
These equivalence classes are known as polynomial-many-one degrees. You can embed any finite poset into the degrees below NP. In particular the degrees are not ...
24
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.
Consider Boolean formulas and SAT.
Using padding and slightly modifying the encoding of formulas
we can make sure that
$\varphi$ and $\lnot \varphi$ have the ...
22
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 comprehensive answer than this, but its author removed it for some reason. Hopefully the question can continue to get more answers.
$\mathsf{P}/\mathsf{poly}$ is the set ...
20
Integer Programming.
Showing that if there is an integer solution then there is a polynomial size integer solution is quite involved. See
Christos Papadimitriou, "On the Complexity of Integer Programming", JACM, 1981.
19
The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General resolution is exponentially more powerful than tree-like resolution, as shown for example by Ben-Sasson, Impagliazzo and Wigderson. The concept has also been ...
19
No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\mathrm{NP}=\mathrm{RP}$ and $\mathrm{PH}=\mathrm{ZPP^{RP}}=\mathrm{BPP}$; in particular, it is not even known to imply $\mathrm{NP}=\mathrm{coNP}$. (However, all ...
19
Just an extended comment to better explain ARi's comment (I was writing it while I saw it).
It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example:
$A_1 = \{ x \mid x \in SAT \land f(|x|) \text { is even}\} \cup \{x \mid f(|x|) \text{ is odd} \}$
$A_2 = \{ x \mid x \in SAT \land f(|x|) \text { is odd}\} \...
19
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 claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, ...
18
While the problem "is the crossing number of a graph at most $k$?" is trivially in NP,
the NP-membership of the related problems for the rectilinear crossing number and
the pair crossing number are highly not obvious;
cf. Bienstock, Some probably hard crossing number problems, Discrete Comput. Geometry 6 (1991) 443-459, and
Schaefer et al., Recognizing ...
17
If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:
Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject
Another - less trivial - example that relies on no assumption is the following:
Input: x (boolean ...
16
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 machine, etc. A good place to start looking is this Lambda the Ultimate post, which has some good further references.
Section 7.4 of Bob Harper's Practical ...
15
I can only give a partial answer to this question.
A result by Lenstra (later improved by Kannan, and Frank and Tardos) states that ILP with $k$ variables can be solved in time $k^{O(k)}$ (times a polynomial in the size of the ILP). Therefore, ILP is in P when the number of variables is $O(\log n/\log\log n)$. I am not sure if a $2^{O(k)}$ algorithm is ...
15
Actually, acceptance of nondeterministic Turing machines in time $t$ is $O(t \log t)$-time reducible to SAT (the construction is via oblivious simulation, see Arora-Barak), so typically any time a nondeterministic machine is appreciably faster than a deterministic one, we'll see at least some speedup with a SAT oracle.
To be more concrete, primality testing ...
14
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 the reduction, we may very well increase the variable $n$ in question substantially (by some polynomial). And the canonical reductions do blow it up quite ...
14
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 ($\mathsf{NP}$-completeness of SAT) using a functional language (a variant of the λ-calculus) instead of Turing machines. A summary:
the key notion is that of affine ...
14
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". The class $\Pi_1^P$ in there is of course coNP. Stockmeyer wrote a full paper on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.
13
My favourite example is a classic 1977 result of Ashok Chandra and Philip Merlin. They showed that the query containment problem was decidable for conjunctive queries. The conjunctive query containment problem turns out to be equivalent to deciding whether there is a homomorphism between the two input queries. This rephrases a semantics problem, involving ...
12
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-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ ...
11
You can take a look to:
Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, and Aleksandar Chakarov. 2009. Tricolorable torus knots are NP-complete. In Proceedings of the 47th Annual Southeast Regional Conference (ACM-SE 47). ACM, New York, NY, USA, , Article 42 , 6 pages.
Abstract: This work presents a method for associating a class of ...
11
This is a very interesting question.
First, a clarifying remark. Note that "upper bound on the number of witnesses" is not a property of a computational problem per se, but of a particular verifier used to decide an $NP$ problem, just as an "upper bound on number of states" would not be a property of a problem but of a Turing machine deciding it. So saying ...
11
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 to show that $P^{NP \cap coNP} = NP \cap coNP$. Clearly, one direction is obviously true: $NP \cap coNP \subseteq P^{NP \cap coNP}$. To prove the other ...
11
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 = EXP.
The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.
10
How about the edge coloring number in a dense graph (aka Chromatic index)? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the natural witness describing the coloring has size $n^2\log n$. Of course, there might be shorter proofs for class 1 graphs in Vizing's theorem.
See also this possibly related question
9
There are a few references in the first paragraph of
Marc Lackenby. A polynomial upper bound on Reidemeister moves. arXiv:1302.0180
In particular, the author says that the problem of recognizing that a knot diagram represents the unknot is in $\mathbf{NP} \cap \mathbf{coNP}$, by combining a result of Hass-Lagarias-Pippenger (that unknottedness is in NP) ...
9
I think the $k$-clique cover problem, which asks whether there exists a partition of the vertices in $k$ sets such that each set induces a clique, has the desired properties.
Clearly, taking induced subgraphs can't make the minimum size of such partition increase. On the other hand, when you take the disjoint union of two graphs, you have to take the union ...
8
Such a characterization of NP follows from the NP-hardness of any gap problem for a binary CSP with constraints of arity 2.
A binary CSP with arity 2 constraints is given by a family $\Pi$ of arity 2 relations on $\{0, 1\}^n$. An instance is given by a set of constraints. The GapCSP$_\Pi$($c$,$s$) problem for the CSP is the promise problem of distinguishing ...
8
Here is an example, which appears a natural problem.
Instance: Positive integers, $d_1,\ldots,d_n$ and $k$, all bounded from above by $n$.
Question: Does there exist a $k$-colorable graph with degree sequence $d_1,\ldots,d_n$ ?
Here the input can be described with $O(n\log n)$ bits, but the witness may require $\Omega(n^2)$ bits.
Remark: I do not have ...
8
I came along some quite natural NP-complete problems that seemingly require long witnesses. The problems, parameterized by integers $C$ and $D$ are as follows:
Input: A one-tape TM $M$
Question: Is there some $n\in\mathbb{N}$, such that $M$ makes more than $Cn+D$ steps on some input of length $n$?
Sometimes the complement of the problem is easier to state: ...
8
Müller and Szeider study Resolution proofs where the proof DAG has bounded tree-width or bounded path-width (for suitable extensions of these graph complexity measures to directed graphs.)
They show that the path-width of the DAG is essentially the same as the space complexity of the proof, and define a generalized notion of proof space which is equivalent ...
8
Comment => Answer.
In this paper, Posa shows that for some constant $c$, a graph chosen from the Erdos-Renyi random graph distribution $G(n, c \log n / n)$ has a Hamiltonian cycle with probability approaching $1$ as $n \rightarrow \infty$. If we encode the input to the Hamiltonian Cycle problem as simply a bit-string representing its adjacency matrix, the ...
Only top voted, non community-wiki answers of a minimum length are eligible