P-NP

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 Lc be the complement of L over ∑*. Show that Lc is also in NP.

A
Theory Explanation.
Question 2

Assuming P ≠ NP, which of the following is TRUE?

A
NP-complete = NP
B
NP-complete ∩ P = ∅
C
NP-hard = NP
D
P = NP-complete
Question 2 Explanation: 
Note: Out of syllabus.
The definition of NP-complete is,
A decision problem p is NP-complete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
Question 3

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
Question 3 Explanation: 
Note: As per Present syllabus, it is not required.
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
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
Question 5 Explanation: 
Note: Out of syllabus.
Question 6

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
Question 6 Explanation: 
SAT → Boolean satisfiability problem & it is a decision problem.
2-SAT and 3-SAT is a NP-complete.
Question 7

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

A
Q1 is in NP, Q2 in NP hard
B
Q1 is in NP, Q2 is NP hard
C
Both Q1 and Q2 are in NP
D
Both Q1 and Q2 are NP hard
Question 7 Explanation: 
3-SAT ⇒ NPC problem
Q1≤p 3-SAT≤p Q2 ≤p ≤p hence → Q1 is in NP
but Q2 is not given in NP
Hence Q2 is in NP-Hard.
Question 8

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

A
B
C
D
Question 8 Explanation: 
The most important open question in complexity theory is whether the P = NP, which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems (since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.
There are 8 questions to complete.

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

Register Now

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