HW3 Solutions Page

1. Suppose we have a super proof system computed by TM `M(x,y)` where `q` is the polynomial that bounds proof size. Then `M` operates in polynomial time in `(x,y)` and for any tautology `y` there is a `x` where `|x| \leq q(|y|)` such that `M(x,y)` outputs 1. If `y` is not a tautology no `x` makes `M` output `1` on input `(x,y)`. Hence, the language TAUT can be expressed as `{y| exists x \in {0,1}^{q(|y|)}(M(x,y) = 1)}`. I.e., as an NP-language. Since TAUT is coNP-complete any language in coNP can be reduced to TAUT in p-time and so can in turn be expressed as a NP-language using our super proof system characterization of TAUT.
2. A given 5-SAT clause chosen randomly by the process from class will have at most a 31/32 chance of being satisfied by any given assignment. As we chose clauses independently of each other, the odds an `m` clause formula will be satisfied by a particular assignment is `(31/32)^m`. The odds that some assignment on `n` variable would make an `m` clause formula 1 is less than `2^n(31/32)^m`. This will converge to 0 as `n -> infty` if `(2^n(31/32)^m)^{1/n} < 1`. We note
   `(2^n(31/31)^m)^{1/n} = 2 cdot (31/32)^{m/n}`
   and solving the equation `2 cdot (31/31)^{m/n} = 1` implies a value `m/n` of `- (ln2)/ln (31/32) approx 21.83`.

3. Consider the Turing Machine `D` which computes: "On input `x`, run for `g(|x|)` steps the UTM `U` that simulates the execution of `M_x` on `x`. If `U` outputs some bit `b in {0, 1}` in this time, then output the opposite answer. Else output `0`." Recall `M_x` is the machine represented by the string `x`.

   Given its definition, `D` halts after at most `g(|x|)` steps. So it is decided within time `g(n)`. Let `L` be the language of `D`. We claim that `L !in DTIME(f(n))`. For contradiction's sake, assume there is some TM `M` such that TM `M`, given any input `x \in{0, 1}^star`, halts within `f(|x|)` steps and outputs `D(x)`.

   The time to simulate `M` by the UTM `U` on every input `x` is at most `c'f(|x|)log f(|x|)` for some number `c'` that depends on the alphabet size and number of tapes and states of `M`, but is independent of `|x|`. Since `f(n) log f(n) = o(g(n))`, there is some number `n_0` such that `g(n) > c' f(n) log f(n)` for every `n > n_0`. Let `x` be a string representing `M` whose length is at least `n_0` (such a strings exists since `M` is represented by infinitely many strings). Then `D(x)` will obtain `b=M(x)` within `g(|x|)` steps, but by the definition of `D`, we have `D(x) = 1 -b ne M(x)`. Thus, giving a contradiction.

4. To show `TAUT^A` is `coNP^A`-complete, we need to show that it is in `coNP^A` and then it is p-time hard for `coNP^A`. To see `TAUT^A` is in `coNP^A`, we first that a binary string can be used to encode a true assignment for an instance of `TAUT^A` where we view the `i`th bit of the string as saying whether or not the `i`th variable is true or false. An instance of `x` of `TAUT^A` can make use of at most `n=|x|` variables and we assume these variables are number `1, ..., n`. We can then write `TAUT^A` as `{y| \forall x in {0,1}^{|y|} M(x,y)=1}`. Here `M` operates as a TM version of the following pseudo-code:

   On input x,y:
   Check if `y` is an encoding of a collection of CNF clauses, if not, it outputs 1 and halts. (O(|y|) time to do this)
   for each clause C: //(fewer than |y| many)
       flag := false;
       for each literal L in clause C: // (fewer than |y| many)
           if L is a non-A literal and is 1 according to x:
               flag := true;
               break;
           else if L is of the form A or not A: 
               delete and rewind oracle tape; // fewer than |y| steps)
               for each sub_literal L' in A: // (fewer than |y| many)
                   lookup its value in x copy it to the oracle tape
                   move right on oracle tape;
               enter oracle query state;  
               if oracle output is 1 and L is of form A:
                   flag := true;
                   break;
               if oracle output is 0 and L is of form not A: 
                   flag := true;
                   break; 
           if flag == false:
               output 0;
               halt;
   output 1;
   halt;                  
   

   So `M` makes use of triply-nested loops over fewer than |y| items, where each statement in the loops takes at most `O(|y|)` time to process. So the whole algorithm is `O(|y|^4)`, hence, in `P^A`.

   To see `TAUT^A` is `coNP^A`-hard, we first argue that it suffices to show `SAT^A` is `NP^A` hard: Suppose `L in coNP^A` and suppose there is a p-time reduction of its complement, `bar{L}`, to `SAT^A`. For every input `x` such a reduction produces a formula `phi_x` that is satisfiable iff `x in bar{L}`. Now consider `\neg phi_x`. If `phi_x` is in CNF, then `not phi_x` won't necessarily be in CNF, however, we can make an equivalent to `not phi_x` `CNF` formula, `bar{phi}_x`, by introducing new variables `c_i` for each clause `C_i` in `phi_x`, and by introducing a variable `z` whose value represent `phi_x`. `c_i iff C_i` can be expressed by taking the conjunction of the clauses `{bar{c_i}} \cup C_i` and `{\bar{l}_{i1},\bar{l}_{i2} ... \bar{l}_{it}, c_i}` where `l_{ij}` are the literals in `C_i` (which may involve `A` or `not A`). We can express `z iff ^^_i c_i` as the set of clauses `{\bar{z}, c_i}` for each `i` together with `{bar{c_1}, ... bar{c}_m, z}`. We define `bar{phi}_x` as the conjunction over clauses for `c_i iff C_i` for each `i`, with `z iff ^^_i c_i`, and with the clause containing just `bar{z}`. From our discussion `bar{phi}_x` has value 1 iff `neg\phi_x` has value 1. Further `bar{phi}_x` is at most quadratic in the size of `not phi_x`. So `bar{phi}_x in mbox(TAUT)^A` iff `x in L`, giving the reduction.

