## cs701 final term solved papers

** **

**CS701: Total Marks: 4 x 15 = 60 Time: 2Hrs**

**Date: 01-Sep-2018: 5:00PM : Saturday**

**
**

**Q.1: Let ADD = {<x, y, z> | x, y, z >0 are binary integers and x + y =z}. Show that ADD ϵ LSPACE ?**

**Q.2: SQ:2 Let ALBA = {<M,w> | M is an LBA (Linear Bounded Automaton) that accept input w}. Show that ALBA is PSPACE-complete?**

**Q.3: Say that two Boolean formulas are equivalent if they have the same set of variables and are true on the same set of assignments to those variables. A Boolean formula is minimal if no shorter Boolean formula is equivalent to it. Let MIN-Formula be the collection of minimal Boolean formulas. Show that MIN-FORMULA is in PSPACE.?**

**Q.4: Related to 3COLORS**

** **

**My todays paper of cs701 01-09-18**

**SAAD ZIA·SATURDAY, SEPTEMBER 1, 2018**

** **

**04 descriptive Questions having 15 marks each.**

**Question:1**

**Define CYCLE = {(G)| G is a directed graph that contains a directed cycle}.**

**OR Show that CYCLE-Length problem is NL-Complete where Cycle Length is a problem where a cycle of nodes in a directed graph has at least 3 nodes.**

**Show that CYCLE is NL-Complete?**

** **

**Answer:**

** **

**We reduce PATH to CYCLE. The idea behind the reduction is to modify the PATH problem instance (G, s, t) by adding an edge from t to s in G. If a path exists from s to t in G, a directed cycle will exist in the modified G.**

**However, other cycles may exist in the modified G because they may already be present in G. To handle that problem, we first change G so that it contains no cycles. A leveled directed graph is one where the nodes are divided into groups, A1, A2, . . . , Ak, called levels, and only edges from one level to the next higher level are permitted. Observe that a leveled graph is acyclic.**

**The PATH problem for leveled graphs is still NL-complete, as the following reduction from the unrestricted PATH problem shows. Given a graph G with two nodes s and t, and m nodes in total, produce the leveled graph G´ whose levels are m copies of G’s nodes.**

**Draw an edge from node i at each level to node j in the next level if G contains an edge from i to j. additionally, draw an edge from node i in each level to node i in the next level. Let s´ be the node s in the first level and let t´ be the node t in the last level. Graph G contains a path from s to t iff G´ contains a path from s´ to t´.**

**If we modify G´ by adding an edge from t´ to s´ we obtain a reduction from PATH to CYCLE. The reduction is computationally simple, and its implementation in logspace is routine. Furthermore, a straightforward procedure shows that CYCLE ****∈ NL.**

**Hence CYCLE is NL-complete.**

**
**

**Question:2**

**A subset of nodes of a graph G is Dominating Set if every other node of G is adjacent to some node in the subset. Let DOMINATING-SET = {<G, k>| G has a dominating set with k nodes}. **

**Show that it is NP Complete by giving a reduction from VERTEX-COVER?**

** **

**Question:3**

**Let EQNFA = {<N, N’> | N, N’ are NFAs with the same alphabet and L(N) = L(N’)}. Show that EQNFA Є PSPACE. **

** **

**Answer: **

** **

**First of all convert the N and N’ into non deterministic finite automata then we are able to derive the states of n and N’ prime may reach to s[1….1 +1] then the following no deterministic Turing machine M which tries to guess the alphabet on exactly one of n or N’ accept . Instead of storing the guessed alphabet. The machine M keeps the next bits of the alphabets and forgets about the previous bits of the alphabets. So on guessing the next bits the machine M update the alphabets of the N and N’ may reach after reading the guessed so far. **

**In the other hand if the after guessing some bits of the alphabets the machine M find the exactly one of N and N’ are entered into accepting states. **

**For this computation M run in polynomial space otherwise it fail to halt So in this way N and N’ differ if and only if M( N , N’) has an accepting states for computation branches . **

**So Savitch theorem we approved this **

**NPSPACE = PSPACE = co-NPSPACE and the EQNFA Є PSPACE.**

** **

**Question:4**

** **

**The 3SAT problem consists of conjunction of clauses over n Boolean variables where each clause is dis‐junction of 3 literals. **

**The DOUBLE‐SAT problem takes as input a Boolean formula f, and asks if there are two satisfying assignments for f. Prove that DOUBLE‐SAT is NP complete by reduction from 3‐SAT. **

