Introduction
NP and N concepts are commonly asked in competitive exams such as GATE. As a result, it is critical to have a solid understanding of this subject. But don't be concerned about any of it. Ninjas are here to help, and today we'll talk about top NP and N concepts questions.
Questions
1. Let SHAM3 be the problem of locating a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3, and DHAM3 be the problem of determining whether such graphs contain a Hamiltonian cycle. Which of the following statements is correct?
 Both DHAM3 and SHAM3 are NPhard
 SHAM3 is NPhard
 DHAM3 is NPhard

Both DHAM3 and SHAM3 are not NPhard
Answer: (a) Both DHAM3 and SHAM3 are NPhard
Explanation: The problem of determining whether or not a Hamiltonian Cycle exists is NPHard and NPComplete. It is also NPHard to find a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3.
2. Which of the following statements about NPComplete and NPHard problems is correct?
 To demonstrate the NPHardness of problem X, we take a known NPHard problem Y and reduce it to X.
 The circuit satisfiability problem was the first to be proven to be NPcomplete.
 NPcomplete is a subset of NPHard.

All the above.
Answer: (d) All the above.
Explanation: The most challenging problems in the NP set are NPcomplete problems. A decision problem L is NPcomplete if and only if the following conditions are met:
1) L is in NP (Any given solution for NPcomplete problems can be verified quickly, but there is no efficient known solution).
2) In polynomial time, every problem in NP can be reduced to L. (Reduction is defined below).
A problem is NPHard if it follows the abovementioned property 2, but it does not need to follow property 1. As a result, the NPComplete set is a subset of the NPHard set.
Thus answer is All the above.
3. Consider X to be an NPcomplete problem. Then, which of the following statements is TRUE?
 For X, there is no polynomialtime algorithm.
 P = NP if X can be solved deterministically in polynomial time.
 If X is NPhard, it must also be NPcomplete.

X could be indecisive.
Answer: (c) If X is NPhard, it must also be NPcomplete.
Explanation:
(a) is incorrect because the set NP contains both P (Polynomialtime solvable) and NPComplete.
(b) is incorrect because X could belong to P (for the same reason that (A) is incorrect).
(c) is the correct answer because the NPComplete set is the intersection of the NP and NPHard sets.
(d) is incorrect because all NP problems can be solved in a finite number of operations.
4. 3SAT and 2SAT are the problems of
 both in P
 Both NPcomplete
 NPcomplete and in P, respectively

undecidable and NPcomplete, respectively
Answer: (c) NPcomplete and in P, respectively.
Explanation: The Boolean satisfiability problem (SAT) is a decision problem in which the instance is a Boolean expression written only with AND, OR, NOT, variables, and parentheses. The problem is that, given the expression, is there some combination of TRUE and FALSE values assigned to the variables that will make the entire expression true? A propositional logic formula is said to be satisfactory if logical values can be assigned to its variables in such a way that the formula is true.
3SAT and 2SAT are special cases of ksatisfiability (kSAT) or simply satisfiability (SAT), respectively, when each clause contains exactly k = 3 and k = 2 literals.
2SAT is a P, whereas 3SAT is an NPComplete.
5. Ramu and Shyamu have been tasked with demonstrating that a specific problem is NPcomplete. Ramu demonstrates a polynomialtime reduction from the 3SAT problem, while Shyamu demonstrates a polynomialtime reduction from 3SAT. Which of the following conclusions can be drawn from these reductions?
 NPcomplete but not NPhard
 NPhard but not NPcomplete
 NPcomplete?

Neither NPhard nor NPcomplete.
Answer: (c) NPcomplete.
Explanation: It is NPhard because polynomialtime reduction from the 3SAT problem is possible.
It is NPComplete because polynomialtime reduction from 3SAT is possible.
6. Consider the two graph problems below.
 Given a graph, determine whether it contains a cycle that visits each vertex exactly once, with the exception of the first visited vertex, which must be visited again to complete the cycle.
 Given a graph, determine whether it has a cycle that visits each edge exactly once.
Which of the following statements about the above two problems is correct?
 Problem 1 belongs to the NPComplete set, while Problem 2 belongs to the P Complete set.
 Problem 1 belongs to the P set, while Problem 2 belongs to the NPComplete set.
 Both problems are from the P set

