<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-09T15:29:07.250Z
2010-09-09T15:29:07.250Z
Robin Kothari
<p>We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$.</p>

<p>The <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aE">complexity zoo</a> states that $\mathbf{E}$  does not equal $\mathbf{NP}$, and cites the following paper:</p>

<p><a href="http://link.aip.org/link/?SMJCAT/1/281/1">R. Book. On languages accepted in polynomial time. <em>SIAM Journal on Computing</em>, 1(4):281–287, 1972.</a></p>

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

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

<p><em>Proof:</em> 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.</p>

CC BY-SA 2.5
2010-09-07T16:45:48.613Z
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
CC BY-SA 2.5
2010-09-07T16:46:02.247Z
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
CC BY-SA 2.5
2010-09-07T17:09:17.933Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-09-07T17:53:02.203Z
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
CC BY-SA 2.5
2010-09-07T18:50:11.240Z
Could you please elaborate on why $\mathbb{E}$ is not closed under Karp reductions?
Sadeq Dousti
CC BY-SA 2.5
2010-09-07T19:06:10.640Z
Intuitively a reduction can increase the input size polynomially and then you would get a machine running in time $2^{n^k}$.
Kaveh
<cc.complexity-theory><np-hardness><complexity-classes>
Comparing $\mathbf{NP}$ and $\mathbf{E}$
Sadeq Dousti
# Comparing $\mathbf{NP}$ and $\mathbf{E}$

(Asked by: username_0 on 2010-09-07)

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

The [complexity zoo](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aE) 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.](http://link.aip.org/link/?SMJCAT/1/281/1)

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.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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?  
> **username_3**: 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.  
> **username_0**: Could you please elaborate on why $\mathbb{E}$ is not closed under Karp reductions?  
> **username_3**: Intuitively a reduction can increase the input size polynomially and then you would get a machine running in time $2^{n^k}$.  

---

## 1 answers

### Answer by username_4 on 2010-09-09. Score: 9 | Accepted 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.


---

