If P = NP, can a proof be generated / verified efficiently for a proposition?

[r731]

If P = NP, then the solution of any decision problem in NP can be found efficiently.

Consider the Pythagoras theorem. It can be represented as an encoded (binary) string. (How?) Let D be the decision problem asking whether the input to D is a proof of the Pythagoras theorem.

Given an arbitrary string S, apply the verifier (the algorithm) to check whether S is a valid proof or not, answering D. By applying logarithmic search, the valid proof S* can be found in polynomial-time.

My concern is that any proposition (and theorem) can be encoded as a string, and hence no human mathematician would be needed. Finding the proof in the search space would take polynomial-time. This would also apply to mathematical proofs in engineering and physics.

 

[fresh_42]

You would still have a few major problems:

1. Polynomial does not mean fast. ##O(|S|^{10^{100}})## is still polynomial, but not fast.
2. Your sample space of possible valid strings is exponentially big.
3. You have to find a criterion when ##S## solves ##D## and when it does not.
4. How do you deal with negative statements like FLT, or with checking infinitely many solutions like RH?

In any case there is no way to generate a proof. At best you can hope to verify it in ##P##. I do not see how this problem is any different from ##SAT##. The work to be done remains, namely in coding the problem in a way, such that an algorithm can decide (3). Your example of Pythagoras can be read faster than encoded.

 

[Jarvis323]

You should check out Gödel's letter to Von Neumann.

https://ecommons.cornell.edu/bitstream/handle/1813/6910/89-994.pdf

 

[Jarvis323]

1. Polynomial does not mean fast. ##O(|S|^{10^{100}}## is still polynomial, but not fast

While this is true, it is usually the case that once a polynomial solution is found, a polynomial solution with a small degree is found.

 

[fresh_42]

While this is true, it is usually the case that once a polynomial solution is found, a polynomial solution with a small degree is found.

Yes, because we deal with 'real' problems and algorithms. I doubt that your statement can hold an all quantifier. There might well be theoretical problems with huge lower bounds, depending on how ##NP\subseteq P## is possibly be solved.

 

[Jarvis323]

Yes, because we deal with 'real' problems and algorithms. I doubt that your statement can hold an all quantifier. There might well be theoretical problems with huge lower bounds, depending on how ##NP\subseteq P## is possibly be solved.

This is true. What is especially interesting is that if P=NP, then we get "the great collapse", where the entire polynomial hierarchy $$\Sigma_k^P$$ (which includes problems with more and more nested quantifiers to infinity) all collapses to P. This is one of the reasons why people think it's so unlikely, because there are really really deep problems in there. If P=NP, at least we should expect those deeply nested problems in the polynomial hierarchy to have a high degree, I suppose.

https://en.wikipedia.org/wiki/Polynomial_hierarchy

But the thing is that, assuming P=NP, it is still hard to reason why proof finding should have a specific bounded degree. Would there be some intrinsic upper limit to the logical depth as a function of n that all minimal proofs converge to? I would think not, but it would be pretty cool, as it would mean there are some fundamental limits to complexity (how complex (logically deep) things can get as they get larger). It might tell us some pretty deep stuff, even in theoretical physics, I would guess.

 

[Jarvis323]

You would still have a few major problems:
In any case there is no way to generate a proof.

This is also true. If P=NP, it means that for a class of proofs for which one can write a generalized polynomial verifier, those proofs can all be found as well in polynomial time with a single generalized algorithm. So it would mean that a one algorithm for finding all of those proofs exist. It would mean there isn't some unbounded set of special cases that need to be considered separately, but rather everything we need to know about those statements validity is compressible to the size of those statements themselves along with the finite algorithm we had.

But we wouldn't necessarily be able to easily come up with the algorithm that does that. However, we would know that it could be reduced to instances of SAT (how to do the reduction might not be known). But once that happened for example, then you could plug in any provable statement (that a proof of can be trivially verified ) in ZFC and find a proof for it in polynomial time in the length of the statement.

But yes, also a non-constructive proof of P=NP could be found, which would tell us this is possible, but we would still have no clue how to do any of it.

 

[r731]

You would still have a few major problems:

1. Polynomial does not mean fast. ##O(|S|^{10^{100}})## is still polynomial, but not fast.
2. Your sample space of possible valid strings is exponentially big.
3. You have to find a criterion when ##S## solves ##D## and when it does not.
4. How do you deal with negative statements like FLT, or with checking infinitely many solutions like RH?

