# 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.