** **

**Answer: **

** **

**DOUBLE-SAT, like any variant of SAT, is in NP since the truth assignment is the certificate. We can check every clause polynomial time to see if it is satisfied. **

**We now show a reduction from 3-SAT. **

**Given a 3-SAT formula f, we construct a DOUBLE-SAT formula f´ = f ˄ (xk V ¬xk), where xk is a variable not used in f. Clearly this reduction is poly-time. **

**We now show that f has a satisfying assignment iff f´ has two satisfying assignments. **

**⟹If f has a satisfying assignment σ, then f´ has two satisfying assignment, corresponding to (σ, xk = true) and to (σ, xk = false). **

**⇐The clause (xk V ¬xk) can be satisfied with either xk = true or xk = false. **

**In either case, if we have a satisfying assignment σ for f, this ensures DOUBLE-SAT is validated. In same case, 3-SAT is also validated.**

**
**

**STRONGLY-CONNECTED := {G = (V, E) : G is strongly connected directed graph}.**

**Prove that STRONGLY-CONNECTED is NL-complete.**

**Solution Let’s show first that STRONGLY-CONNECTED ****∈ NL. We**

**offer two ways of showing this.**

**proving that STRONGLY-CONNECTED****∈ NL. (From this, since**

**NL = coNL the claim follows). Nondeterministically choose a pair**

**of vertices (s, t) of the input graph and output the decision of PATH**

**on those.**

**iterating over all pairs of vertices: we iterate over all (u, v)****∈ E.**

**We run PATH(G, s, t). If it rejects, we reject. If the iteration was**

**finished without rejecting, we accept.**

**Next, we want to show that STRONGLY-CONNECTED is NL-hard. We**

**do it by reducing PATH to STRONGLY-CONNECTED. Let (G, s, t) be an**

**instance of PATH problem. We construct graph G0 by adding edges so that**

**s has an incoming edge from every other vertex and that t has an outgoing**

**edge to every other vertex. We claim that STRONGLY-CONNECTED(G) ****⇔**

**PATH(G, s, t). Assume there is a path π from s to t in G and consider**

**any two vertices u, v ****∈ G0**

**. Then there is a path u − s − t − v Conversely,**

**assume that there is now path between s and t in graph G. But this also**

**means they are not connected in G0**

**, as all added edges were coming into**

**s and going out of t, hence G0**

**is not connected.**

** **

**Paper CS701 Date: 03-09-2018**

**Time: 08:00 to 10:00 AM Total Marks: 4 x 15 = 60**

** **

**Q.1**

**Prove that NEAR-TAUT is NP-Complete by reducing SAT to it.**

**Q.2**

**Prove that STRONGLY-CONNECTED is NL-Complete.**

**Q.3**

**There was given a Boolean Formula Monotone and we have to prove that k-MON.2SAT is NP-Complete**

**Q.4**

**Prove that 3COLOR is N-Complete by using Graph.**

** **

**Cs701 sep 2018**

**Show that half-clique is in NP****Nested language is in P****3SAT**

**
**

**Today 701 paper 11am 5 sep2018**

**HALF CLIQUE**

**MAX CLIQUE**

**GEOGRAPHIC GAME**

**NAT WALA THA**

** **

**701…11 am… 5 sep 2018**

** **

**3COLOR is NP-complete**

**Monotone 2CNF**

**Strongly-connected**

**ALBA is PSPACE-complete**

** **

**Today 701 nim game , montone 2 cnf, minfirmula pspace, 3sat to sat**

** **

**My CS701 Paper (Sat 8-9-2018 8:00 am)**

**(1) Prove that Isomorphic graph is NP complete **

**(2) PAL-Add is NP Complete**

**(3) Scheduling related**

**(4) Max Clique is NP Complete**

** **

**cs701 today sep 2018 11 am**