In any case there is no way to generate a proof. At best you can hope to verify it in ##P##. I do not see how this problem is any different from ##SAT##. The work to be done remains, namely in coding the problem in a way, such that an algorithm can decide (3). Your example of Pythagoras can be read faster than encoded.

1. True.
2. It is exponential in size, but a good algorithm is not exhaustive. The problem space must be reduced to polynomial in size so that the algorithm is efficient.
3. This step I overlooked. A decision problem is a set of instances paired with Yes/No. For example, 3SAT is a decision problem. An instance of 3SAT is a formula, and an assignment to the formula is a solution. The 3SAT decision problem answers if a formula is satisfiable or not, i.e., if there exists an assignment that satisfies the formula. The criterion is "embedded" in the definition of the decision problem.
4. A proof to FLT is finite. Guessing the proof takes exponential-time, since every combination of characters - some of which are proofs - must be checked. (The set of proofs is a subset of the set of the problem space.) However, if checking whether a proof is valid would take polynomial-time, and the approximate size of a valid proof is known, then generating the proof would be easy (via logarithmic searching).

As Jarvis323 pointed out, it's possible to generate proofs.

 

[fresh_42]

... which includes problems with more and more nested quantifiers to infinity, all collapses to P. This is one of the reasons why people think it's so unlikely, because there are really really deep problems in there. If P=NP, at least we should expect those deeply nested problems in the polynomial hierarchy to have a high degree, I suppose.

I like to think of it a bit prosaically: NP=P is the question, whether there are inherently difficult problems in this world, or whether we are just too dumb to come up with a nice solution. It is something personal.

 

[Vanadium 50]

While this is true, it is usually the case that once a polynomial solution is found, a polynomial solution with a small degree is found.

I think this is very unlikely. We have problems that have defied polynomial time solutions for decades. And remember, if you solve one of them, you solve all of them (in NP-complete). I think it's very unlikely that the outcome will be "Who knew it was quadratic all along?"

 

[Jarvis323]

I like to think of it a bit prosaically: NP=P is the question, whether there are inherently difficult problems in this world, or whether we are just too dumb to come up with a nice solution. It is something personal.

Yeah, I don't like to speculate too much about the human brain's capability in comparison with a classical machine.

But I think that the great collapse is perhaps one of the most compelling and interesting facts/consequences if P=NP. At each new level in the polynomial hierarchy, you get more and more apparently difficult problems that you would not expect to be in P. We're talking about n dimensional chess here where n is unbounded, and all of those problems turning out to be in P.

 

[Jarvis323]

I think this is very unlikely. We have problems that have defied polynomial time solutions for decades. And remember, if you solve one of them, you solve all of them (in NP-complete). I think it's very unlikely that the outcome will be "Who knew it was quadratic all along?"

I think NP=P would be essentially equally shocking if it was quadratic, or degree 1 billion. Because the polynomial hierarchy is not bounded, there will be some problems which you would expect to be so difficult that the difference between a degree 1 billion and degree 4 polynomial seems like nothing.

 

[Office_Shredder]

I think NP=P would be essentially equally shocking if it was quadratic, or degree 1 billion. Because the polynomial hierarchy is not bounded, there will be some problems which you would expect to be so difficult that the difference between a degree 1 billion and degree 4 polynomial seems like nothing.

I don't really agree. A degree four polynomial probably represents an algorithm we can construct. An algorithm which has degree 1 billion probably represents some very subtle adjustment to juuuust stop the thing from growing exponentially.

 

[Jarvis323]

I don't really agree. A degree four polynomial probably represents an algorithm we can construct. An algorithm which has degree 1 billion probably represents some very subtle adjustment to juuuust stop the thing from growing exponentially.

My point is just that any polynomial degree NP complete problem would be extremely surprising.

Because there is a problem that is very strongly believed to be beyond P in any degree (higher time complexity), and there is a problem very strongly believed to be beyond that one, and so on, towards infinity. Just like there is no largest natural number, there is no highest level in the polynomial hierarchy.

If P=NP, all of those problems are in P as well. These are problems with say 1 trillion nested quantifiers tacked on, and beyond. It would be shocking if an algorithm in P could even handle the first next level up with only 2 quantifiers tacked on, let alone gazillions on top of gazillions.

It would mean that the jumps between those levels in the hierarchy (each of which seems a bigger deal than any increase in a polynomial degree) is actually less significant than bumping up the degree of the polynomial or its constant.

From a practical perspective, yes billion degree polynomial complexities are still unfeasible. And it would be surprising if P=NP and that in a practical way.

