Intractability

Some problems take so long to solve that we consider them essentially intractable

Proving intractability is actually quite difficult; this section is essentially a more general look at $\text{P}$ versus $\text{NP}$ and related questions

Hierarchy Theorems

Common sense suggests that giving a Turing machine more time or more space increases the class of problems it can solve

Subject to certain conditions, the hierarchy theorems prove this intuition as correct

Definition: A function $f:\mathcal{N}\to \mathcal{N}$, where $f(n)$ is at least $O(\log n)$, is called space constructible if there is some $O(f(n))$ space TM that maps $1^n$ to $f(n)$

Commonly occurring functions are space constructible, like ${\log }_{2}n$, $n{\log }_{2}n$, and $n^2$

This definition is useful because it helps us prove that an asymptotically larger function can be used to compute more functions

Space Hierarchy Theorem: For any space constructible function $f:\mathcal{N}\to \mathcal{N}$, a language $A$ exists that is decidable in $O(f(n))$ space but not in $o(f(n))$ space

We describe $A$ in terms of an algorithm that decides it in $O(f(n))$ space and guarantees it is different from any language in $o(f(n))$ space, using the diagonalization method

$D=$ “On input $w$:

1. Let $n$ be the length of $w$.
2. Compute $f(n)$ using space constructability and mark off this much tape. If later stages ever attempt to use more, reject.
3. If $w$ is not of the form $⟨M⟩10^{\ast }$ for some TM $M$, reject.
4. Simulate $M$ on $w$ while counting the number of steps used in the simulation. If the count ever exceeds $2^{f(n)}$, reject.
5. If $M$ accepts, reject. If $M$ rejects, accept.”

An important detail is that we use $⟨M⟩10^{\ast }$ to guarantee the asymptotic behavior kicks in for some input $w$

This machine is amazingly contrived but does work! It must behave differently from any decider that uses $o(f(n))$ space, and assuming otherwise leads to a clear contradiction

Corollary: If $f_1(n)$ is $o(f_2(n))$ and $f_2$ is space constructible then $\text{SPACE}(f_1(n))⊊\text{SPACE}(f_2(n))$

With some work, we can show that $n^c$ is space constructible for any rational number $c>0$, and since the rationals are dense in the reals, we can extend this to any real number

Corollary: For any two real numbers $0\le {ϵ}_1<{ϵ}_2$, $\text{SPACE}(n^{{ϵ}_1})⊊\text{SPACE}(n^{{ϵ}_2})$

Corollary: $\text{NL}⊊\text{PSPACE}$
This follows since we already had $\text{NL}\subseteq \text{SPACE}({\log }^{2}n)$ from Savitch’s theorem

Furthermore, this establishes the main objective of this section, which is the existence of intractable problems

Corollary: $\text{PSPACE}⊊\text{EXPSPACE}$

Definition: A function $t:\mathcal{N}\to \mathcal{N}$, where $t(n)$ is at least $O(n\log n)$, is called time constructible if there is some $O(t(n))$ time TM that maps $1^n$ to $t(n)$

This behaves analogously to our class of space constructible functions

Time Hierarchy Theorem: For any time constructible function $t:\mathcal{N}\to \mathcal{N}$, a language $A$ exists that is decidable in $O(t(n))$ time but not decidable in time $o(t(n)/\log t(n))$

The construction of $D$ is exactly the same, however we require $M$ decrement a counter of $\lceil t(n)/\log t(n)\rceil$ and reject if it hits 0

We can simulate $M$ in $O(t(n)/\log t(n))$ with a multi-tape construction, storing the transition function and states on separate tapes, which can be converted to a single-tape machine at a constant time factor

The essential difficulty is actually the need to update the counter each step, which adds a $O(\log t(n))$ factor to the whole process, bringing the algorithm to the desired $O(t(n))$ time

Then our proof works with the same contradiction argument

A tighter time hierarchy theorem is conceivable, especially if we could simulate a Turing machine with a time allotment with a smaller time factor, but has not been proven

