# cs701 final term solved papers ## 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

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?

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.

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.

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

1. Show that half-clique is in NP
2. Nested language is in P
3. 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

(3) Scheduling related

(4) Max Clique is NP Complete

cs701 today sep 2018 11 am

1. A coloring graph is an assingment of colors nodes so that no two adjacent nodes are assigne the same color.
2. Let SET-SPLITTING = {<S,C> | S is finite set and C= c1…..ck……
3. Let MULT – SAT ={< pi> | pi has at least ten satisfying assignment ….show that MULT SAT is NP comlete.
4. 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

1. 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.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…

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

1. CNF3 is in NP
3. Snario based…..boolean formula is satisfiable in L
4. 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

1. ISO belongs to NP
2. Near-Taut is NP
3. 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.