I have an embarrasing confession to make. I don’t understand why PvsNP is so hard.
[I’m in good company since apparently Richard Feynmann couldn’t be convinced it was a serious open problem.]
I think I understand PvsNP and its many variants like existence of one-way function is about computational hardness of certain tasks. It is surprising that we have such strong intuitions that some tasks are computationally hard but we fail to be able to prove it!
Of course I don’t think I can prove it and I am not foolish enough to spend significant amount of time on trying to prove it. I still would like to understand the deep reasons why it’s so hard to prove computational hardness results. That means I’d like to understand why certain general proof strategies are impossible or very hard.
There is an old argument by Shannon that proves that almost every* Boolean function has exponential circuit depth. This is a simple counting argument. Basically, there are exponentially many more Boolean functions than there are circuits. It’s hard to give explicit examples of computationally hard functions** but we can easily show they are plentiful.
This would seem to settle the matter of existence of computationally hard functions. I believe the rattlesnake in the grass is that the argument only proves that Boolean functions are computationally hard to compute in terms of Boolean circuits but general computable algorithms are more expressive? I am not entirely sure about this.
I have two confusions about this:
Confusion #1: General algorithms would need to make use of some structure. They aren’t magic. Can’t we solve that if you could do this in general you would need to effectively ‘simulate’ these Boolean circuits which would reduce the proof to Shannon-like counting argument?
Confusion #2: Why couldn’t we make similar counting arguments for Turing machines?
Shannon’s argument is very similar to the basic counting argument in algorithmic information theory, showing that most strings are K-incompressible.
Rk. There are the famous ‘proof barriers’ to a proof of PvsNP like natural proofs and algebraization. I don’t understand these ideas—perhaps they can shed some light on the matter.
I’m just computational complexity theory enthusiast, but my opinion is that P vs NP centered explanation of computational complexity is confusing. Explanation of NP should happen in the very end of the course.
There is nothing difficult in proving that computationally hard functions exist: time hierarchy theorem implies that, say, P is not equal EXPTIME. Therefore, EXPTIME is “computationally hard”. What is difficult is to prove that very specific class of problems which have zero-error polynomial-time verification algorithms is “computationally hard”.
Confusion #2: Why couldn’t we make similar counting arguments for Turing machines?
I guess a central issue with separating NP from P with a counting argument is that (roughly speaking) there are equally many problems in NP and P. Each problem in NP has a polynomial-time verifier, so we can index the problems in NP by polytime algorithms, just like the problems in P.
in a bit more detail: We could try to use a counting argument to show that there is some problem with a (say) <n2 time verifier which does not have any (say) <n1000 time solver. To do this, we’d like to say that there are more n2 verifier problems than n1000 algorithms. While I don’t really know how we ought to count these (naively, there are ℵ0 of each), even if we had some decent notion of counting, there would almost certainly just be more <n1000 algorithms than <n2 verifiers (since the n2 verifiers are themselves <n1000 algorithms).
Looking at this again, I’m not sure I understand the two confusions. P vs. NP isn’t about functions that are hard to compute (they’re all polynomially computable), rather functions that are hard to invert, or pairs of easily computable functions that hard to prove are equal/not equal to each other. The main difference between circuits and Turing machines is that circuits are finite and bounded to compute whereas the halting time of general Turing machines is famously impossible to determine. There’s nothing special about Boolean circuits: they’re an essentially complete model of what can be computed in polynomial time (modulo technicalities)
In particular, it’s not hard to produce a computable function that isn’t given by a polynomial-sized circuit (parity doesn’t work as it’s polynomial, but you can write one down using diagonalization—it would be very long to compute, but computable in some suitably exponentially bounded time). But P vs. NP is not about this: it’s a statement that exists fully in the world of polynomially computable functions.
We know there are difficult computational problems. P vs NP is more narrow than that; it’s sometimes phrased as “are there problems that are not difficult to verify but difficult to solve?”, where “difficult” means that it cannot be done in asymptotically polynomial time.
The point is that you can’t use the result that there exists a hard function, since all you know is that the function is hard, not whether it’s in NP, which is a basic problem for your scheme.
Your counting argument for Turing Machines also likely have this problem, and even if not, I see no reason why I couldn’t relativize the results, which is a no-go for P vs NP proof attempts.
Basically, there are 3 main barriers to proving P not equaling NP.
One, you have to actually show that there exists a hard function that isn’t in P, and it’s not enough to prove that there are exponentially many hard functions, because it might be that a circuit computing an NP-complete problem has a linear time bound.
And natural proofs argue that unless cryptographically hard functions don’t exist, the common way to prove circuit lower bounds also can’t prove P vs NP (Technical details are below:)
Also, both of the strategies cannot relativize or algebrize, where relativization means that if we give a fixed oracle tape O consisting of a single problem you can solve instantly to all parties doesn’t change the conclusion for all oracle tapes O.
Many results like this, including possibly your attempts to prove via counting arguments almost certainly relativize, and even if they don’t, they algebrize, and the technical details are below for algebrization are here, since I already explained relativization above.
Yeah I think this is a good place to probe assumptions, and it’s probably useful to form world models where you probability of P = NP is nonzero (I also like doing this for inconsistency of logic). I don’t have an inside view, but like Scott Aaronson on this: https://www.scottaaronson.com/papers/pnp.pdf:
My real view on P vs NP is that at this point, I think P almost certainly not equal to NP, and that any solving of NP-complete problems efficiently to the standard of complexity theorists requires drastically changing the model of computation, which corresponds to drastic changes in our physics assumptions like time travel actually working according to Deutsch’s view (and there being no spurious fixed-points).
I have an embarrasing confession to make. I don’t understand why PvsNP is so hard.
[I’m in good company since apparently Richard Feynmann couldn’t be convinced it was a serious open problem.]
I think I understand PvsNP and its many variants like existence of one-way function is about computational hardness of certain tasks. It is surprising that we have such strong intuitions that some tasks are computationally hard but we fail to be able to prove it!
Of course I don’t think I can prove it and I am not foolish enough to spend significant amount of time on trying to prove it. I still would like to understand the deep reasons why it’s so hard to prove computational hardness results. That means I’d like to understand why certain general proof strategies are impossible or very hard.
There is an old argument by Shannon that proves that almost every* Boolean function has exponential circuit depth. This is a simple counting argument. Basically, there are exponentially many more Boolean functions than there are circuits. It’s hard to give explicit examples of computationally hard functions** but we can easily show they are plentiful.
This would seem to settle the matter of existence of computationally hard functions. I believe the rattlesnake in the grass is that the argument only proves that Boolean functions are computationally hard to compute in terms of Boolean circuits but general computable algorithms are more expressive? I am not entirely sure about this.
I have two confusions about this:
Confusion #1: General algorithms would need to make use of some structure. They aren’t magic. Can’t we solve that if you could do this in general you would need to effectively ‘simulate’ these Boolean circuits which would reduce the proof to Shannon-like counting argument?
Confusion #2: Why couldn’t we make similar counting arguments for Turing machines?
Shannon’s argument is very similar to the basic counting argument in algorithmic information theory, showing that most strings are K-incompressible.
Rk. There are the famous ‘proof barriers’ to a proof of PvsNP like natural proofs and algebraization. I don’t understand these ideas—perhaps they can shed some light on the matter.
@Dalcy
*the complement is exponentially sparse
** parity functions?
I’m just computational complexity theory enthusiast, but my opinion is that P vs NP centered explanation of computational complexity is confusing. Explanation of NP should happen in the very end of the course.
There is nothing difficult in proving that computationally hard functions exist: time hierarchy theorem implies that, say, P is not equal EXPTIME. Therefore, EXPTIME is “computationally hard”. What is difficult is to prove that very specific class of problems which have zero-error polynomial-time verification algorithms is “computationally hard”.
I guess a central issue with separating NP from P with a counting argument is that (roughly speaking) there are equally many problems in NP and P. Each problem in NP has a polynomial-time verifier, so we can index the problems in NP by polytime algorithms, just like the problems in P.
in a bit more detail: We could try to use a counting argument to show that there is some problem with a (say) <n2 time verifier which does not have any (say) <n1000 time solver. To do this, we’d like to say that there are more n2 verifier problems than n1000 algorithms. While I don’t really know how we ought to count these (naively, there are ℵ0 of each), even if we had some decent notion of counting, there would almost certainly just be more <n1000 algorithms than <n2 verifiers (since the n2 verifiers are themselves <n1000 algorithms).
Thank you Kaarel—this the kind of answer I was after.
Looking at this again, I’m not sure I understand the two confusions. P vs. NP isn’t about functions that are hard to compute (they’re all polynomially computable), rather functions that are hard to invert, or pairs of easily computable functions that hard to prove are equal/not equal to each other. The main difference between circuits and Turing machines is that circuits are finite and bounded to compute whereas the halting time of general Turing machines is famously impossible to determine. There’s nothing special about Boolean circuits: they’re an essentially complete model of what can be computed in polynomial time (modulo technicalities)
In particular, it’s not hard to produce a computable function that isn’t given by a polynomial-sized circuit (parity doesn’t work as it’s polynomial, but you can write one down using diagonalization—it would be very long to compute, but computable in some suitably exponentially bounded time). But P vs. NP is not about this: it’s a statement that exists fully in the world of polynomially computable functions.
We know there are difficult computational problems. P vs NP is more narrow than that; it’s sometimes phrased as “are there problems that are not difficult to verify but difficult to solve?”, where “difficult” means that it cannot be done in asymptotically polynomial time.
Yes, I am familiar with the definition of PvsNP. That’s not what I am asking.
The point is that you can’t use the result that there exists a hard function, since all you know is that the function is hard, not whether it’s in NP, which is a basic problem for your scheme.
Your counting argument for Turing Machines also likely have this problem, and even if not, I see no reason why I couldn’t relativize the results, which is a no-go for P vs NP proof attempts.
Basically, there are 3 main barriers to proving P not equaling NP.
One, you have to actually show that there exists a hard function that isn’t in P, and it’s not enough to prove that there are exponentially many hard functions, because it might be that a circuit computing an NP-complete problem has a linear time bound.
And natural proofs argue that unless cryptographically hard functions don’t exist, the common way to prove circuit lower bounds also can’t prove P vs NP (Technical details are below:)
https://en.wikipedia.org/wiki/Natural_proof
Also, both of the strategies cannot relativize or algebrize, where relativization means that if we give a fixed oracle tape O consisting of a single problem you can solve instantly to all parties doesn’t change the conclusion for all oracle tapes O.
Many results like this, including possibly your attempts to prove via counting arguments almost certainly relativize, and even if they don’t, they algebrize, and the technical details are below for algebrization are here, since I already explained relativization above.
https://www.scottaaronson.com/papers/alg.pdf
But that’s why proving P vs NP is so hard technically.
You might be interested in Scott Aaronson’s thoughts on this in section 4: Why Is Proving P != NP Difficult?, which is only 2 pages.
looks like you referenced the same paper before me while I was making my comment :)
Ha, that’s awesome. Thanks for including the screenshot in yours :) Scott’s “invisible fence” argument was the main one I thought of actually.
See https://en.wikipedia.org/wiki/Natural_proof
Yeah I think this is a good place to probe assumptions, and it’s probably useful to form world models where you probability of P = NP is nonzero (I also like doing this for inconsistency of logic). I don’t have an inside view, but like Scott Aaronson on this: https://www.scottaaronson.com/papers/pnp.pdf:
My real view on P vs NP is that at this point, I think P almost certainly not equal to NP, and that any solving of NP-complete problems efficiently to the standard of complexity theorists requires drastically changing the model of computation, which corresponds to drastic changes in our physics assumptions like time travel actually working according to Deutsch’s view (and there being no spurious fixed-points).