Corollary: If $t_1(n)$ is $o(t_2(n)/\log t_2(n))$ and $t_2$ is time constructible, then $\text{TIME}(t_1(n))⊊\text{TIME}(t_2(n))$

Corollary: $\text{TIME}(n^{{ϵ}_1})⊊\text{TIME}(n^{{ϵ}_2})$

Corollary: $\text{P}⊊\text{EXPTIME}$

Therefore, intractable problems do exist, in both time and space

Exponential Space Completeness

The hierarchy theorems establish the existence of intractable problems but only implicitly

We use completeness to demonstrate actual intractable problems

Let $\uparrow$ be the exponentiation operation
If $R$ is a regular expression and $k$ is a nonnegative integer, we write $R\uparrow k$ to mean the concatenation of $R$ with itself $k$ times, $R^k=R\uparrow k=\underset{k}{\underbrace{R\circ R\circ \cdots \circ R}}$

Generalized regular expressions allow the exponentiation operation in addition to the usual regular operations $\cup$, $\circ$, and ${}^{\ast }$

Checking the equivalence of normal regular expressions can be done in polynomial time with a graph fill, but this does not apply to generalized regular expressions, because these expressions when expanded can have exponential size

Definition: A language $B$ is EXPSPACE-complete if $B\in \text{EXPSPACE}$ and every $A$ in $\text{EXPSPACE}$ is polynomial time reducible to $B$

Theorem: $E{Q}_{\text{REX}\uparrow }$ is $\text{EXPSPACE}$-complete

First, note that we can test that two NFAs with $q$ total states are inequivalent by nondeterministically reading an input symbol into both NFAs $2^q$ times, and accepting if one ever accepts without the other

This takes $O(n)$ time, so Savitch’s theorem gives us a $O(n^2)$ space algorithm for the problem

Then we can determine $E{Q}_{\text{REX}\uparrow }$ in $\text{EXPSPACE}$ by converting $R_1$ and $R_2$ to ordinary regular expressions, to NFAs, and then using the above deterministic algorithm

The tricky part is showing this is $\text{EXPSPACE}$-hard

Let $A$ be a language that is decided by a TM $M$ running in $2^{(n^k)}$ space for some constant $k$

Our reduction will produce a set of all possible strings $R_1={\Delta }^{\ast }$, and $R_2$, an expression which we will set up to generate all strings that aren’t rejecting computation histories on $w$

We divide $R_2=R_{\text{bad-start}}\cup R_{\text{bad-window}}\cup R_{\text{bad-reject}}$, representing the different places it could fail to be a proper rejecting computation history

Configuration $C_1$ looks like $q_0{w}_1{w}_2\dots w_n\bigsqcup \bigsqcup \cdots \bigsqcup \#$, which we match with the union of several subexpressions $R_{\text{bad-start}}=S_0\cup S_1\cup \cdots \cup S_n\cup S_b\cup S_{\#}$

For $S_0,\dots ,S_n$, we write ${\Delta }^i{\Delta }_{-w_i}{\Delta }^{\ast }$, where ${\Delta }_{-x}$ is a shorthand for the union of all characters except $x$

$S_b={\Delta }^{n+1}(\Delta \cup ϵ{)}^{2^{(n^k)-n-2}}{\Delta }_{-\bigsqcup }{\Delta }^{\ast }$ generates all strings that fail to contain a black symbol in some position $n+2$ through $2^{(n^k)}$

