What are the P-NP problem interview questions?
Here is a list of simple questions with answer.
Answer: There are two types of computational machines.
Now, what is the problem statement?
Answer: Problem is solving a decision problem which gives an answer in Yes/No.
Answer: There are two types of problems.
Definition: NP-complete problems are defined recursively, a problem is an NP-complete problem if…
Now question arises
Answer: Boolean satisfiability problem was first NP-complete problem proposed by Steve Cook.
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.
Answer: Boolean satisfiability is the problem to find of whether the given Boolean equation is true or false.
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.
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.