topic - solutions adda

P-NP

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let L^c be the complement of L over ∑*. Show that L^c is also in NP.

A	Theory Explanation.

Theory-of-ComputationP-NPGATE 1995

Question 2

Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions?

A	Π is NP-hard but not NP-complete
B	Π is in NP, but is not NP-complete
C	Π is NP-complete
D	Π is neither NP-hard, nor in NP

AlgorithmsP-NPGATE 2003

Question 2 Explanation:

Note: As per Present syllabus, it is not required.

Question 3

The problems 3-SAT and 2-SAT are

A	both in P
B	both NP complete
C	NP-complete and in P respectively
D	undecidable and NP-complete respectively

AlgorithmsP-NPGATE 2004

Question 3 Explanation:

SAT → Boolean satisfiability problem & it is a decision problem.
2-SAT and 3-SAT is a NP-complete.

Question 4

A problem in NP is NP-complete if

A	It can be reduced to the 3-SAT problem in polynomial time
B	The 3-SAT problem can be reduced to it in polynomial time
C	It can be reduced to any other problem in NP in polynomial time
D	Some problem in NP can be reduced to it in polynomial time

AlgorithmsP-NPGATE 2006-IT

Question 4 Explanation:

A problem is in NP becomes NP-complete if all NP problems can be reduced to it in polynomial time. This is same as reducing any of the NPC problem to it. 3SAT being an NPC problem reducing it to a NP problem would mean that NP problem is NPC.

Question 5

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?

A	If X can be solved in polynomial time, then so can Y
B	X is NP-complete
C	X is NP-hard
D	X is in NP, but not necessarily NP-complete

AlgorithmsP-NPGATE 2008-IT

Question 5 Explanation:

Note: Out of syllabus.

Question 6

Consider the following two problems on undirected graphs:

Which one of the following is TRUE?

A	α is in P and β is NP-complete
B	α is NP-complete and β is in P
C	Both α and β are NP-complete
D	Both α and β are in P

AlgorithmsP-NPGATE 2005

Question 6 Explanation:

Graph independent set decision problem is belongs to NP-complete.

Question 7

Consider two decision problems Q₁, Q₂ such that Q₁ reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q₂. Then which one of following is consistent with the above statement?

A	Q₁ is in NP, Q₂ in NP hard
B	Q₁ is in NP, Q₂ is NP hard
C	Both Q₁ and Q₂ are in NP
D	Both Q₁ and Q₂ are NP hard

Theory-of-ComputationP-NPGATE 2015 [Set-2]Video-Explanation

Question 7 Explanation:

3-SAT ⇒ NPC problem
Q₁≤p 3-SAT≤p Q₂ ≤p ≤p hence → Q1 is in NP
but Q₂ is not given in NP
Hence Q₂ is in NP-Hard.

Question 8

Let π_A be a problem that belongs to the class NP. Then which one of the following is TRUE?

A	There is no polynomial time algorithm for π_A.
B	If π_A can be solved deterministically in polynomial time,then P = NP.
C	If π_A is NP-hard, then it is NP-complete.
D	π_A may be undecidable.

AlgorithmsP-NPGATE 2009

Question 8 Explanation:

Note: Out of syllabus.

There are 8 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access