$S_{\#}={\Delta }^{2^{(n^k)}}{\Delta }_{-\#}{\Delta }^{\ast }$

Note that while the exponentiation operator wasn’t strictly necessary for $S_0,\dots ,S_n$, there was no way we could have matched $S_b$ and $S_{\#}$ without it

$R_{\text{bad-reject}}={\Delta }_{-q_{\text{reject}}}^{\ast }$ is trivial

We recall the idea from the proof of the Cook-Levin theorem that we can determine the validity of a transition function by looking at the changes in every three consecutive symbols

Thus, $R_{\text{bad-window}}=\bigcup _{\text{bad}(abc,def)}{\Delta }^{\ast }abc{\Delta }^{2^{(n^k)}-2}def{\Delta }^{\ast }$, where $\text{bad}(abc,def)$ means $abc$ doesn’t yield $def$ according to the transition function, which is a set of constant size

The largest parts of $R_2$ are exponents of magnitude $2^{(n^k)}$, which are $O(n^k)$ in binary, thus the length of $R_2$ is polynomial in $n$ and our mapping is complete

Relativization

Ultimately, the proof that $E{Q}_{\text{REX}\uparrow }$ is intractable rests on the hierarchy theorems’ use of the diagonalization method

This begs the question, can we use a similar method to show a strict hierarchy for $\text{P}$ and $\text{NP}$? Unfortunately, this would be tricky due to the method of relativization

Definition: An oracle for a language $A$ is a device that is capable of reporting whether any string $w$ is a member of $A$

An oracle Turing machine $M^A$ is a modified Turing machine that has the additional capability of querying an oracle for $A$ in one step, by writing a string onto a special oracle tape

$M^A$ is said to be computing relative to $A$, hence our term relativization

Definition: Let ${\text{P}}^A$ be the class of languages decidable with a polynomial time oracle Turing machine that uses oracle $A$, and define ${\text{NP}}^A$ similarly

It naturally follows that $\text{NP}\subseteq {\text{P}}^{SAT}$ and $\text{coNP}\subseteq {\text{P}}^{SAT}$

Furthermore, ${\text{NP}}^{SAT}$ contains languages we believe are not in $\text{NP}$, such as $\overline{MIN\text{-}FORMULA}$ (boolean formulas that are not minimal)

Theorem: $A$ exists such that ${\text{P}}^A\ne {\text{NP}}^A$ and $B$ exists such that ${\text{P}}^B={\text{NP}}^B$

This is a major barrier towards the use of diagonalization as a technique for proving $\text{P}=\text{NP}$, since diagonalization ought to be invariant towards the inclusion of oracles

How do we prove this theorem?

Proof:
Let $B$ be any $\text{PSPACE}$-complete problem such as $TQBF$

${\text{NP}}^{TQBF}\subseteq \text{NPSPACE}\subseteq \text{PSPACE}\subseteq {\text{P}}^{TQBF}$

The first containment follows definitionally, the second by Savitch’s theorem, and the third because $TQBF$ is $\text{PSPACE}$-complete, hence ${\text{P}}^{TQBF}={\text{NP}}^{TQBF}$

Let $L_A=\{w\mid \exists x\in A[|x|=|w|]\}$, i.e. the collection of all strings for which a string of equal length appears in $A$

We can easily construct a non-deterministic machine with an oracle $A$ that checks all strings of length $w$, so $L_A\in {\text{NP}}^A$

We index all polynomial time oracle TMs, and assume for simplicity that $M_i$ runs in time $n^i$ (this can be enforced fairly easily)

We decide what belongs to $A$ in stages; for each $i$, we declare strings part of $A$ such that $M_i^A$ cannot decide $L_A$

We choose $n$ greater than any string already declared in $A$, with $2^n>n^i$, and run $M_i$ on input $1^n$, responding with a no to any oracle queries

$M_i$ cannot query every string in $n^i$ time, so it is missing information about $A$

If $M_i$ finally answers false, then we add one string to $A$ that it hasn’t queried, and if it answers true then we leave $A$ with no strings of size $n$, so no matter what $M_i$ answers incorrectly

In summary, a method to solve $\text{P}$ versus $\text{NP}$ must somehow analyze computations, not just simulate machines

Circuit Complexity

Boolean circuits are the theoretical counterpart to digital circuits

Many believe that circuits are a convenient model for approaching theorems on computation, and they also provide a neat alternative proof that $SAT$ is $\text{NP}$-complete

Definition: A Boolean circuit is a collection of gates and inputs connected by wires

• Cycles are not permitted, and gates take the form of $\text{AND}$, $\text{OR}$, and $\text{NOT}$
• Wires carry the Boolean values 0 and 1, and gates compute their respective Boolean functions
• One gate is designated as the output gate
• The size of a circuit is the number of gates it contains
• The depth of a circuit is the length of the longest path from an input variable to an output gate

To a Boolean circuit $C$ with $n$ input variables and $k$ output gates, we associate a function $f_C:\{0,1{\}}^n\to \{0,1{\}}^k$ that matches $C$‘s behavior

In order to handle languages with variable length, we need some broader concepts

Definition: A circuit family $C$ is an infinite list of circuits, $(C_0,C_1,C_2,\dots )$ where $C_n$ has $n$ input variables

We say $C$ decides a language $A$ over $\{0,1\}$ if for every string $w$, $w\in A⟺C_n(w)=1$, where $n$ is the length of $w$

A circuit family is minimal if every $C_i$ in the list has no smaller equivalent circuit

The size complexity of a circuit family $C$ is the function $f:\mathcal{N}\to \mathcal{N}$, where $f(n)$ is the size of $C_n$

We define depth complexity similarly

Definition: The circuit complexity of a language is the size complexity of a minimal circuit family for that language, and the circuit depth complexity is defined similarly using depth instead of size

Theorem: Let $t:\mathcal{N}\to \mathcal{N}$ be a function, where $t(n)\ge n$; if $A\in \text{TIME}(t(n))$, then $A$ has circuit complexity $O(t^2(n))$

The key idea in proving this is that we can construct a circuit $C_n$ that simulates $M$ on inputs of length $n$, one row for each of the $t(n)$ steps in $M$‘s computation

Let $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{\text{accept}},q_{\text{reject}})$ decide $A$ in time $t(n)$ and let $w$ be an input of length $n$ to $M$

We look at a tableau for $M$ on $w$, a $t(n)\times t(n)$ table whose rows are configurations of $M$, where the top row contains the start configuration of $M$ on $w$ and the $i$th row contains the $i$th step of the computation

• For convenience, this tableau uses a composite character for the state $q$ of the tape head and the symbol at its location
• So each entry $(i,j)$ of the tableau contains either $\Gamma$ or a composite $Q\times \Gamma$, notated by $cell[i,j]$

We simplify by taking $M$ to only accept when the head is on the leftmost tape cell with a $\bigsqcup$, and remain there indefinitely

Importantly, the content of each cell is determined by the (at most) three cells bordering it in the row above

With this in mind, we can design the circuit to represent each cell, with a wire for each possible value in $\Gamma \cup (Q\times \Gamma )$, using a combination of $\wedge$ and $\vee$ gates to wire together cells

The cells in the first row are wired directly to the input variables, and the output gate is assigned to the wire denoting that $cell[t(n),1]$ is equal to $q_{\text{accept}}\bigsqcup$

It’s clear that the size of this circuit is proportional to $t^2(n)$

This theorem links circuit complexity with time complexity; if we demonstrate a language in $\text{NP}$ has non-polynomial circuit complexity, then $\text{P}\ne \text{NP}$

We can also derive a few more cool results with these tools

Let $CIRCUIT$-$SAT=\{⟨C⟩\mid C\text{ is a satisfiable Boolean circuit}\}$

Theorem: $CIRCUIT$-$SAT$ is $\text{NP}$-complete

To prove this, we must give a polynomial time reduction $f(w)=⟨C⟩$ where $w\in A⟺$ Boolean circuit $C$ is satisfiable

Because $A$ is in $\text{NP}$, it has a polynomial time verifier $V$ that takes inputs of form $⟨x,c⟩$

We obtain the circuit simulating $V$ and fill in the inputs that correspond to $x$ with the symbols of $w$; if $C$ is satisfiable then a certificate exists, meaning $w$ is in $A$ (and the converse also holds)

If the running time of the verifier is $n^k$ then the size of the circuit is $O(n^{2k})$, so the reduction is polynomial

Theorem: $3SAT$ is $\text{NP}$-complete (recall how we proved this before)

Without going into the details, it should be obvious that a circuit can be reduced to a Boolean formula by representing each wire with a variable and converting the gates appropriately

The size of the resulting expression is proportional to the size of the circuit, so the reduction is polynomial time