**CS701 Theory of Computation1**

In CS701 Theory of Computation we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.

+92 307 41 51 71 8 vuassassins@gmail.com

In CS701 Theory of Computation we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.

*Try your lucky to get discount coupon**1 spin per email**No cheating*

Never

Remind later

No thanks

Show that A is NP-Complete.

2. Prove that Double SAT is NP-Complete (by reducing from 3 SAT)

3. Prove that SET SPLITTING is NP-Complete.

4. Prove Multi SAT is NP-Complete.

5. Show that directed hymoltonian cycle is NP-Complete.

6. Show that half clique is NP-Complete.

7. Let CNF-k = { | ɸ is satisfiable CNF-formula where each variable appears in at most k

places}. Show that CNF3 is NP-Complete.

8. A subset of nodes of a graph is a dominating set if every other node of G is adjacent to

some node in the subset. Let DOMINATING-SET={ | G has a dominating set with k

nodes}. Show that it is NP-Complete by giving a reduction from VERTEX-COVER.

9. Let TRUE-SAT; given Boolean expression E that is true when all the variables are made

true, is there some other truth assignment besides all true that make E true. Show that

TURE-SAT is NP-Complete by reducing SAT to it.

10. Let NEAR TAUT; given Boolean expression E all the variables are made f, is there some

other truth assignment besides all f that make E true. Show that NEAR TAUT is NPComplete by reducing SAT to it.

11. Let NEAR-TAUT: E is a Boolean expression having when at most one true makes it false.

Show that complement of NEAT-TAUT is in NP-Complete using reduction it to SAT.

12. Let G represent and undirected graph. Also let LPATH = {|G contains a simple

path of length k for a to b>}. Show that LPATH is NP complete. You may assume that NP

completeness of UHAMPTH the HAMPATH problem of undirected graph.

13. A directed Graph is STRONGLY-CONNECTED of every two nodes are connected by a

directed graph in each direction. Let STRONGLY-CONNECTED = {|G is strongly

connected graph}. Show that STRONGLY-CONNECTED is NP-Complete.

14. Let A = {|NTM, M accepts input x within t steps on at least one branch}. Show

that A is NP-Complete.

15. Prove cycle- length problem is NL-Complete.

16. Let ADD = { | x, y, z >0 are binary integers and x + y =z}.

Show that ADD ϵ LSPACE.

17. Let PAL-ADD = { | x, y >0 are binary integers where x + y is an integer whose

binary representation is palindrome}. Show that PAL-ADD ϵ LSPACE.

18. Nim game question to prove unbalance and balance

19. See the Questions of Sipser Book 2013 edition 3

Exercises: 7.17, 7.22, 7.28, 7.30, 8.13, 8.19, 8.22, 8.22b, 8.27

20. Winning strategy (q 8.3 )