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..."

 

[JacobIA]

Ignore "is large..."

Is that correct?

 

[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.

sorry, i did not see the rest of your post. was using a small screen phone. now using laptop... ok. so your saying pythagoras theorem/formula in probably not in NP because some input values cannot be written in finite time. makes sense. am i on the same page with you now?

 

[fresh_42]

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

This depends on what you mean by "verify". Say we have an Input $\{a,b\}$ of binary length $n.$ Then $c=\sqrt{a^2+b^2}$ is the answer. I can write down the expression $\sqrt{a^2+b^2}\,$ in time $n+4$. One root symbol, two squares, one addition sign, and the length of the Input. But this is probably not the answer. If $a$ and $b$ are fixed, then I can write $\sqrt{a^2+b^2}\,$ even in constant time. I guess this isn't what you thought of either. So what is the Output $c$? It is normally an irrational number of infinite length that cannot be "verified" at all!

 

[JacobIA]

This depends on what you mean by "verify". Say we have an Input $\{a,b\}$ of binary length $n.$ Then $c=\sqrt{a^2+b^2}$ is the answer. I can write down the expression $\sqrt{a^2+b^2}\,$ in time $n+4$. One root symbol, two squares, one addition sign, and the length of the Input. But this is probably not the answer. If $a$ and $b$ are fixed, then I can write $\sqrt{a^2+b^2}\,$ even in constant time. I guess this isn't what you thought of either. So what is the Output $c$? It is normally an irrational number of infinite length that cannot be "verified" at all!

mmm! ok. so the pythagoras formula cannot be verified in poly time (for all values) and therefor not in np. correct? if correct then i think i understand now. many thanks!

 

[fresh_42]

mmm! ok. so the pythagoras formula cannot be verified in poly time (for all values) and therefor not in np. correct?

It doesn't even have an algorithm that stops at all! If you add the condition that, e.g. 100 digits after the comma is enough precision, then it can be verified in polynomial time. But that is a different problem. If you add the condition that $\{a,b,c\}$ all are integers, then we have Pythagorean triples. They are all known and can be written down in polynomial time.

 

[fresh_42]

You can find some examples of calculations on algorithms in the last attached document of
https://www.physicsforums.com/threads/solution-manuals-for-the-math-challenges.977057/
if you search the text for "algorithm".

None of them is NP-hard, but it illustrates how the typical questions in the field are dealt with.

 

[Jarvis323]

mmm! ok. so the pythagoras formula cannot be verified in poly time (for all values) and therefor not in np. correct? if correct then i think i understand now. many thanks!

It can get murky I guess depending on how you define the input, and you have to be very precise in your definitions. Technically, any computable number can be encoded as a finite length string. E.g., if $a$ and $b$ are computable, then you can encode $c$ as $\sqrt{a^2+b^2}$. $\sqrt{2}$, $\pi$, are examples of irrational but computable numbers. You can encode $\pi$ as a finite string, for example, by making that string the computer program that prints $\pi$. Some real numbers aren't computable, meaning there is no computer program that prints them, and therefore, no finite representation of them. A non-computable number obviously can't be an input or output of a computer program.

If you restrict the domain of your Pythagorean theorem algorithm to only the computable numbers and define how you encode them, then you can take any of the numbers as inputs. Some of the inputs might look strange, for example, because they could be something like a computer program that generates its digits. Then you might have to consider how to do algebra with variables taking such strange values as things like computer programs. This seems complex, or actually impossible. But still, the challenges that I imagine you would have to overcome, assuming it was even possible in some restricted sense, are not (to me) intuitively relatable to the problems encountered solving NP hard problems.

 

[fresh_42]

$P$ and $NP$ are computation classes. A single problem is always either impossible to solve, or will be solved in constant time. You can only speak of an NP-hard problem if you have varying input lengths. The time an algorithm takes to come to hold on such an input is a function of its input length. Whether this function is a constant, a polynomial, or an exponential function determines its computation class.

Let's simplify your "Pythagoras". Say, we have three inputs $\{a,b,c\}$ of total length $n$. Our algorithm has to decide whether $a^2+b^2=c^2$ or not, so its output is either True or False. If we have a completely rational input, then this problem will be solved in polynomial time.

If we have an input where $a^2+b^2$ isn't a perfect square, then our algorithm will always stop on False. This is because $a^2+b^2\neq c^2$ always (False), since in case $a^2+b^2=c^2$ we cannot even read $c$ because it's infinitely long, contradicting our assumption of a finite length of input.

Algorithms with an infinite input length cannot even start since they will be busy reading the input forever.

Whatever you do to tailor "Pythagoras" such that it makes sense to speak about $NP$, you will either have an algorithm that a) doesn't stop reading the input, b) doesn't stop writing the output, or c) is in $P$.

