Philosophical implications of P vs NP proof?

Question

Wikipedia article on P vs NP says that "a proof either way would have profound implications for ... Philosophy" without providing further details.

So I was wondering what could be the philosophical implications of P vs NP proof?

Answer 1

I would like to preface what I'm about to write by saying that the question might be a little misleading in its seeming assumption that there are two fields: mathematics (containing computational complexity) and philosophy - and never shall the two shall twine. But, I would respond by asking if a clear delineation exists, is it actually definable? I would say obviously figuring out cosets of a group or linear transformations is math and I would say obviously Heidegger is philosophy (using Justice Stewart's "I know it when I see it"). However, what about Godel's Incompleteness Theorem? Branches of decision theory? Other types of meta-mathematics (that is, math about mathematics)? Are these philosophy or math?

All of that is just to say that you might simply be asking the wrong question. It's not "what implications does $P$ vs. $NP$ have for philosophy". Rather it might be better to ask, "If math is about the constructs of our understanding, isn't it all philosophy?"

That being said, I would like to posit a few thoughts about $P$ vs. $NP$ and philosophy. Firstly, the whole notion of $P$ $vs$ $NP$ is about the solvability of kinds of problems. That is, it's asking a very fundamental question about what it means to be a problem. This thinking very quickly bleeds into philosophy. If solving a 100 x 100 sudoku (something we know to be $NP$ $Complete$ turns out to be computationally equivalent with verifying that solution, that seems to indicate something very unintuitive about the nature of solving.

The thinking is that for some reason, humans are much better at verifying problems than solving them. But, is that a construct? Or, is that built into the fabric of the problems? This is very similar to things modern philosopher work on, as well as things as old as Kant or Descartes.

Further, as Scott Aarronson says in his paper Why Philosophers Should Care About Computational Complexity, he posits a relation between complexity and epistemology. He talks about "the largest known prime number" which, as of 2011 is p := 243112609 − 1. But, what does known mean? If it just means that it satisfies the criteria that:

"(a) the expression ‘243112609 − 1’ picks out a unique positive integer, and

(b) that integer has been proven (in this case, via computer, of course) to be prime."

then couldn't we just write

$p'$ = "The first prime larger than 243112609 − 1."?

So, Aaronson says, that the way to define this better is with complexity. That is, "We know an algorithm that takes as input a positive integer k, and that outputs the decimal digits of p = 2k − 1 using a number of steps that is polynomial—indeed, linear—in the number of digits of p. But we do not know any similarly-efficient algorithm that provably outputs the first prime larger than 2k − 1"

So, while not totally related to the $P$ vs. $NP$ problem, per se, it indicates another area of intersection between complexity and philosophy.