To me, finding that P=NP for classical machines, would be like finding that caterpillars have superseded humans in intelligence and technology over night.

 

[r731]

I may be off. What frightens me is that if P=NP and any proof can be generated for an arbitrary proposition, then countless new theorems would be derived, notwithstanding theorems applicable in the sciences and engineering.

Speaking of cryptography, if P=NP, it's not too hard to see that a private key in asymmetric encryption can be uncovered easily. In this case, public key encryption would be vulnerable and I wonder what the alternative would be. Maybe the Turing computing model should be replaced by the quantum Turing model, though I have no idea how quantum computers work.

I've glimpsed through quantum-resistant cryptography, but I'm still intuitively not convinced that they are secure (on a classical computational model) if P=NP.

 

[Vanadium 50]

Well, whether one likes the implications of a statement has no bearing on the truth of that statement.

Also, P = NP has no impact on the concept of public key encryption. It has a huge impact on any implementation, such as RSA, but it would still allow trapdoor algorithms in principle: (verification has a lower exponent than solution) P = NP is a statement that verification and solution are both polynomial, not that the solution is efficient.

 

[JacobIA]

Going back to the pythagoras example. Given two sides of a right angled triangle A and B. VERIFYING that some given number C is a solution to the third side can be done in polynomial time - just plug it in the formula A^2 + B^2 = C^2. On the other hand, FINDING C can also be done in polynomial time, just use the same formula.

The question now is: from the above analysis, why can't we conclude that P=NP?.

Considering that we have a finder and a verifier for the triangle problem both working in polynomial time.

 

[PeroK]

Going back to the pythagoras example. Given two sides of a right angled triangle A and B. VERIFYING that some given number C is a solution to the third side can be done in polynomial time - just plug it in the formula A^2 + B^2 = C^2. On the other hand, FINDING C can also be done in polynomial time, just use the same formula.

The question now is: from the above analysis, why can't we conclude that P=NP?.

Considering that we have a finder and a verifier for the triangle problem both working in polynomial time.

P=NP is not just about Pythagoras' theorem!

 

[pbuk]

The question now is: from the above analysis, why can't we conclude that P=NP?.

Considering that we have a finder and a verifier for the triangle problem both working in polynomial time.

All that that shows is that Pythagoras is in P and is also in NP. In fact it can be proved that all problems that are in P are also in NP, not just Pythagoras. However the question is whether there are problems that are in NP that are not in P.

We know lots of problems that are in P. We also know problems that are not in NP (and therefore not in P either) for example the traveling salesman problem. However there are very few problems which we know are in NP but we do not know if they are in P.

The easiest of these to understand is the prime factorization problem: you can quickly check that the prime factors of 304,250,263,527,210 are 2×3×5×7×11×13×17×19×23×29×31×37×41 but if I ask you to factorize 304,250,263,527,209 it is going to take you some time (Edit: unless you cheat by typing it into Wolfram Alpha).

 

[PeroK]

but if I ask you to factorize 304,250,263,527,209 it is going to take you some time.

That's a prime number, actually!

 

[PeroK]

By contrast:
$$304,250,263,527,207 = 3 \times 47 \times 83 \times 25,997,629,969$$And
$$304,250,263,527,211 = 61 \times 450,451 \times 11,072,701$$

 

[pbuk]

That's a prime number, actually!

That's why I chose it.

 

[JacobIA]

That's why I chose it.

Thank you for your comments.

 

[Jarvis323]

There are some problems for which, if you found a polynomial time algorithm for the problem, that would prove P=NP. These are called NP-complete problems. They are both in NP (can be verifed in polynomial time), and they are NP-Hard (as "hard" as any problem in NP, really meaning that you can reduce/convert (in polynomial time) any other problem in NP into a problem instance of the NP-Hard problem). Travelling salesman decision variant or deciding if a booean formula has a true solution (SAT) are some examples of NP-complete problems. So if it turns out that SAT (or any othe NP-complete problem) is actually in P, then all of NP is in P too.

 

[JacobIA]

There are some problems for which, if you found a polynomial time algorithm for the problem, that would prove P=NP. These are called NP-complete problems. They are both in NP (can be verifed in polynomial time), and they are NP-Hard (as "hard" as any problem in NP, really meaning that you can reduce/convert (in polynomial time) any other problem in NP into a problem instance of the NP-Hard problem). Travelling salesman decision variant or deciding if a booean formula has a true solution (SAT) are some examples of NP-complete problems. So if it turns out that SAT (or any othe NP-complete problem) is actually in P, then all of NP is in P too.

