代做assignment – CSC 463H

2021-04-20

CSC 463H

代做assignment – 这是值得参考的assignment代写的题目

ass代做 assignment代写 代写assignment

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