CircuitSat $\in$ DTIME $(2^{n})$ consequences

$CircuitSat \in DTIME (2^{n})$ does not imply $NP \subseteq DTIME (2^{n})$ since the reduction might increase the input’s size. Suppose for example that $L \in N P$ and the reduction from $L$ to $CircuitSat$ maps strings of length $n$ to strings of length $n^{c}$ (for all $n \in N$ ), then applying the reduction and using a naive exponential time algorithm for circuit sat yields a $2^{n^{c}}$ time algorithm for $L$ .

If however you can place an NP-complete problem in a subexponential time class, e.g. $n^{\log n}$ , then $N P \neq E X P$ , since $n^{O (\log n)}$ is closed under polynomial transformations, i.e. $n \mapsto n^{c}$ .

P/poly $= \cup_{c \in N}$ SIZE $(n^{c})$ consequences

If NEXPTIME $\subset P / p o l y$ then NEXPTIME = EXPTIME. Proof that $B P P \subseteq P / P o l y$ Let L be a language in BPP, and let $M (x, r)$ be a polynomial-time algorithm that decides $L$ with error $\leq 1 / 3$ (where x is the input string and r is a set of random bits).

Construct a new machine $M^{'} (x, r)$ , which runs $M, 48 n$ times and takes a majority vote of the results (where $n$ is the input length and R is a sequence of $48 n$ independently random $r^{'} s$ ). Thus, $M^{'}$ is also polynomial-time, and has an error probability $\leq 1 / e$ by the (chernof). If we can fix $R$ then we obtain an algorithm that is deterministic.

If $Bad (x)$ is defined as ${R : M^{'} (x, R) is incorrect}$ , we have:

: $\forall x {Prob}_{R} [R \in Bad (x)] \leq \frac{1}{e^{n}} .$ >

The input size is ”n”, so there are 2<sup>”n”</sup> possible inputs. Thus, by the [[union bound]], the probability that a random ”R” is bad for at least one input ”x” is

: ${P r o b}_{R} [\exists x R \in Bad (x)] \leq \frac{2^{n}}{e^{n}} < 1.$

In words, the probability that ”R” is bad for some ”x” is less than 1, therefore there must be an ”R” that is good for all ”x”. Take such an ”R” to be the advice string in our ”’P/poly”’ algorithm.

Prove that PP is closed under complement

algorithm A with the property that $x \in L \Rightarrow \Pr [A (x) = 1] > \frac{1}{2}$ and $x \notin L \Rightarrow \Pr [A (x) = 1] \leq \frac{1}{2}$ .

> Let $f (| x |)$ be the > polynomial upper bound on the running time of A on input x. Thus A > makes at most $f (| x |)$ random coin flips during its execution. In > particular, $x \in L \Rightarrow \Pr [A (x) = 1] \geq \frac{1}{2} + \frac{1}{2^{f (| x |)}}$ .

I understand that:

- By definition of PP, $x \in L \Rightarrow \Pr [A (x) = 1] > \frac{1}{2}$ . It means that if indeed $x \in L$ , more than half of the possible coin flip combinations would cause the algorithm to accept. - The algorithm’s running time is bound by $f (| x |)$ , then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f (| x |)} = \frac{1}{2^{f (| x |)}}$ .

But why is it so obvious that $x \in L \Rightarrow \Pr [A (x) = 1] \geq \frac{1}{2} + \frac{1}{2^{f (| x |)}}$

x \notin L \Rightarrow Pr [A^{'} acc x] \leq \frac{1}{2} \cdot (1 - \frac{1}{2^{f (| x |) + 1}}) < \frac{1}{2}

and x \in L \Rightarrow Pr [A^{'} acc x] \geq (\frac{1}{2} + \frac{1}{2^{f (| x |)}}) \cdot (1 - \frac{1}{2^{f (| x |) + 1}}) > \frac{1}{2} .

This justifies the assumption (since A is still a polynomial-time probabilistic algorithm) and completes the proof.

Theorem

(extended rice) Let $C \subset R E$ s.t $Σ^{*} \notin C, C \neq \emptyset .$ then $L_{C} \notin R E$

L_{C} = {⟨ M ⟩ : M is TM and L (M) \in C} \notin R E

Proof ▼

$\overset{―}{A C C} \leq_{m} L_{C}$ and Let $M_{A}$ be TM that accept some $A \in C$ . Define $f (⟨ M, w ⟩) \mapsto ⟨ B_{M, w} ⟩$ ,
$B_{M, w}$ On input $x$ : Emulate $M_{A} (x)$ and $M (w)$ in parallel, and accept if one of them does.

⟨ B_{M, w} ⟩ \in \overset{―}{A C C} \Rightarrow L (B_{M, w}) = A \in C ⟨ B_{M, w} ⟩ \notin \overset{―}{A C C} \Rightarrow L (B_{M, w}) = Σ^{*} \notin C

Rice extended(not the version we saw)

theorem Given a property $S \subseteq R E$ , the language

L_{S} = {⟨ M ⟩ ∣ L (M) \in S}

is recursively-enumerable ( $L_{S} \in R E$ ) if and only if all the following three statements jointly hold
1. For any two $L_{1}, L_{2} \in R E$ , if $L_{1} \in S$ and also $L_{1} \subseteq L_{2}$ then also $L_{2} \in S$ .
2. If $L_{1} \in S$ then there exists a finite subset $L_{2} \subseteq L_{1}$ so that $L_{2} \in S$ .
3. The set of all *finite* languages in $S$ is enumerable (in other words: there is a TM that enumerates all the finite languages $L \in S$ ).

Proof ▼

If (1,2) hold, but (3) does not, then $L_{S} \notin R E$ *. Let’s assume that $L_{S} \in R E$ , and we’ll see that we have a way to accept any finite languages in $S$ (and thus, the set of all these languages is RE), thus condition (3) holds and we reach a contradiction. How to decide if a finite $L$ belongs to $S$ or not? Easily – we use the description of $L$ to construct a machine $M_{L}$ that accepts only the words in $L$ , and now we run the machine of $L_{S}$ on $M_{L}$ (remember - we assumed $L_{S} \in R E$ , so there is a machine that accepts $L_{S}$ !). If $L \in S$ then $⟨ M_{L} ⟩ \in L_{S}$ and since $L_{S} \in R E$ , its machine will say yes on the input $⟨ M_{L} ⟩$ , and we are done.
If (2,3) hold, but (1) does not, then $L_{S} \notin R E$ *. We assume that $L_{S} \in R E$ and we’ll show that we have a way to decide $H P$ , leading to a contradiction.

Because condition (1) doesn’t hold, there is a language $L_{1} \in S$ and a superset of it, $L_{2} \supseteq L_{1}$ so that $L_{2} \notin S$ . Now we are going to repeat the argument used in Section 4 to decide $H P$ : given an input $(⟨ M ⟩, x)$ for $H P$ , we construct a machine $M^{'}$ whose language is $L_{1}$ if $(⟨ M ⟩, x) \notin H P$ or otherwise, its language is $L_{2}$ . Then, we can decide $H P$ : either $M$ halts on $x$ , or the RE-machine for $L_{S}$ accepts $M^{'}$ ; we can run both in parallel and are guaranteed that at least one will halt.

Let’s give the details of constructing $M^{'}$ (on input $x^{'}$ ):

1. Do the following in parallel: 1.1 run $M$ on $x$ . 1.2 run the machine of $L_{1}$ on $x^{'}$ 2. If 1.2 halts and accepts - accept. 3. If 1.1 halts: run the machine of $L_{2}$ on $x^{'}$ .

Why does this work? If $(⟨ M ⟩, x) \notin H P$ then 1.1 never halts, and $M^{'}$ accepts exactly all the inputs that are being accepted at step 1.2, so $L (M^{'}) = L_{1}$ . On the other hand, if $(⟨ M ⟩, x) \in H P$ then, at some point step 1.1 halts and $M^{'}$ accepts exactly $L_{2}$ . It may happen that $1.2$ accepts beforehand, but since $L_{1} \subseteq L_{2}$ , this doesn’t change the language of $M^{'}$ in this case.
If (1,3) hold, but (2) does not, then $L_{S} \notin R E$ *. Again, we will assume $L_{S} \in R E$ and show that $H P$ becomes decidable, which is a contradiction.

If condition (2) doesn’t hold, then for any $L_{1} \in S$ , all its finite subsets $L_{2} \subseteq L_{1}$ satisfy $L_{2} \notin S$ (note that $L_{1}$ must be infinite, since $L_{1} \subseteq L_{1}$ ). As in the above, in order to decide $H P$ for a given input $(⟨ M ⟩, x)$ , we construct a machine $M^{'}$ whose language is $L_{1}$ if $(⟨ M ⟩, x) \notin H P$ and some finite $L_{2}$ otherwise. The contradiction follows in a similar way as above.

The construction of this machine is quite similar to the previous $M^{'}$ we constructed. The machine $M^{'}$ (on input $x^{'}$ ) does:

1. Runs $M$ on $x$ for $| x^{'} |$ steps. 2. If $M$ halts during step 1 – reject 3. Otherwise, run the machine of $L_{1}$ on $x^{'}$ .

It holds that, if $(⟨ M ⟩, x) \in H P$ , then at some point, say after 1000 steps, $M$ halts on $x$ . Therefore, step 1 will halt on (and reject) any input $x^{'}$ of length $> 1000$ . Therefore, in this case, $L (M^{'})$ is **finite**. Also note that $L (M^{'}) \subseteq L_{1}$ , and in particular, by our assumptions on the invalidity of condition (2), we have that $L (M) \notin S$ .

On the other hand, if $(⟨ M ⟩, x) \notin H P$ , then step 1 never halts, and we never reject at step 2. In this case it is easy to see that $L (M) = L_{1}$ and in particular, $L (M) \in S$ .

We are left to show the other direction of the extended theorem. That is, we need to show that if all the conditions (1,2,3) hold, then we have a TM that accepts $L_{S}$ , that is, $L_{S} \in R E$ . In other words, we need to show a machine $M_{S}$ so that for any input $⟨ M ⟩$ for which $L (M) \in S$ , the machine accepts this input, $M_{S} (⟨ M ⟩) \to accept$ .

Here is how the machine $M_{S}$ behaves (on input $⟨ M ⟩$ ):

1. Let $M_{enum S}$ be the machine that enumerates all the finite languages in $S$ , guaranteed by condition (3). 2. Run the following in parallel for $i = 1, 2, . . .$ 2.1 Run $M_{enum S}$ until it outputs the language $L_{i}$ 2.2. Check if $M$ accepts all the words of $L_{i}$ (run $M$ on these words, again in parallel). 2.3. If for some $i$ , $M$ accepts all the words of $L_{i}$ – accept.

Why does it work? If $L (M) \in S$ then it has a finite subset $L_{j} \in S$ , and once $M_{enum S}$ outputs that subset, step 2.2/2.3 will find that $M$ accepts all the words in that language and accept.

On the other hand, if $L (M) \notin S$ it cannot be accepting all the words in $L_{i}$ for any $i = 1, 2, . . .$ . Indeed, by condition (1), any $L^{'} \supseteq L_{i}$ is also in $S$ , so if $M$ accepts all the words in $L_{i}$ for some $i$ , then $L (M) \supseteq L_{i}$ and thus $L (M) \in S$ , in contradiction. □

Given a non trivial property

S ⊊ R E

, so that

\emptyset \in S

, the language >

L_{S} = {⟨ M ⟩ ∣ L (M) \in S}

> is not recursively-enumerable, that is,

L_{S} \notin R E

CircuitSat ∈ DTIME(2n) consequences

P/poly =∪c∈NSIZE(nc) consequences

Prove that PP is closed under complement

Rice extended(not the version we saw)

CircuitSat $\in$ DTIME $(2^{n})$ consequences

P/poly $= \cup_{c \in N}$ SIZE $(n^{c})$ consequences