Complexity Classes P & NP Video Lecture | Theory of Computation - Computer Science Engineering (CSE)

This video is part of
18 videos|70 docs|44 tests
Join course for free

FAQs on Complexity Classes P & NP Video Lecture - Theory of Computation - Computer Science Engineering (CSE)

1. What is the complexity class P?
Ans. The complexity class P consists of all decision problems that can be solved by a deterministic Turing machine in polynomial time. In other words, it includes problems for which there exists an algorithm that can solve them efficiently.
2. What is the complexity class NP?
Ans. The complexity class NP (nondeterministic polynomial time) consists of all decision problems for which a solution can be verified by a deterministic Turing machine in polynomial time. It includes problems that can be solved in polynomial time by a nondeterministic Turing machine, but not necessarily by a deterministic one.
3. What is the difference between the complexity classes P and NP?
Ans. The main difference between the complexity classes P and NP is that P represents problems that can be solved efficiently by a deterministic Turing machine in polynomial time, while NP represents problems for which a solution can be verified efficiently in polynomial time, but not necessarily solved by a deterministic machine in polynomial time.
4. Are all problems in P also in NP?
Ans. Yes, all problems in P are also in NP. This is because if a problem can be solved efficiently by a deterministic Turing machine in polynomial time, then its solution can also be verified efficiently by a deterministic Turing machine in polynomial time.
5. Is P equal to NP?
Ans. The question of whether P is equal to NP is one of the biggest open problems in computer science. It asks whether every problem for which a solution can be verified efficiently can also be solved efficiently. So far, no one has been able to prove whether P is equal to NP or not, and it remains an unsolved problem.
18 videos|70 docs|44 tests

Up next

Explore Courses for Computer Science Engineering (CSE) exam
Related Searches

practice quizzes

,

pdf

,

past year papers

,

Viva Questions

,

video lectures

,

Semester Notes

,

Previous Year Questions with Solutions

,

Complexity Classes P & NP Video Lecture | Theory of Computation - Computer Science Engineering (CSE)

,

ppt

,

mock tests for examination

,

Objective type Questions

,

Summary

,

Important questions

,

study material

,

Free

,

Sample Paper

,

Exam

,

Complexity Classes P & NP Video Lecture | Theory of Computation - Computer Science Engineering (CSE)

,

shortcuts and tricks

,

MCQs

,

Extra Questions

,

Complexity Classes P & NP Video Lecture | Theory of Computation - Computer Science Engineering (CSE)

;