The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).

In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer's present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other).

In this theory, the class P consists of all those decision problems that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine. Clearly, P ⊆ NP. Arguably the biggest open question in theoretical computer science concerns the relationship between those two classes:

Is P equal to NP?

What would be the philosophical implications of a solution to the P versus NP problem?

  • This question appears to be off-topic because it is about theoretical computer science rather than philosophy; it assumes that there are philosophical implications of P=NP rather than arguing for one. Commented Jul 10, 2014 at 1:25

1 Answer 1


What would be the philosophical implications of a solution to the P versus NP problem?

I'm not sure whether "a solution" itself will have philosophical implications, and whether we can know anything about these implications without knowing the solution itself.

If by solution, you just mean the knowledge that P is not equal NP, then there are some philosophical implication that we can know. At least some people have elaborated on these consequences, but let me just cite from Scott Aaronson's Why Philosophers Should Care About Computational Complexity:

The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are particularly subject. This is the assumption that as soon as a fact is presented to a mind all consequences of that fact spring into the mind simultaneously with it. It is a very useful assumption under many circumstances, but one too easily forgets that it is false. —Alan M. Turing [126]

In my own opinion, the assumption that all phenomena that we can observe in the physical world like randomness, independence and unpredictability (or non-observability) can be approximated arbitrarily good by mathematical theories is only tenable if we also assume that P is not equal to NP.

Not the answer you're looking for? Browse other questions tagged .