• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

8 P-NP Problem Interview Questions with Answers

Want to Share your Interview Experience?/10170/1
CSE SubjectData Structure

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.

Data StructureP-NP
Want to Share your Interview Experience?
This interview questions and experience are shared by one of the readers like you. You can share your interview experience as well. If you want to help new job aspirants to get their dream job, kindly share your experience on CSEstack Portal, by filling this simple form. It will be published on our portal. Thank You!

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Sawan
    January 22, 2019 at 10:50 pm

    Good one…some more elaboration will be more helpful..:)

Leave a Reply Cancel reply

Interview Questions



You can share your interview experience.

Subscribe for FREE Newsletter

Do you want me to send you programing updates for FREE?

Subscribe below…

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard