NP and N concepts

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?

1. Both DHAM3 and SHAM3 are NP-hard
2. SHAM3 is NP-hard
3. DHAM3 is NP-hard
4. Both DHAM3 and SHAM3 are not NP-hard
    

Answer: (a) Both DHAM3 and SHAM3 are NP-hard
Explanation: The problem of determining whether or not a Hamiltonian Cycle exists is NP-Hard and NP-Complete. It is also NP-Hard to find a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3.

 

2. Which of the following statements about NP-Complete and NP-Hard problems is correct?

1. To demonstrate the NP-Hardness of problem X, we take a known NP-Hard problem Y and reduce it to X.
2. The circuit satisfiability problem was the first to be proven to be NP-complete.
3. NP-complete is a subset of NP-Hard.
4. All the above.
    

Answer: (d) All the above.
Explanation: The most challenging problems in the NP set are NP-complete problems. A decision problem L is NP-complete if and only if the following conditions are met: 

1) L is in NP (Any given solution for NP-complete 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 NP-Hard if it follows the above-mentioned property 2, but it does not need to follow property 1. As a result, the NP-Complete set is a subset of the NP-Hard set.

Thus answer is All the above.

 

3. Consider X to be an NP-complete problem. Then, which of the following statements is TRUE?

1. For X, there is no polynomial-time algorithm.
2. P = NP if X can be solved deterministically in polynomial time.
3. If X is NP-hard, it must also be NP-complete.
4. X could be indecisive.
    

Answer: (c) If X is NP-hard, it must also be NP-complete.
Explanation:

(a) is incorrect because the set NP contains both P (Polynomial-time solvable) and NP-Complete.

(b) is incorrect because X could belong to P (for the same reason that (A) is incorrect).

(c) is the correct answer because the NP-Complete set is the intersection of the NP and NP-Hard sets.

(d) is incorrect because all NP problems can be solved in a finite number of operations.

 

4. 3-SAT and 2-SAT are the problems of

1. both in P
2. Both NP-complete
3. NP-complete and in P, respectively
4. undecidable and NP-complete, respectively
    

Answer: (c) NP-complete 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.

3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT), respectively, when each clause contains exactly k = 3 and k = 2 literals.

2-SAT is a P, whereas 3-SAT is an NP-Complete.

 

5. Ramu and Shyamu have been tasked with demonstrating that a specific problem is NP-complete. Ramu demonstrates a polynomial-time reduction from the 3-SAT problem, while Shyamu demonstrates a polynomial-time reduction from 3-SAT. Which of the following conclusions can be drawn from these reductions?

1. NP-complete but not NP-hard 
2. NP-hard but not NP-complete 
3. NP-complete?
4. Neither NP-hard nor NP-complete.
    

Answer: (c) NP-complete.
Explanation: It is NP-hard because polynomial-time reduction from the 3-SAT problem is possible.

It is NP-Complete because polynomial-time reduction from 3-SAT is possible.

 

6. Consider the two graph problems below.

1. 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.
2. 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?

1. Problem 1 belongs to the NP-Complete set, while Problem 2 belongs to the P Complete set.
2. Problem 1 belongs to the P set, while Problem 2 belongs to the NP-Complete set.
3. Both problems are from the P set 
4. Both problems are part of the NP-complete set.
    

Answer: (a) Problem 1 belongs to the NP-Complete set, while Problem 2 belongs to the P Complete set.
Explanation: The first problem is the Hamiltonian Cycle problem, a well-known NP-Complete problem. The second problem is the Euler Circuit problem, which can be solved in polynomial time.

 

7. If a problem in NP is NP-complete, then:

1. In polynomial time, it can be reduced to the 3-SAT problem 
2. It is possible to solve the 3-SAT problem in polynomial time  
3. In polynomial time, it can be reduced to any other NP problem.
4. Some NP problems can be reduced to them in polynomial time.
    

Answer: (b) It is possible to solve the 3-SAT 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 3-SAT is an NPC problem, reducing it to an NP problem implies that the NP problem is NPC.

 

8. Let S be an NP-complete problem, and Q and R be two other problems that are not known to be NP-complete. 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.

