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作业君