8 P-NP Problem Interview Questions with Answers

What are the P-NP problem interview questions?

Here is a list of simple questions with answer.

1. What is a deterministic and non-deterministic machine?

Answer: There are two types of computational machines.

1. Deterministic: the computers which we are using with performance and parallelism limitations
2. Non-Deterministic: the computer which we wish we could have that can have tremendous parallelism

Now, what is the problem statement?

Answer: Problem is solving a decision problem which gives an answer in Yes/No.

2. What is P and NP problem?

Answer: There are two types of problems.

1. P-Problems: Problems which could be solved in Polynomial time by a deterministic machine.
2. NP-Problem: Which could be solved in polynomial time by a non-deterministic machine.

3. What is NP-Complete Problem?

Definition: NP-complete problems are defined recursively, a problem is an NP-complete problem if…

• It is an NP-problem.
• It is reducible to an NP-complete problem in polynomial time.

Now question arises

4. What is the first NP-complete problem?

Answer: Boolean satisfiability problem was first NP-complete problem proposed by Steve Cook.

5. How to prove given problem is NP-complete or not?

Answer: Now to prove that any NP problem is NP-complete, we need to prove that, it is reducible in polynomial time to Boolean satisfiability problem.

6. What is Boolean Satisfiability Problem?

Answer: Boolean satisfiability is the problem to find of whether the given Boolean equation is true or false.

7. What is NP-Hard Problem?

Answer: This is a problem to which a NP-complete problem is polynomial time Turing reducible.

If a problem X in NP-complete is polynomial time Turing reducible to problem Y, problem Y is NP-hard problem.

8. What is Turing Reduction?

Answer: Turing Reduction is nothing but an algorithm which solves problem A when it knows how to solve problem B by converting A into B. That is, all algorithm can be applied on B by inserting a reduction algorithm in between.

I tried to simplify simple questions usually asked in many placement interviews. You can explore these topics to get more detail about each question.

Editors’ Note: This article is written by Madhav Purohit (M.Tech., IIT Kanpur) and edited by CSEstack editorial team. Thanks, Madhav for sharing your knowledge with us. We are sure, readers will be benefited.