Both problems are part of the NPcomplete set.
Answer: (a) Problem 1 belongs to the NPComplete set, while Problem 2 belongs to the P Complete set.
Explanation: The first problem is the Hamiltonian Cycle problem, a wellknown NPComplete problem. The second problem is the Euler Circuit problem, which can be solved in polynomial time.
7. If a problem in NP is NPcomplete, then:
 In polynomial time, it can be reduced to the 3SAT problem
 It is possible to solve the 3SAT problem in polynomial time
 In polynomial time, it can be reduced to any other NP problem.

Some NP problems can be reduced to them in polynomial time.
Answer: (b) It is possible to solve the 3SAT problem in polynomial time.
Explanation: If all NP problems can be reduced to it in polynomial time, a problem in NP becomes NPC. This is the same as reducing any NPC problem to it. Because 3SAT is an NPC problem, reducing it to an NP problem implies that the NP problem is NPC.
8. Let S be an NPcomplete problem, and Q and R be two other problems that are not known to be NPcomplete. Q can be reduced to S in polynomial time, and S can be reduced to R in polynomial time. Which one of the following statements is true.
 R is NPcomplete
 R is NPhard
 Q is NPcomplete

Q is NPhard
Answer: (b) R is NPhard.
Explanation:
(a) False because R does not exist in NP. An NPComplete problem must be NP and NPhard.
(b) True because an NPComplete problem S is polynomialtime educable to R.
(c) False because Q does not exist in NP.
(d) False because there is no NPcomplete polynomialtime problem. Q is Turingreducible.
9. Given the following assertions:
S1: Every language that is contextsensitive. L is a recursive function.
S2: There is a noncontextsensitive recursive language.
Which of these statements is correct?
 Only S1 is correct
 Only S2 is correct
 Both S1 and S2 are not correct

Both S1 and S2 are correct
Answer: (d) Both S1 and S2 are correct.
Explanation: Because CSL languages are a subset of recursive languages, (S1) is the correct answer.
Furthermore, Recursive languages are the superset of CSL, but not every Recursive language is CSL. As a result, (S2) is also correct.
Option (d) is the correct answer.
10. Y is NPcomplete for problem X, and X reduces to Y in polynomial time for problem Y. Which of the following statements is TRUE?
 If X can be solved in polynomial time, then so can Y
 X is NPcomplete
 X is NPhard

X is in NP, but not necessarily NPcomplete
Answer: (d) X is in NP, but not necessarily NPcomplete.
Explanation:
1st Theorem
When a given Hard Problem (NPC, NPH, and Undecidable Problems) is reduced in polynomial time to an unknown problem, the unknown problem also becomes Hard.
Case No. 1 When an NPC(NPComplete) problem is reduced to an unknown problem, the unknown problem is transformed into an NPH (NPHard).
Case 2: When an NPH(NPHard) problem is reduced to an unknown problem, the unknown problem becomes an NPH (NPHard).
Case â€“ 3 When an undecidable problem is reduced to an unknown problem, the unknown problem becomes undecidable as well.
Remember that for this theorem, Hard problems must be converted but not the other way around.
2nd Theorem
When an unknown problem is reduced in polynomial time to an Easy problem (P or NP), the unknown problem also becomes easy.
Case No. 1 When an unknown problem is reduced to a Ptype problem, the unknown problem is also reduced to a Ptype problem.
Case 2: When an unknown problem is reduced to an NP type problem, the unknown problem becomes NP as well.
Remember that in order for this theorem to work, unknown problems must be converted, not the other way around.
In the given question, X, an unknown problem, is reduced to NPC in polynomial time, so Theorem â€“ 1 does not apply. However, because all NPC problems are also NP, we can say that X is being reduced to a known NP problem, allowing Theorem â€“ 2 to apply and X to be NP. To make it NPC, we must first prove that it is NPH, which is not the case because Y is not reduced to X.
11. Assume you discover a polynomialtime algorithm for computing the largest clique in a graph. In this scenario, which of the following Venn diagrams of the complexity classes P, NP, and NPComplete is correct? (NPC)?
Answer: (d)
Explanation: The problem of the clique is NPcomplete. If one NPcomplete problem can be solved in polynomial time, then all NPcomplete problems can be solved in polynomial time. As a result, the NPC set equals P.
12. Which of the following statements is true?
(1) In P, the problem of determining whether a cycle exists in an undirected graph is addressed.
(2) Determining whether a cycle exists in an undirected graph is an NP problem.
(3) If problem A is NPComplete, a nondeterministic polynomialtime algorithm for solving it exists.
 1, 2 and 3
 1 and 3
 2 and 3