**A coloring graph is an assingment of colors nodes so that no two adjacent nodes are assigne the same color.****Let SET-SPLITTING = {<S,C> | S is finite set and C= c1…..ck……****Let MULT – SAT ={< pi> | pi has at least ten satisfying assignment ….show that MULT SAT is NP comlete.****A dircted graph is srongly connected if every two nodes are conncted by a directed path is each directed . Let Stringly conncted = {<G> | G is stronlg connected graph}**

**show that strongly conncted is NL complete**

**Manage**

**Image may contain: text**

** **

** **

** **

** **

**Today my papr of cs701 at 4.30**

**Half clique**

**Parenthese**

**Strongly connected graph is nl complete**

**Subset of graph wala**

** **

** **

**CS 701 28 feb 10:30 am**

**Show that STRONGLY-CONNECTED is NL-Complete. **

**Show that MIN-FORMULA is in PSPACE . **

**Show CNF3 is NP-Complete.**

**Show A is NP-Complete**

** **

**Today my paper of CS701**

**nim game**

**2.CNF3 in np-complete**

**3.Dominating….**

**4.Max-Clique..finding largest ..**

** **

**today CS701 paper questions**

**1- 3 CNF in np complete **

**2- nim game **

**3- strongly connected graph is in NL..**

**4- min formula wala**

** **

**CS701 23/2/18**

**Q.1. Final Exam Schedule**

**Q.2. Max-Clique**

**Q.3. PAL-ADD belongs to LSPACE**

**Q.4. ISO belongs to NP**

** **

**Cs 701 Paper 23-2-2018**

**1) Exam Schedule**

**2)Nim game**

**3) Max clique**

**4) double sat is reducible to 3 Sat (given a boolean formula f)**

** **

**Final 701 today 22feb18**

**ALBA NPSPACE **

**GG GAME **

**Boolean Formulas Equivanlency **

**A belongs to NP**

**
**

** **

**MY cs701 paper **

**1.**

**Question: Prove that PAL-ADD is in Space| Show that PAL-ADD Є LSPACE?**

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

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

**2.**

**Question: Two Boolean formulas and are equivalent if for every truth assignment p,**

**p satisfies iff p satisfies (that is, the two formulas have identical sets of satisfying**

**assignments). A Boolean formula is minimal if there is no formula that is shorter**

**than in length and is equivalent to. Let MIN-FORM be the language consisting of**

**minimal Boolean formulas. Prove the following: if P=NP then MIN-FORM is in P.**

**3.**

**Question: Question: Show that 3COLOR is NP-Complete?**

**4.**

**Question: Let ᶲ be a 3CNF-Formula. An ≠-assignment to the variables of ᶲ…**

**a: Show that negation of any ≠-assignment to ᶲ is also an ≠-assignment**

**b: Let ≠ SAT be the collection of 3-CNF formulas that have an ≠-assignment, show**

**that we obtain a polynomial time reduction from 3SAT to ≠ SAT by replacing each**

**clause ci : (y1 ˅ y2 ˅ y3) with two clauses: (y1 ˅ y2 ˅ zi) and (****𝒛𝒊 ˅ y3 ˅ b), where zi is**

**new variable…**

**c: Conclude that ≠ SAT is NP-Complete**

** **

** **

**CS701 My Paper 19-02-2018**

**Q1: Let ALBA = {<M,w> | M is an LBA (Linear Bounded Automaton) that accepts input w}. Show that ALBA is PSPACE-complete. **

**Q2: Show that if P=NP ,then every language A belong to P, except A= and A= * is NP-Complete. **

**Q3: For a CNF-formula with m variable and c clauses that you can construction polynomial time an NFA with O(cm) states that accepts all non-satisfying assignments, represented as Boolean strings of length m **

**Q4: A directed Graph is STRONGLY-CONNECTED of every two nodes are connected by a directed graph in each direction. Let STRONGLY-CONNECTED = {<G>|G is strongly connected graph}. Show that STRONGLY-CONNECTED is NP-Complete.**

** **

** **

**
**

**CS701:20-02-2018:Tuesday:4:30PM**

**Q:1: Let ALBA = {<M,w> | M is an LBA (Linear Bounded Automaton) that**

**accepts input w}. Show that ALBA is PSPACE-complete?**

**Q2: The game of Nim is played with a collection of piles of sticks. In one move a**

**player may remove any nonzero number of sticks from a single pile. The players**

**alternately take turns making moves. The player who removes the very last stick**

**loses. Say that we have a game position in Nim with k piles containing s1, …, sk**

**sticks. Call the position balanced if, when each of the numbers si is written in binary**

**and the binary numbers are written as rows of a matrix aligned at the low order**

**bits, each column of bits contains an even number of 1s. Prove the following two**

**facts.**

**(a):Starting in an unbalanced position, a single move exists that changes the**

**position into a balanced one.**

**(b):Starting in a balanced position, every single move changes the position into anunbalanced one.**

