P versus NP Question
Jump to navigation
Jump to search
A P versus NP Question is a theoretical Computing Science research question that asks whether there is an efficiently verifiable solution for any NP-complete decision task.
References
2014
- (Bolotin, 2014) ⇒ Arkady Bolotin. (2014). “Computational Solution to Quantum Foundational Problems.” In: arXiv preprint arXiv:1403.7686. doi:10.9734/PSIJ/2014/11144
- QUOTE: This paper argues that the requirement of applicableness of quantum linearity to any physical level from molecules and atoms to the level of macroscopic extensional world, which leads to a main foundational problem in quantum theory referred to as the “measurement problem", actually has a computational character … From the point of view of computational complexity theory, this requirement is equivalent to the assumption that the computational complexity classes P and NP are equal, which is widely believed to be very unlikely.
2011
- (Kolaitis, 2011) ⇒ Phokion G. Kolaitis. (2011). “The quest for a logic for polynomial-time computation: technical perspective.” In: Communications of the ACM, 54(6). doi:10.1145/1953122.1953149
- QUOTE: Formally, the P vs. NP problem asks whether or not the class NP of all algorithmic problems solvable by a non-deterministic Turing machine in polynomial time coincides with the class P of all algorithmic problems solvable by a deterministic Turing machine in polynomial time. Informally, the P vs. NP problem asks whether every algorithmic problem whose solutions can be efficiently verified has the property that its solutions can also be efficiently computed.
2009
- (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The Status of the P versus NP Problem.” In: Communications of the ACM, 52(9). doi:10.1145/1562164.1562186
- So P = NP means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well. … In the 1970s, theoretical computer scientists showed hundreds more problems NP-complete (see Garey and Johnson16). An efficient solution to any NP-complete problem would imply P = NP and an efficient solution to every NP-complete problem.
