Dept. of Computer Science
University of Toronto
Assignment # 4
(Due Apr 9, 3:00 pm)
CSC463H1
Winter 2021
Worth: 15%
1. [20 marks]
Let EXP =
⋃
k T IME(2
nk ) and NEXP =
⋃
kNT IME(2
nk ) be the classes of languages decidable by
respectively deterministic and nondeterministic Turing machines with running time O(2nk ) for some
constant k.
Both P ?= NP and EXP ?= NEXP are open questions. However, it is known that if P = NP , then
EXP =NEXP . Prove this fact!
Hint: For a language A ∈NT IME(2nk ), consider the “padded” language
A′ = {x#2|x|k | x ∈ A},
where x#2
|x|k
is the string formed by x followed by 2|x|k many #’s.
2. [20 marks]
The (m,n,k)-game is a game that generalizes the familiar game of Tic-Tac-Toe. There are two players
— Player X and Player O. Player X plays first. Each player takes turns to place their marker “X”
or “O” on an m×n grid G. The first player to get k markers consecutively in a row — horizontally,
vertically, or diagonally — wins.
Let GT be the following language:
GT = {〈m,n,k〉 | Player X has a winning strategy on the (m,n,k)-game}.
Show that GT is in P SPACE.
3. [40 marks]
The purpose of this problem is to show that 2-Sat is NL-complete.
Given a 2-CNF formula ϕ, we associate a directed graph Gϕ = (V ,E), where V is the set of all literals
` such that either ` or ¬` occurs in ϕ, and for every clause (`1 ∨ `2) in ϕ we put the directed edges
(¬`1, `2) and (¬`2, `1) in E.
(The idea is that if a truth assignment τ satisfies the clause (`1 ∨ `2), then if τ makes `1 False, then `2
must be True; and if τ makes `2 False, then `1 must be True.)
(a) [10 marks] Suppose that `1 and `2 are two literals such that there is a directed path from `1 to
`2 in Gϕ. Then show that there is a directed path from ¬`2 to ¬`1 in Gϕ. Also, show that every
truth assignment to ϕ which satisfies ϕ and `1 also satisfies `2.
(b) [10 marks] Use part (a) to prove that ϕ is unsatisfiable iff Gϕ has a directed cycle which includes
both x and ¬x for some variable x.
(c) [20 marks] Use the previous observations to show that 2-Sat is NL-complete. You may use the
fact that Path is NL-complete.
University of Toronto Department of Computer Science Page 1 of 1

欢迎咨询51作业君