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

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

 

[pbuk]

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

If you do not know the answer to this question then, with respect, I suggest that you do not yet have sufficient understanding of the subject to consider P vs NP. You can find a free course on the subject here: https://ocw.mit.edu/courses/mathematics/18-404j-theory-of-computation-fall-2020/index.htm

 

[fresh_42]

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

Yes.

https://en.wikipedia.org/wiki/Multi...g a natural,additions, which can be expensive.

 

[Mark44]

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

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

If you do not know the answer to this question then, with respect, I suggest that you do not yet have sufficient understanding of the subject to consider P vs NP.

I agree. Thread closed.