Aha! Now we are getting somewhere. The question now is : is pythagoras np-hard? If not then why not?

 

[fresh_42]

Aha! Now we are getting somewhere. The question now is : is pythagoras np-hard? If not then why not?

What do you mean by Pythagoras?

Pythagoras has long been dust, so he isn't hard by any meaning.

 

[pbuk]

The question now is : is pythagoras np-hard? If not then why not?

You should answer this for yourself: what is the definition of NP-hard? Does this apply to finding the hypotenuse of a right angled triangle given the length of the sides?

 

[JacobIA]

There are some problems for which, if you found a polynomial time algorithm for the problem, that would prove P=NP. These are called NP-complete problems. They are both in NP (can be verifed in polynomial time), and they are NP-Hard (as "hard" as any problem in NP, really meaning that you can reduce/convert (in polynomial time) any other problem in NP into a problem instance of the NP-Hard problem). Travelling salesman decision variant or deciding if a booean formula has a true solution (SAT) are some examples of NP-complete problems. So if it turns out that SAT (or any othe NP-complete problem) is actually in P, then all of NP is in P too.

Aha! Now we are getting somewhere. The question now is : is pythagoras np-hard? If not then why not?

What do you mean by Pythagoras?

Pythagoras has long been dust, so he isn't hard by any meaning.

Sorry .. a bit of a lazy typer. Pythagoras theorem. A^2 +b^ = c^2

 

[fresh_42]

Aha! Now we are getting somewhere. The question now is : is pythagoras np-hard? If not then why not?

Sorry .. a bit of a lazy typer. Pythagoras theorem. A^2 +b^ = c^2

Sure, but what has to be solved, i.e. what is the problem? Finding Pythagorean triples (in P), calculating the hypothenuse given the legs, or whatever did you have in mind? And what is a solution? E.g. ##1,414213562373095048801688724209\ldots ## cannot be written in finite time, ##\sqrt{2}## in constant time, and ##\sqrt{n}## in polynomial (linear) time.

 

[JacobIA]

Sure, but what has to be solved, i.e. what is the problem? Finding Pythagorean triples (in P), calculating the hypothenuse given the legs, or whatever did you have in mind? And what is a solution? E.g. ##1,414213562373095048801688724209\ldots ## cannot be written in finite time, ##\sqrt{2}## in constant time, and ##\sqrt{n}## in polynomial (linear) time.

Problem: given two sides of a right angled triangle. Find the third side. I can verify that in polynomials time

 

[fresh_42]

Problem: given two sides of a right angled triangle. Find the third side. I can verify that in polynomials time

You cannot verify ##1^2+1^2= (1,414213562373095048801688724209\ldots )^2## in polynomial time. You cannot even write it in finite time! Hence my question: what is Input, and what is Output?

 

[JacobIA]

Np-hard: say problem A is np-HARD. ﹰﹰproblem ﹰB is also np-hard if problem A can reduce to problem B.
So when I asked if pythagoras theorem (finding the third side...) is np-hard, I was really asking if there exists an np-hard problem that reduces to the pythagoras theorem.

 

[fresh_42]

Np-hard: say problem A is np-HARD. ﹰﹰproblem ﹰB is also np-hard if problem A can reduce to problem B.
So when I asked if pythagoras theorem (finding the third side...) is np-hard, I was really asking if there exists an np-hard problem that reduces to the pythagoras theorem.

Step by step. Before you even talk about P and NP of a certain problem, you will have to define this problem in the first place! And this begins with a description of the Input (in order to determine its length n) and its desired Output (in order to determine its dependence on n).

 

[JacobIA]

Step by step. Before you even talk about P and NP of a certain problem, you will have to define this problem in the first place! And this begins with a description of the Input (in order to determine its length n) and its desired Output (in order to determine its dependence on n).

Great answers guys!

If I understand (I hope I do!) What your saying is that the input I.e in the pythagoras theorem or formula a^2 + b^2 = c^2 . Say your given a, b and c. Verifyng c in polynomial time is not possible for large a and B. is large i.e close to infin

 

[JacobIA]

Great answers guys!

If I understand (I hope I do!) What your saying is that the input I.e in the pythagoras theorem or formula a^2 + b^2 = c^2 . Say your given a, b and c. Verifyng c in polynomial time is not possible for large a and B. is large i.e close to infin

Ignore "is large..."