In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. It is the set of problems that can be solved in polynomial time by a nondeterministic Turing machine or verified in polynomial time by a deterministic Turing machine. P (all problems solvable in polynomial time) is contained in NP, but NP contains many more problems, including the hardest ones called NP-complete. The most important open question is whether polynomial-time algorithms exist for solving NP-complete problems.
Carnegie Mellon University
Fall 2018
The course provides a rigorous introduction to the foundations of computer science, improving abstract thinking skills and preparing students to be innovators in the field. Topics include computation, computational complexity, and real-world applications of computational concepts. Prerequisites imply this is an intermediate-level course.
No concepts data
+ 25 more concepts