The Australian National University Semester 1, 2020 Research School of Computer Science Tutorial 11
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 More Complexity Problems
Copyright By PowCoder代写 加微信 powcoder
We define co-NP-Hard and co-NP-Complete in an analogous fashion to NP-Hard and NP-Complete. We say that a problem L is co-NP-hard if for every problem Lco in co-NP, there exists a polytime
reduction from Lco to L, (Lco ≤P L.)
A problem is co-NP-Complete if it is both co-NP and co-NP-Hard.
Given a boolean expression as input, we let TAUT be the problem of deciding if the expression is a tautology, i.e. evaluates to true for all variable assignments.
Prove that TAUT is co-NP-Complete.
Solution. To proceed, we first demonstrate that TAUT is co-NP, by showing the complement is in NP. The complement of TAUT is deciding if a boolean expression E ever has some valuation that makes it false. So, if provided with such a valuation, I can verify that in polynomial time. Hence the complement of TAUT is in NP, and thus TAUT is in co-NP.
Next, we show that the problem UNSAT (given a boolean expression, is it unsatisfiable? (no valuation makes it true)) is co-NP-Hard.
Now, Cook’s theorem gives a polytime transformation from any problem L in NP to SAT, in the sense that we have some function f such that
x ∈ L ⇔ f(x) ∈ SAT
Hence, Cook’s theorem also provides a polytime transformation (exactly the same transformation in fact)
which is the same as
x ̸∈ L ⇔ f(x) ̸∈ SAT
x∈Lc ⇔f(x)∈UNSAT
Now, let Lco be an arbitrary problem in co-NP. There exists a problem L in NP (namely L = Lco) such
that Lc = Lco. Then, by the same polytime reduction from Cook’s theorem, we have that any instance of Lc = Lco can be converted to an instance of UNSAT.
Now, there is a polytime reduction of instances of UNSAT to instances of TAUT, by taking any instance of UNSAT (a boolean expression) and simply negating it. Given a boolean expression E,
E is unsatisfiable ⇔ ¬E is a tautology
as if an expression is unsatisfiable, then it is always false for any valuation, and the negation of that
expression is one that is always true for any valuation, and hence a tautology.
So, we have a polytime reduction from any co-NP problem Lco, to UNSAT, and a polytime reduction from UNSAT to TAUT, giving us a polytime reduction from any co-NP problem Lco to TAUT. Hence TAUT is co-NP-Hard, and therefore co-NP-Complete.
Exercise 2 co-NP
1. Prove that NP = co-NP if and only if there is some NP-Complete problem L such that its comple- ment Lc is also in NP.
Solution. Assume NP = co-NP. Let L be any NP-Complete problem. Then L is in NP. So Lc is in co-NP by definition. So Lc is in NP.
Assume that there exists a NP-Complete problem L such that Lc is in NP. We need to prove NP ⊆ co-NP and co-NP ⊆ NP.
LetK∈NP.ToprovethatK∈co-NP,weneedtoshowthatKc ∈NP.NotethatKc ∈co-NP. Now, by Lemma 1 we have that Lc is co-NP-Complete. So there is a polytime reduction f from Kc to Lc. Lc is in NP, so there is a NDTM M that recognizes Lc. Then there must also be a NTDM M′ that recognizes Kc, as for a string x, M′ emulates the polytime transformation to obtain f(x), and then emulates M with f(x) as input. Since M′ is a polytime NTDM recognizing Kc, this means that Kc ∈ NP, as required.
Let K ∈ co-NP. Prove that K ∈ NP. Note that Kc ∈ NP. Now K polytime reduces under some transformation f to Lc, as Lc is co-NP-Complete. Lc is in NP. So this gives a non-deterministic polytime algorithm to recognize strings x ∈ K, by polytime transforming them to string f(x), and then testing if that string f(x) belongs in Lc (which we can do as Lc is in NP). Hence, K ∈ NP.
Lemma 1: Let L be a NP-Complete problem. Prove that Lc is co-NP-Complete.
Proof: We need to prove that Lc is co-NP and co-NP-Hard.
Clearly, Lc is in co-NP as (Lc)c = L is in NP.
Now, let K be a problem in co-NP. Then Kc is in NP. There exists a polytime transformation f such that
x∈Kc ⇔f(x)∈L as L is NP-Complete. But this is equivalent to
x̸∈Kc ⇔f(x)̸∈L x ∈ K ⇔ f(x) ∈ Lc
so there is a polytime reduction from K to Lc. Since K was an arbitrary co-NP problem, this means that Lc is co-NP-Hard.
2. (hard) Suppose there was a bijective function f : {0, 1}∗ → {0, 1}∗ such that
• |x| = |f(x)| i.e. the length of the output of f is the same as the length of the input • f(x) can be computed in polynomial time with respect to |x|.
• f−1(x) cannot be computed in polynomial time1
Show that the language
L = {(x,y) : f−1(x) < y}
where < is lexicographic order on bitstrings {0, 1}∗ is in (NP ∩ co-NP) \ P. Solution.
Assume for a contradiction that L ∈ P. Let B = {0,1}. Let y ∈ Bn. We assume that B∗ is well ordered, and we define the order on B∗ to be the lexicographical order.
ε < 0 < 1 < 00 < 01 < 10 < 11 < 00 < 000 < 001 < . . .
We want to find the inverse of y under the function f. Now f is bijective, and string length is invariant under application of f, so there are 2n possible candidates for the inverse of y. Trying them all would take more than polynomial time, but we can use the assumption that L ∈ P to help us. Enumerate all possible candidates lexicographically.
b2 = 0n−11
1f is an example of what’s called a one-way function. Examples of suspected one-way functions include cryptographically secure hash functions (like sha-1 or sha-256). It is an open problem if one-way functions actually exist, as their existence would indicate P ̸= NP.
f−1(y) < m?
f−1(y) < 12m? f−1(y) < b2n 43?
Figure 1: Using method of bisection to find the inverse f−1(y) of y.
Choose the middle string m = b2n−1. Is (y,m) ∈ L? If yes, then f−1(y) < m, and we know that the inverse x lies in the range b1 ≤ x < m. If not, then f−1(y) ≥ m and the inverse x lies in between m ≤ x ≤ b2n . We can repeat this method of bisection, each time halving the search space, until we are left with only one possible option for the inverse of y. (See Figure 1).
For b1,b2,...,b2n, we have to ask n many questions of the form “Is f−1(y) < bi?” to narrow it down to one option. The time taken to check if f−1(y) < bi is the same as the run time to verify if (y,bi) ∈ L, which by assumption has runtime O(p(n)). Hence the time taken to compute the inverse of y is O(n·p(n)), which is polynomial time, a contradiction. Hence L ̸∈ P.
Now we can non-deterministically compute f−1(y) in poly-time, by guessing the correct x from the 2n available options, and then verifying that f(x) = y, which takes polynomial time. We can then check if f−1(y) < x, by running through both pairs of digits and comparing which one is bigger with respect to lexicographical ordering, which takes linear time. Hence we can check if (y, x) ∈ L on a non-deterministic TM in O(p(n) + n) time, which is polynomial. Hence L ∈ NP.
ToproveL∈co−NP,proveLc ∈NP.
Lc = {(y,x) : f−1(y) ≥ x}
Same as above, we can non-deterministically guess γ and then verify that f(γ) = y in poly- nomial time, and then check if γ ≥ x in linear time. Hence we can check if (y,x) ∈ Lc on a non-deterministic TM in O(p(n) + n) time, which is polynomial.
∴ L ∈ co − NP
By combining the above, we have that L ∈ (NP ∩ co − NP)\P. Exercise 3 Alternating QBFs
An (alternating quantified boolean formula) is ma quantified boolean formula of the form ∃x1.∀x2.∃x3 . . . ∃xn.φ
where each of the xi’s represents any variable, and φ is a boolean expression.
The alternating quantified Boolean formula problem, or AQBF, is the problem that, given a fully quantified alternating boolean formula, i.e. an alternating quantified boolean formula without free variables, is it equivalent to true?
Show that AQBF is PSPACE-Complete.
Solution. Clearly this restriction is a subset of all QBFs, and so must be PSPACE. To see PSPACE hardness, we reduce from QBF to AQBF.
Given a QBF, we first relabel variables so no two variables under the scope of different quantifiers share the same name.
f−1(y) < m
f−1(y) ≥ m
1m ≤ f−1(y) < m 2
f−1(y) ≥ b2n 43
f−1(y) < m/2
m ≤ f − 1 ( y ) < b 2 n 32
E.g rewrite ∀x.(∃x.x) as ∀x(∃y.y).
We then move all the quantifiers out the front (as increasing the scope of a quantifier doesn’t change the
meaning if it only captures unrelated variables) E.g rewrite ∀x.(∃y.(y ∧ ∃z.z)) as ∀x.∃y.∃z.(y ∧ z).
We insert new dummy variables and quantifiers as required so the quantifiers alternate, as it won’t change the meaning of the expression.
E.g Rewrite the above as
Now, this transformation costs O(n2) for the rewriting of variables, O(n2) to propagate the quantifiers
∃w1∀x.∃y.∀w2.∃z.(y ∧ z).
and O(n2) time to check which variables are not present, and add dummy variables with quantifiers.
This proves the claim, as all transformations preserve truth of quantified boolean formulae.
Exercise 4 REE problem
Show that the problem
REE = {⟨E, F ⟩ | E, F are regular expressions, and L(E) = L(F )}
is in PSPACE. Is it PSPACE complete?
Solution. Given E and F we decide whether their languages are different in NPSPACE. Since PSPACE = co-NPSPACE the result follows.
Note that L(E) ̸= L(F) if there is a string that is at most exponentially long in the symmetric difference.
For the algorithm, we convert E and F to NFA’s (this is polynomial) and then count (in polyspace) to the maximum length of a word for which L(E) and L(F) can differ. At step, we guess an element of the input alphabet, and mark the set(!) of states that the automata for E and F will have visited.
If at any stage, one of the automata accepts the word, and the other doesn’t, we accept.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com