Discover published sets by community

The P vs NP problem is a major unsolved problem in computer science, regarding the relationship between the complexity classes P and NP.

Complexity classes are categories in computational complexity theory, which classify problems based on the resources needed to solve them, typically time or memory.

P, or polynomial time, refers to the set of problems that can be solved by an algorithm in time that is polynomial with respect to the size of the input.

NP, or nondeterministic polynomial time, refers to the set of decision problems for which a solution can be verified in polynomial time by a deterministic Turing machine.

NP-Complete problems are a subset of NP problems that are both in NP and as hard as any problem in NP, meaning that every NP problem can be reduced, in polynomial time, to an NP-Complete problem.

NP-Hard problems are problems that are at least as hard as the hardest problems in NP, but they are not necessarily in NP themselves, as they may not be decision problems.

A Turing machine is a theoretical computational model used in computer science to represent an algorithm and formalize the definition of computation.

Deterministic computation means that each step of an algorithm leads to only one possible state, while nondeterministic computation allows for multiple possible states, representing different choices at each step.

Polynomial time reduction is a method of proving that one problem is at least as hard as another by showing how an algorithm for one can be used to solve the other in polynomial time.

The Cook-Levin Theorem states that the Boolean satisfiability problem (SAT) is NP-Complete, demonstrating for the first time that NP-complete problems exist.

The Boolean satisfiability problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.

An oracle machine is a theoretical model of computation used to study decision problems. It can solve a specific problem (the oracle) in a single step without elaborating how the solution is derived.

The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2001. A correct solution to any of the problems results in a $1 million prize.$

The Traveling Salesman Problem is an NP-Complete problem that asks for the shortest possible route that a salesman can take to visit each city once and return to the origin city.