1. R is NP-complete
2. R is NP-hard
3. Q is NP-complete
4. Q is NP-hard
    

Answer: (b) R is NP-hard.
Explanation:

(a) False because R does not exist in NP. An NP-Complete problem must be NP and NP-hard.

(b) True because an NP-Complete problem S is polynomial-time educable to R.

(c) False because Q does not exist in NP.

(d) False because there is no NP-complete polynomial-time problem. Q is Turing-reducible.

 

9. Given the following assertions:

S1: Every language that is context-sensitive. L is a recursive function.

S2: There is a non-context-sensitive recursive language.

    Which of these statements is correct?

1. Only S1 is correct
2. Only S2 is correct
3. Both S1 and S2 are not correct
4. 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 NP-complete for problem X, and X reduces to Y in polynomial time for problem Y. Which of the following statements is TRUE?

1. If X can be solved in polynomial time, then so can Y
2. X is NP-complete
3. X is NP-hard
4. X is in NP, but not necessarily NP-complete
    

Answer: (d)  X is in NP, but not necessarily NP-complete.
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(NP-Complete) problem is reduced to an unknown problem, the unknown problem is transformed into an NPH (NP-Hard).

Case 2: When an NPH(NP-Hard) problem is reduced to an unknown problem, the unknown problem becomes an NPH (NP-Hard).

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 P-type problem, the unknown problem is also reduced to a P-type 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 polynomial-time 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 NP-Complete is correct? (NPC)?

 

Answer: (d)
Explanation: The problem of the clique is NP-complete. If one NP-complete problem can be solved in polynomial time, then all NP-complete 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 NP-Complete, a non-deterministic polynomial-time algorithm for solving it exists.

1. 1, 2 and 3
2. 1 and 3
3. 2 and 3
4. 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 NP-complete is a subset of NP, and NP denotes the existence of a non-deterministic polynomial-time 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 NP-Complete, it can be solved using a non-deterministic polynomial-time algorithm.

1. 1, 2 and 3
2. 1 and 2 only
3. 2 and 3 only
4. 1 and 3 only

Answer: (c) NP-complete 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 decision-making. 2CNFSAT's definition is as follows:

1. NP-Complete.
2. Solvable in polynomial time by reduction to directed graph reachability.
3. Solvable in the constant time since any input instance is satisfiable.
4. NP-hard, but not NP-complete.
    

Answer: (b) Solvable in polynomial time by reduction to directed graph reachability.
Explanation: 2CNF-SAT can be reduced to a problem with strongly connected components. A polynomial-time solution exists for the strongly connected component. As a result, 2CNF-SAT 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?

1. α is in P, and β is NP-complete
2. α is NP-complete, and β is in P
3. Both α and β are NP-complete
4. Both α and β are in P
    

Answer: (c) Both α and β are NP-complete
Explanation: Graph independent set decision problem is NP-Complete

 

16. Consider the following two scenarios. Q1, Q2, with Q1 reducing to 3-SAT in polynomial time and 3-SAT reducing to Q2 in polynomial time. Then which of the following is true in light of the preceding statement?

1. Q1 is in NP, Q2 is NP-hard
2. Q2 is in NP, Q1 is NP-hard
3. Both Q1 and Q2 are in NP
4. Both Q1 and Q2 are in NP-hard
    

Answer: (a) Q1 is in NP, Q2 is NP-hard
Explanation: 
Q1 reduces to 3-SAT in polynomial time ==> Q1 is in NP.

3-SAT is reduced to Q2 in polynomial time ==> Q2 is an NP-hard problem. If Q2 can be solved in P, then 3-SAT can be solved in P, but because 3-SAT is NP-Complete, Q2 is NP-Hard.

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

1. II only
2. III only
3. I and IV only
4. 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?:

1. P3 is decidable if P1 is reducible to P3
2. P3 is undecidable if P3 is reducible to P2
3. P3 is undecidable if P2 is reducible to P3
4. 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 NP-complete undecidable?

1. Partition Problem
2. Halting Problem
3. Hamiltonian Circuit
4. 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.