Computational Complexity

Definition 1. We say that a class C of propositional formulas is nice if it has the following property:

• There is a polynomial-time algorithm that—given a formula ϕ ∈ C, a positive integer k ∈ N, and a partial truth assignment α to (some of) the variables in Var(ϕ)—correctly decides if there exists a truth assignment β : Var(ϕ) → {0, 1} that (i) extends α, (ii) satisfies ϕ, and (iii) that sets at least k variables among Var(ϕ) to true.

Exercise 1 (6pt; a: 1
1
2
pt, b: 1
1
2
pt, c: 1
1
2
pt, d: 1
1
2
pt).

(a) Show that if the class of all 2CNF formulas is nice, then P = NP.
(b) Specify a class C of propositional formulas that is nice, and such that for every (arbitrary) propositional formula ϕ, there exists some ψ ∈ C that is logically equivalent to ϕ. Prove that this is the case.

In the rest of this exercise, we will show that the class of all propositional 3CNF formulas does not polynomial-size compile into any nice class C, unless the PH collapses.

Definition 2. Let C1, C2 be two classes of propositional formulas. The class C1 polynomial-size compiles into C2 if there exists a polynomial p : N → N such that for every ϕ ∈ C1 there exists a f(ϕ) ∈ C2 that is logically equivalent to ϕ and for which holds |f(ϕ)| ≤ p(|ϕ|). Note that there are no requirements on the running time to compute f(ϕ).

Consider the following family {ϕn}n∈N of propositional formulas, where each ϕn contains variables
in { xi
, xi,j | 1 ≤ i < j ≤ n }, and is defined as follows:
ϕn =
^
1≤i<j≤n
(¬xi,j ∨ ¬xi ∨ ¬xj )

(c) Let C be a class of propositional formulas that is nice. Suppose that there exists a polynomial p : N → N and a family {ψn}n∈N of propositional formulas such that for each n ∈ N: (i) ψn ∈ C, (ii) ψn is logically equivalent to ϕn, and (iii) |ψn| ≤ p(n).

Show that then there exists a polynomial-time algorithm that—given a graph G = (V, E) with n vertices, an integer k ∈ N, and the formula ψn—decides if G has a clique of size k.

(d) Show that if 3CNF polynomial-size compiles into a class C that is nice, then PH = Σp2.
Hint: use the answer that you gave for (c).
1
Exercise 2 (3pt; a: 1pt, b: 2pt). Consider the following problem:
Restricted-Positive-1-in-3-SAT
Input: A propositional formula ϕ in 3CNF, where each clause contains only positive literals, and where each variable x ∈ Var(ϕ) occurs at most 3 times in ϕ.

Question: Does there exist a truth assignment α : Var(ϕ) → {0, 1} such that α makes exactly one (positive) literal true in each clause of ϕ?

Do the following:
(a) Prove that Restricted-Positive-1-in-3-SAT is solvable in time O(1.45n)· p(|ϕ|), for some polynomial p : N → N, where n is the number of variables in ϕ.
(b) Prove that if the ETH is true, then Restricted-Positive-1-in-3-SAT is not solvable in time 2o(n)
,
where n is the number of variables in ϕ.
Exercise 3 (1pt). Consider the following game, played on an m × m board where each of the positions
on the board may be occupied by (i) a tile marked O, (ii) a tile marked X, or (iii) no tile at all. In other
words, there are tiles marked with O and X, and in each position on the board there is at most one tile.
The game is played by a single player, and for each of the m columns, this player has to play one of
the following moves: (1) remove all tiles marked O from positions in this column, (2) remove all tiles
marked X from positions in this column. The player wins the game if (a) for each of the columns she
made a move, and after these moves (b) for each of the m rows, there is at least one tile remaining in
this row.
Then consider the following problem, related to the game described above.
Game-can-be-won
Instance: An m × m board of the game, where each of the positions is occupied by a tile
marked with O, a tile marked with X, or no tile.
Question: Can the player win the game starting from this board position?
Show that the problem Game-can-be-won is complete for some complexity class K ∈ {NP, coNP, Σ
p
2
, Π
p
2
,
PSPACE}.
2

Click here for further assistance on this assignment