**Q.3: Let G represents an undirected graph. Let LPATH={<G,a,b,k>|G contains a simple path of length at most k from a to b}**

**Show that LPATH is NP-Complete. You may assume that NP-Completeness of**

**UHAMPATH, the Hamiltonian path problem for undirected graph?**

**Q.4: Related to NAT-SAT? (Note:Sorry! I have no idea about it)**

** **

**My Today paper cs701- 10:30-18-2-2018**

**1- scheduling list of final exams **

**2- multi-SAT is NP-complete**

**3- Nim-Game **

**4- show that we obtain from 3SAT to SAT in 3CNF es trha ka tha..**

** **

**Cs701**

**Prove that LPATH is NP-complete**

**Prove that Eq-NFA is in Pspace**

**Show winning strategy for player1 or player2 in a given graph**

**Prove that 2Sat in CNF form is NP-complete for true values of k variables**

** **

**
**

**701 18/02/2018 10:30**

**Q:1: Prove LPATH Is NP Complete assuming UHAMPAT is NP COMPLETE**

**Q.2: A={M, x, #power2 } Prove that A is NP Complete**

**Q.3: prove that FORMULA-MIN IS in PSPACE**

** **

** **

**cs701- 10:30-18-2-2018**

**1- scheduling list of final exams**

**2- multi-SAT is NP-complete**

**3- Nim-Game**

**4- show that we obtain from 3SAT to SAT in 3CNF es trha ka tha..**

**Q4. NIM GAME is pile of sticks s1…sk sucht that players who picks last one is lost..Prove that if its unbalanced then there exists a stick if removed NIM gets balanced…also proved that if its balanced removing a stick will make unbalance**

** **

** **

**cs701 today paper**

**1.cnf3 SAt**

**2.Lspace**

**3.NP**

**4.SAT is Np còmplete**

** **

**CS 701_ final paper_19th_Feb_2018**

**There was 4 questions of 15marks**

**1- Let ADD={<x,y,z> I x,y,z >0 are binary integers and x+y = z } Show that ADD belongs to LSPACE.**

**2- Show that HALF-Clique is NP complete**

**3- NEAR-TAUT is NP Complete.**

**4- A= {M, X, #^2} Prove that A is NP complete.**

**This is all about my paper… Keep me remember in your prayers….**

** **

** **

**cs701- 10:30-18-2-2018**

**1- scheduling list of final exams**

**2- multi-SAT is NP-complete**

**3- Nim-Game**

**4- show that we obtain from 3SAT to SAT in 3CNF es trha ka tha..**

** **

**
**

** **

**Current CS 701 paper 19/02/2018 at 1030**

**Q1. The 3 SAT problem consists of conjunction of clauses over n Boolean variables where each clause is dis-junction of 3 literals.**

**The DOUBLE-SAT problem takes as input a Boolean formula f, and asks if there are two satisfying assignments for f. Prove that DOUBLE-SAT is NP complete by reduction from 3-SAT.**

**Q2 Show that MULT-SAT is NP-complete**

**Q3 2 CNF is NP complete**

**Q4 2. Let PAL-ADD = {<x, y> | x, y >0 are binary integers where x + y is an integer whose binary representation is palindrome}. Show that PAL-ADD ? LSPACE.**

** **

** **

**Today cs 701 **

**Total 4 qstn of 15 marks**

**almost qstn pastpaper m sy thay**

**1) Scheduling wala tha**

**2) Directed graph stongly-connected wala**

**3) multi -sat is NP complete**

**and last qstn b isi trha ka tha kch cnf3 fi wala ab mind m nh**

** **

** **

**CS701 **

**Q:1: Prove LPATH Is NP Complete assuming UHAMPAT is NP COMPLETE**

**Q.2: A={M, x, power2 } Prove that A is NP Complete**

**Q.3: prove that FORMULA-MIN IS in PSPACE**

**Q4. NIM GAME is pile of sticks s1…sk such that players who pick last one is lost..Prove that if it is unbalanced then there exists a stick if removed NIM gets balanced…also prove that if it is balanced removing a stick will make unbalance**

** **

**CS701**

**Total 4 Question**

**Question1: Let ALBA = {<M,w> | M is an LBA (Linear Bounded Automaton) that accepts**

**input w}. Show that ALBA is PSPACE-complete.**

**Question2: Call graphs G and H isomorphic if the nodes of G may be reordered so**

