# Comparing $\mathbf{NP}$ and $\mathbf{E}$

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.

• 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. – Suresh Venkat Sep 7 '10 at 16:45
• 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. – Ryan Williams Sep 7 '10 at 16:46
• 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? – M.S. Dousti Sep 7 '10 at 17:09
• 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. – Kaveh Sep 7 '10 at 17:53
• Intuitively a reduction can increase the input size polynomially and then you would get a machine running in time $2^{n^k}$. – Kaveh Sep 7 '10 at 19:06

## 1 Answer

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.