代做assignment – CSC 463H

CSC 463H

``````Dept. of Computer Science
University of Toronto
``````

assignment # 4

CSC 463H

``````Winter 2021
``````

Worth: 15%

1. [20 marks] Let EXP = kTIME (2 nk ) and NEXP = kNTIME (2 nk ) be the classes of languages decidable by respectively deterministic and nondeterministic Turing machines with running timeO(2 nk ) for some constant k. BothP=?NPand EXP =? NEXP are open questions. However, it is known that ifP=NP, then EXP = NEXP. Prove this fact! Hint: For a language A NTIME (2 nk ), 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.
``````
1. [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 PSPACE.
2. [40 marks] The purpose of this problem is to show that 2-Satis NL -complete. Given a2- 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 beTrue; and if __ makes _` 2 False, then `_ 1 must beTrue.) (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-Satis NL -complete. You may use the fact thatPathis NL -complete.
``````University of Toronto Department of Computer Science Page 1 of 1
``````