**that it is identical to H. Let ISO = {(G, H) | G and H are isomorphic graphs}.**

**Show that ISO ? NP.**

**Question3: Let A = {<M,x,#t> | NTM, M accepts input x within t steps on at least one branch}. Show that A is NP Complete.**

**Question4: Let EQNFA = {<N, N’> | N, N’ are NFAs with the same alphabet and L(N) = L(N’)}. Show that EQNFA ? PSPACE.**

** **

** **

**701 4 pm**

**Near taut Np cmplt**

**Double sat NP**

**Geography game…**

**Eik ke statment yaaad nahi..**

** **

**CS 701 Today 10:30**

**Q1: Show that 3Color is in NP-Complete**

**Q2: Show that k-Mon-Sat is in NP-Complete**

**Q3: Min Formula € PSPACE**

**Q4: Cycle Length is in NL-Complete**

** **

**
**

**701 today’s paper 2:00pm**

**1- Nims game**

**2- CNF3**

**3- MAX-CLINQUE**

**4- NAT-SAT**

** **

**Cs701 Today at 10:30**

**CNF3 is in NP****ADD is in L****Snario based…..boolean formula is satisfiable in L****EQNFA**

** **

** **

**Cs701**

**Prove that LPATH is NP-complete**

**Prove that Eq-NFA is in Pspace**

**Show winning strategy for player1 or player2 in a given graph**

**Prove that 2Sat in CNF form is NP-complete for true values of k variables**

** **

** **

**Cs701 8:00 am**

**ISO belongs to NP****Near-Taut is NP****Geographical problem**

** **

**Cs701**

**Prove that LPATH is NP-complete**

**Prove that Eq-NFA is in Pspace**

**Show winning strategy for player1 or player2 in a given graph**

**Prove that 2Sat in CNF form is NP-complete for true values of k variables**

** **

** **

**Cs701 today at 4pm**

**Show ALBA is PSPACE complete**

**Show that half clique is NP complete**

**Hamilton cycle is NL complete**

**Ak p complete wala tha**

**Total 4 qs**

**Each q has 15 marks**

**2 hours k tha no mcq’s**

** **

**Cs701 today paper 1. Half clique np complete. 2. Schedule 3. LP Complete 4. Yad ni**

** **

**
**

** **

**opied**

**Today cs 701 **

**Total 4 qstn of 15 marks**

**almost qstn pastpaper m sy thay**

**1) Scheduling wala tha**

**2) Directed graph stongly-connected wala**

**3) multi -sat is NP complete**

**and last qstn b isi trha ka tha kch cnf3 fi wala ab mind m nh**

** **

** **

** **

** **

**CS 701 (18-02-18) 10:30 Q1: Show that 3Color is in NP-Complete Q2: Show that k-Mon-Sat is in NP-Complete Q3: Min Formula € PSPACE Q4: Cycle Length is in NL-Complete**

**Double sat is np complete,cnf ,parentasis**

**Today cs 701 **

**Total 4 qstn of 15 marks**

**almost qstn pastpaper m sy thay**

**1) Scheduling wala tha**

**2) Directed graph stongly-connected wala**

**3) multi -sat is NP complete**

**and last qstn b isi trha ka tha kch cnf3 fi wala ab mind m nh**

**701 18/02/2018 10:30**

**Q:1: Prove LPATH Is NP Complete assuming UHAMPAT is NP COMPLETE**

**Q.2: A={M, x, #power2 } Prove that A is NP Complete**

**Q.3: prove that FORMULA-MIN IS in PSPACE**

**Q4. NIM GAME is pile of sticks s1…sk sucht that players who picks last one is lost..Prove that if its unbalanced then there exists a stick if removed NIM gets balanced…also proved that if its balanced removing a stick will make unbalance**

**701 my finl papr. dijskta algo . **

**A problem is NP Complete . DFS . Huffman encoding . Z(+ ,*) is integer . Knap bracktracing algo**

** **

** **

**
**

**today paper 701 10:30**

**let A={<M,x,# power t> | NTM, M accepts input x within t steps on at least one branch } Show that A is NP Complete.**

**let EQ(NFA )= {<N,N’> are NAFs with same alpjabet and L(N)=L(N;))} show EQ(nfa) E pspace.**

**3-sat problem reducible to double sat problem**

**let ADD={x,y,z|x,y,z>0 are binary integer and x+y=z}. show that ADD E L.**

** **