62
Depends on what you mean by subexponential. Below I explain a few meanings of "subexponential" and what happens in each case. Each of these classes is contained in the classes below it.
I. $2^{n^{o(1)}}$
If by subexpoential you mean $2^{n^{o(1)}}$, then a conjecture in complexity theory called ETH (Exponential Time Hypothesis) implies that no $\mathsf{NP}$-...
44
This is only possible if there are many admissible outputs for a given input. I.e., when the relation $R$ is not a function because it violates uniqueness.
For instance, consider this problem:
Given $n \in \mathbb{N}$ (represented in unary) and a TM $M$, produce another TM $N$ such that $L(M)=L(N)$ and $\# N > n$ (where $\# N$ stands for the encoding (...
41
There are two cases:
$P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we ...
36
NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances.
The class of problems where you can verify "no" instances in polynomial time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you ...
33
Just to list some, all with running time more or less $2^{O(\sqrt{n} \log n)}n^{O(1)}$ or $2^{O(\sqrt{n})}n^{O(1)}$:
Feedback Arc Set on Tournaments [Noga Alon , Daniel Lokshtanov , Saket Saurabh, ALP 2009]
Minimum Fill-in and Chain Completion [Fomin and Villanger SODA 2012]
Split Edge Deletion [Ghosh et al SWAT 2012]
Cluster Editing with $t$ clusters [...
27
Generally speaking, the following is true for any algorithm:
Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain ...
24
Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}_n$ states (informally) that there is no bijection $[n+1] \to [n]$. This sequence of propositions is hard for certain propositional proof systems.
The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, ...
23
Your question doesn't make sense:
The problem is NP-complete (proven) for all input data (without exception).
This is not a thing. NP-completeness is a property of entire sets, not of specific inputs. It's fairly trivial to show that, if you choose a specific input, any problem is $O(1)$ on that input: you just output yes or no, depending which is ...
21
No. This direction is unlikely to be useful, for two reasons:
Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the ...
19
There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness.
[AN6] NON-DIVISIBILITY OF A PRODUCT POLYNOMIAL
INSTANCE: Sequences $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ of pairs of integers, ...
19
So your problem is as follows:
Input: integers $\ell,u$
Question: does there exist a prime in $[\ell,u]$?
As far as I know, it is not known whether that problem is in P or not.
Here's what I do know:
Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the ...
19
The Post correspondence problem is undecidable, and in particular it is not in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just proved it). That is, for your certifier to prove that the Post correspondence problem is in NP, it needs to run in polynomial time (in terms of the size of the ...
18
It is maybe easier to consider the contrapositive, that is ${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$.
So assume ${\sf P}={\sf NP}$, then
for every $L\in {\sf NP}$, we have $L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement, $\bar L\in {\sf P}$ and therefore $L\in {\sf coNP}$.
for every $L\in {\sf coNP}$, we have $\...
17
There are two possible bugs in this proof:
When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\...
17
The problem isn't really well-posed. For any particular instance, there is a single solution, say $S$. Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what input you give it, all it does is just print $S$. This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$.
...
16
Your language is in P. Suppose that the matrix is $n\times n$ and that the words have total length $\ell$. Each word can start at at most $n^2$ positions and be written in $O(1)$ many orientations, for a total of $O(n^2)$ possible placements. Checking each one costs at most $O(m)$, where $m$ is the length of the word. In total, we obtain an algorithm whose ...
15
Here's another way of looking at the point that Shaull makes with respect to "deciders".
A problem is in NP if and only if there is an algorithm $V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$ such that
for every YES instance $x \in \{0,1\}^n$, there is a certificate $p \in \{0,1\}^{\mathrm{poly}(n)}$ such that $V(x,p) = 1$; and
for every NO ...
15
First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.
If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. ...
15
If a finite problem is NP-complete then P=NP, since every finite problem has a polynomial time algorithm (even a constant time algorithm).
When we say that Sudoku is NP-complete, we mean that a generalized version of Sudoku played on an $n^2 \times n^2$ board is NP-complete.
Finally, the 4-clique problem, while not a finite problem (the input graph has ...
14
One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity. You may be familiar with the basic definition of a problem $\Pi$ being NP-complete:
$\Pi$ is in NP, and
For every other problem $\Xi$ in NP, we can turn an ...
14
It is known that any proof of super-polynomial circuit lower bounds (which are slightly stronger statements than $P\neq NP$) require super-polynomial, even exponential size proofs in weak proof systems like resolution. Generalizing this to stronger proof systems is a well known open problem.
See section 5 of this survey by A. Razborov where these things ...
14
Actually you're wrong. In the example you give, you take a list of integers, but even with binary representation for the numbers in the list, the input length is still linear in the number of elements of that list, so the algorithm is polynomial ( not pseudo ). Complexity is always measured in respect to the total input length, not some arbitrary number ( b )...
13
We do know all problems in NP. Each problem in NP is given by a non-deterministic Turing machine running in polynomial time. Steve Cook (and, independently, Leonid Levin) proved that SAT is NP-complete by encoding the statement "Machine $M$ accepts $x$ given non-deterministic choices $y$" as a logical formula for every non-deterministic Turing machine; for a ...
13
First, let's refresh the proof that the definition given is indeed equivalent to the standard definition of NP, i.e., the class of languages accepted by polynomial-time nondeterministic Turing machines.
Suppose $L$ is accepted by a polynomial-time Turing machine $M$. There is some $c$ such that $M$ runs in time $|x|^c$ for all inputs $x$. The verification ...
13
Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not accurate).
It might help to think about reductions in these terms (everything I'll talk about here will be polynomial time, so I will leave that out just so I ...
13
The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI ...
13
One way to consider the difference between decision version and optimization version is by considering different optimization versions of the same decision version. Take for example the MAX-CLIQUE problem, which is very hard to approximate in terms of the usual parameter – the size of the clique. If we change the optimization parameter to the logarithm of ...
13
In fact, you don't need the P$\,\neq\,$NP hypothesis, since there are even infinite constant-time decidable subsets of NP-complete problems. For any NP-complete language $L\subseteq\{0,1\}^*$, let $L' = \{0w\mid w\in L\}\cup\{1w\mid w\in\{0,1\}^*\}$. $L'$ is still NP-complete (trivial reduction from $L$), but it contains the infinite constant-...
12
From an answer to a related question on NP-hard problems which are not contained in NP: probably the most natural example is determining whether two regular expressions (including the Kleene star for arbitrary repetition, and a squaring operation to allow compact expressions of very large fixed numbers of repetitions) are equivalent. The resulting problem is ...
12
Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US.
UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs".
US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be ...
Only top voted, non community-wiki answers of a minimum length are eligible