1 and 2
Answer: (a) 1, 2 and 3
Explanation:
Explanation: 1 is correct because DFS can detect cycles in polynomial time (See this).
P is a subset of NP, so 2 is true.
3 is correct because NPcomplete is a subset of NP, and NP denotes the existence of a nondeterministic polynomialtime solution.
13. Which of the following statements is true
1. The problem of determining whether an undirected graph has a cycle is in P.
2. Determining whether a cycle exists in an undirected graph is an NP problem.
3. If problem A is NPComplete, it can be solved using a nondeterministic polynomialtime algorithm.
 1, 2 and 3
 1 and 2 only
 2 and 3 only
 1 and 3 only
Answer: (c) NPcomplete and in P, respectively.
Explanation: We can either use BFS or DFS to find whether there is a cycle in an undirected graph. For example, see DFS implementation. The time complexity is O(V+E) which is polynomial.
14. Consider the problem of decisionmaking. 2CNFSAT's definition is as follows:
 NPComplete.
 Solvable in polynomial time by reduction to directed graph reachability.
 Solvable in the constant time since any input instance is satisfiable.

NPhard, but not NPcomplete.
Answer: (b) Solvable in polynomial time by reduction to directed graph reachability.
Explanation: 2CNFSAT can be reduced to a problem with strongly connected components. A polynomialtime solution exists for the strongly connected component. As a result, 2CNFSAT can be solved in polynomial time.
15. Consider the following two undirected graph problems.
Î±: Given G(V, E), does G have an independent set of size  V   4?
Î²: Given G(V, E), does G have an independent set of size 5?
Which of the following statements is TRUE?
 Î± is in P, and Î² is NPcomplete
 Î± is NPcomplete, and Î² is in P
 Both Î± and Î² are NPcomplete

Both Î± and Î² are in P
Answer: (c) Both Î± and Î² are NPcomplete
Explanation: Graph independent set decision problem is NPComplete
16. Consider the following two scenarios. Q1, Q2, with Q1 reducing to 3SAT in polynomial time and 3SAT reducing to Q2 in polynomial time. Then which of the following is true in light of the preceding statement?
 Q1 is in NP, Q2 is NPhard
 Q2 is in NP, Q1 is NPhard
 Both Q1 and Q2 are in NP

Both Q1 and Q2 are in NPhard
Answer: (a) Q1 is in NP, Q2 is NPhard
Explanation:
Q1 reduces to 3SAT in polynomial time ==> Q1 is in NP.
3SAT is reduced to Q2 in polynomial time ==> Q2 is an NPhard problem. If Q2 can be solved in P, then 3SAT can be solved in P, but because 3SAT is NPComplete, Q2 is NPHard.
17. Language L1 can be reduced to language L2 in polynomial time. Language L3 can be reduced in polynomial time to L2, which can then be reduced in polynomial time to language L4. Which of the following statements is/are correct?
I. If L4 âˆˆ P, L2 âˆˆ P
II. If L1 âˆˆ P or L3 âˆˆ P, then L2 âˆˆ P
III. L1 âˆˆ P, if and only if L3 âˆˆ P
IV. If L4 âˆˆ P, then L1 âˆˆ P and L3 âˆˆ P
 II only
 III only
 I and IV only

I only
Answer: (c) I and IV only
Explanation:
Theory
18. Consider the following three scenarios. P1, P2, and P3 are the first three letters of the alphabet. P1 is known to be decidable, while P2 is unknown. Which of the following statements is TRUE?:
 P3 is decidable if P1 is reducible to P3
 P3 is undecidable if P3 is reducible to P2
 P3 is undecidable if P2 is reducible to P3

P3 is decidable if P3 is reducible to P2â€™s complement
Answer: (d) Both S1 and S2 are correct.
Explanation:
For (a) P1 â‰¤p P3 and given P1 is decidable gives no conclusion for P3.
For (b) P3 â‰¤p P2 and given P2 is undecidable gives no conclusion for P3.
For (c) P2 â‰¤p P3 and given P2 is undecidable gives conclusion for P3 to be undecidable.
For (d) P3 â‰¤p P2â€™s complement and given P2 is undecidable; therefore, P2â€™s
complement is also undecidable, giving no conclusion for P3.
19. Which of the following problems is not NPcomplete undecidable?
 Partition Problem
 Halting Problem
 Hamiltonian Circuit

Bin packing
Answer: (b) Halting problem
Explanation: This is an undecidable problem because we can't have a generalised algorithm that tells us whether a programme will halt or not without having a specific program/algorithm. We can't always know, which is why we can't have a universal algorithm.