5
$\begingroup$

We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$.

The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following paper:

R. Book. On languages accepted in polynomial time. SIAM Journal on Computing, 1(4):281–287, 1972.

I have not read the formal proof; though I want to know why the following "intuition" fails:

Intution: Every $\mathbf{NP}$ language is solvable in $O(2^n)$ time, where $n$ is the size of the input.

Proof: Assume that $L \in \mathbf{NP}$. There's a poly-time Karp reduction from $L$ to $3SAT$, and a $3SAT$ formula with $n$ variables can be decided via exhaustive search in $O(2^n)$ time.

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ but the "n" here is the size of an input to L. When converting to 3SAT, you might blow up the input to $N = n^5$, for example. Then your exhaustive search takes $2^{n^5}$ time. $\endgroup$ – Suresh Venkat Sep 7 '10 at 16:45
  • 9
    $\begingroup$ The polynomial time reduction from $L$ to $3SAT$ may map instances of $L$ of length $n$ to instances of $3SAT$ of length $n^k$, and hence the number of variables in the $3SAT$ instance may be $n^k$. Then, exhaustive search takes $O(2^{n^k})$ time. $\endgroup$ – Ryan Williams Sep 7 '10 at 16:46
  • $\begingroup$ Thanks a lot. I got it. Is there an upper bound on this "blow-up" effect? (probably not, since it separates NP and EXP). Moreover, do you know of any concrete example in which such blow-up happens? $\endgroup$ – M.S. Dousti Sep 7 '10 at 17:09
  • 7
    $\begingroup$ The reason that $E$ is not equal to $NP$ is that the former is not closed under Karp reductions, so we don't really separate them, $E$ is simply not equal to any class which is closed under Karp reductions. $\endgroup$ – Kaveh Sep 7 '10 at 17:53
  • 1
    $\begingroup$ Intuitively a reduction can increase the input size polynomially and then you would get a machine running in time $2^{n^k}$. $\endgroup$ – Kaveh Sep 7 '10 at 19:06
8
$\begingroup$

This was a comment, but it became too long. I want to give an explicit example where the input size increases. Take the classic reduction from CircuitSAT to 3SAT. The usual idea is to assign a variable to every gate in the circuit. The variable's value is the output of the gate. The you add the constraints that make a gate's output reflect the gate's input and gate type. So if a gate (whose variable is g_1) is an AND gate and has input wires coming from gates g_2 and g_3, you'll get a constraint like g_1 = g_2 AND g_3. We also have variables for the inputs, of course.

With this reduction, even though there are n inputs, if the size of the circuit is, say, $O(n^5)$, then the resulting SAT instance will have $O(n^5)$ variables, which will require $O(2^{n^5})$ time to solve by brute forcing on a deterministic TM.

You also asked why E is not closed under Karp reductions. That's easy. Take a problem that only be solved in $O(2^{n^2})$ time, and therefore it is not in E. Now we can Karp-reduce this to a language in E by padding the input with $O(n^2)$ zeros. The language in E to which we're reducing is the original language with each input of size n padded with $O(n^2)$ zeros. Now since the input size is $O(n^2)$ and we know an algorithm that solves this in $O(2^{n^2})$ time, this problem is in E. So we reduced a problem not in E to a problem in E, showing that E is not closed under Karp reductions.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.