It is in `TAUT^A` iff `x in L`, so this gives a reduction from `L` to `TAUT_A`. So it suffices to show `SAT^A` is hard for `NP^A` to complete the proof. Let `L` be a language in `NP^A` and given a certificate `y in {0,1}^{q(|x|)}` let `M^A(x,y)` be the TM with a read-only input tape, a work tape, and a query tape which decides `L` using oracle A. We assume `M^A` runs for at most `p(|x|)` for some polynomial `p`. We can imagine the computation of `M^A` on input x,y, as being recorded in a tableaux of size p(|x|) many rows for each time step where each row has 3p(|x|) cells recording the contents of each tape square for the three tapes. We use an augmented tape alphabet where underscore indicates the tape head location. Symbols in this alphabet can be encoded with finite-length m, binary strings. We can introduce boolean variables `ts_{ijk}` to hold the value of the `k`th bit of the encoding of the tape symbol in location `j` of the three tapes concatenated at time step i of the computation of `M^A` on `(x,y)`. On input `x`, our reduction computes a CNF formula F(x,y A), which consists of the conjunction of CNF formulas `Init(x,y, t_{111}, ... t_{1(3p(|x|))m})`, asserting the first timestep variables are set according to x and y, `^^_{i=1}^{p(|x|)}Next_i(t_{i11}, ... t_{i(3p(|x|))m}, t_{i+111}, ... t_{i+1(3p(|x|))m}, A)`, asserting that for each `i` the `i+1`st row is correctly computed according to `M^?` and `A` from the `i`th row, and `z ^^ Out(z, t_{p(|x|)11}, ... t_{p(|x|)(3p(|x|))m})`, asserting that the final output computed by the machine is `z` and that `z=1`. This formula is satisfiable iff `M^A(x,y)=1` iff `x in L`, completing the hardness proof. Notice the formula for `Next_i` will use `A` literals.

An example oracle set `A` such that `TAUT^A` is not in `P^A` is the oracle from class, we used to separate `NP^A` from `P^A`. If `TAUT^A` were in `P^A` with respect to that oracle then `coNP^A` would be in `P^A` since we just showed `TAUT^A` is `coNP^A` complete. But `P^A` is closed under complement, so this would mean `NP^A` would be contained in `P^A`, contradicting the result from class.

5. In the proof from class, we assumed `P ne NP` and we wanted to show `SAT_H` couldn't be NP-complete. For contradiction, we supposed that `SAT_H` was `NP`-complete. This means there is a reduction `f` from `SAT` to `SAT_H` that runs in `O(n^i)` time for some constant `i`. Since we already know `SAT_H !in P`, the claim from class implies that `H(n)` tends to infinity. Since the reduction works in `O(n^i)` time only, for large enough `n` it must map `SAT` instance of size `n` to `SAT_H` instances of size smaller than `n^(H(N))`. Thus for large enough formula `phi`, the reduction `f` must map it to a string of the type `psi01^(n^(H(|psi|)))` where `psi` is smaller by more than some fixed polynomial factor, say, smaller that `n^(1/3)`. Problem 5 asks us to show the existence of such a reduction yields a simple polynomial time algorithm for `SAT`, contradicting `P ne NP`! Suppose we had a a polynomial time reduction, `f(phi)`, from `SAT` instances of size `n` to `SAT` instances of `n^{1/3}`. Let `phi_0 = phi` denote the original SAT instance, and let `phi_{j+1} = f(phi_j)`. Then `|phi_j| = n/3^j`. Since `f` can be computed in polynomial tme, apply it `log_3 n` times can be done in p-time, and the resulting formula would be of size smaller than some fixed constant number `m`. Checking each of the `2^m` many assignments for `phi_{log_3 n}` could then be done in constant time and tell us whether `phi` was satisifiable. Hence, as the reduction from `phi` to `phi_{log_3 n}` is p-time computable, SAT would be decidable in `p`-time and therefore `P=NP`, contradicting our starting assumption.