Argument
P versus NP problem
Overview
The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every decision problem for which a proposed positive answer can be quickly verified can also be quickly solved.
Here, "quickly" means an algorithm exists that solves the task and runs in polynomial time (as opposed to, say, exponential time), meaning the task completion time is bounded above by a polynomial function on the size of the input to the algorithm. The general class of questions that some algorithm can answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if provided with an answer, it can be verified quickly. The class of questions where an answer can be verified in polynomial time is "NP", standing for "nondeterministic polynomial time".
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
The problem has been called the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
It is called ‘infinite’ if it includes members belonging respectively to all degrees of complexity. It is to be noted that the base of an abstractive hierarchy may contain any number of members, finite or infinite. Further, the infinity of the number of the members of the base has nothing to do with the question as to whether the hierarchy be finite or infinite. A finite abstractive hierarchy will, by definition…
Alfred North Whitehead, Science and the modern world
States what P versus NP problem is.
The chief business of the logician is to classify arguments; for all testing clearly depends on classification. The classes of the logicians are defined by certain typical forms called syllogisms. For example, the syllogism called _Barbara_ is as follows: S is M; M is P: Hence, S is P. Or, to put words for letters— Enoch and Elijah were men; all men die: Hence, Enoch and Elijah must have died. The “is P” of the…
Charles S. Peirce, Chance, Love, and Logic
States what P versus NP problem is.
The problem of knowledge as conceived in the industry of epistemology is the problem of knowledge _in general_--of the possibility, extent, and validity of knowledge in general. What does this "in general" mean? In ordinary life there are problems a-plenty of knowledge in particular; every conclusion we try to reach, theoretical or practical, affords such a problem. But there is no problem of knowledge in general. I…
John Dewey, Creative Intelligence
States what P versus NP problem is.
Related ideas
- Independence (mathematical logic)
- Artificial intelligence
- Game theory
- Philosophy
- John von Neumann
- Kurt Gödel
- Princeton University
- Peano axioms
- Rice University
- Theory of computation
- Turing machine
- Arithmetic
- Theoretical computer science
- Second-order logic
- Time complexity
- Operations research
- Chess
- Computer science
- Algorithm
- Cornell University
- Decision problem
- Existential quantification
- Economics
- Entscheidungsproblem
Place in the tradition
Part of Epistemic modal logic.