Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 262: Computational Complexity Homework 5
1. Let f be a family of one-way permutations, and let b = {bn} be a hard bit for f −1 . Assume that both f and b are computable in polynomial time. Use f and b to describe a language L for which L ∈ (NP ∩ coNP) − BPP. (This shows that the assumption we used to construct the BMY pseudo-random generator placed a priori bounds on the power of BPP – it presumed that BPP was not powerful enough to simulate NP ∩ coNP.)
2. Consider the following problem. An instance of the problem is a pair (Φ, 1 B), where Φ is a Boolean expression in disjunctive normal form and B is an integer. (Φ, 1 B) is in the language if there is a Boolean expression that is equivalent to Φ that is in conjunctive normal form and has at most B clauses.
Recall that a Boolean expression is in disjunctive normal form, if it is the disjunction of a set of terms, where each term is a conjunction of literals. A Boolean expression is in conjunctive normal form, if it is the conjunction of a set of clauses, where each clause is a disjunction of literals. Show that the language described in in Σ2.
3. Show that if NP ⊆ TIME(n log n ), then PH ⊆ ∪k≥1TIME(n logk n ).
4. Recall the definition of QSAT: QSAT = {Φ(x1, . . . , xn) | ∃x1∀x2 . . . ∀xnΦ(x1, . . . , xn) = 1},
where Φ is a 3-CNF formula. Show that P QSAT = NP QSAT . 1