Hence, forget about "Pythagoras" in this context.

 

[Jarvis323]

If we have an input where $a^2+b^2$ isn't a perfect square, then our algorithm will always stop on False. This is because $a^2+b^2\neq c^2$ always (False), since in case $a^2+b^2=c^2$ we cannot even read $c$ because it's infinitely long, contradicting our assumption of a finite length of input.

Algorithms with an infinite input length cannot even start since they will be busy reading the input forever.

Not strictly true. As I pointed out you could define how you encode each number as being the computer program which prints it. Then you can have as input $a,b$ and $c$ all irrational, and you could parse the input in finite time. But I don't think you could answer yes or no correctly in finite time.

 

[fresh_42]

Not strictly true.

I am pretty sure it is.

But I don't think you could answer yes or no correctly in finite time.

This is a tautology. I can always have an algorithm that stops in one step if I do not bother whether my result is true or not.

 

[Jarvis323]

I am pretty sure it is.

This is a tautology. I can always have an algorithm that stops in one step if I do not bother whether my result is true or not.

There is some extent to which you can do symbolic computation on irrational numbers. Forumulating the input as a computer program generating the number is just a way to generalize the encoding. In some cases, that solver can correctly handle irrational numbers, but not every case, which I think can probably be proven based on undecidability.

 

[fresh_42]

There is some extent to which you can do symbolic computation on irrational numbers.

That was why I have been repeatedly asking for a proper definition of the problem. If $\sqrt{c}$ is a valid output, then $a^2+b^2=c$ is computable in polynomial time and the algorithm is polynomial. But I admit that my usage of the term irrational was an abbreviation of a longer description on which inputs an algorithm does not stop, or cannot read the input. Anyway, that does not change my central statement:

Whatever you do to tailor "Pythagoras" such that it makes sense to speak about $NP$, you will either have an algorithm that a) doesn't stop reading the input, b) doesn't stop writing the output, or c) is in $P$.

Hence, forget about "Pythagoras" in this context.

 

[JacobIA]

You can find some examples of calculations on algorithms in the last attached document of
https://www.physicsforums.com/threads/solution-manuals-for-the-math-challenges.977057/
if you search the text for "algorithm".

None of them is NP-hard, but it illustrates how the typical questions in the field are dealt with.

thank you for your time. but if we do assume pythagorean tripples...is the formula in np or not?
"... If a and b are fixed, then I can write a2+b2 even in constant time.

 

[JacobIA]

thank you for your time. but if we do assume pythagorean tripples...is the formula in np or not?
"... If a and b are fixed, then I can write a2+b2 even in constant ti

That was why I have been repeatedly asking for a proper definition of the problem. If $\sqrt{c}$ is a valid output, then $a^2+b^2=c$ is computable in polynomial time and the algorithm is polynomial. But I admit that my usage of the term irrational was an abbreviation of a longer description on which inputs an algorithm does not stop, or cannot read the input. Anyway, that does not change my central statement:

That was why I have been repeatedly asking for a proper definition of the problem. If $\sqrt{c}$ is a valid output, then $a^2+b^2=c$ is computable in polynomial time and the algorithm is polynomial. But I admit that my usage of the term irrational was an abbreviation of a longer description on which inputs an algorithm does not stop, or cannot read the input. Anyway, that does not change my central statement:

"That was why I have been repeatedly asking for a proper definition of the problem"

Let us simply things a bit.

Problem definition:

Let n be an integer. Can we compute n^2 in polynomial time for any n?

 

[pbuk]

Whatever you do to tailor "Pythagoras" such that it makes sense to speak about $NP$, you will either have an algorithm that a) doesn't stop reading the input, b) doesn't stop writing the output, or c) is in $P$.

Hence, forget about "Pythagoras" in this context.

This says everything that needs to be said; IMHO there is no point in continuing.