3 ms·

This is where complexity theory comes in; you want a proof that is checkable in polynomial time; listing examples one by one to prove something is not such a pr

This is where complexity theory comes in; you want a proof that is checkable in polynomial time; listing examples one by one to prove something is not such a proof. If instead the question asked, solve x^3 = 8192; a proof iterating from 0 uptil the cube root of 8192 wouldn't work, because that's exponential in the problem size. Brute force search to get a counter example to the Reimann hypothesis produces a solution that is checkable in polynomial time; you just evaluate the Reimann-zeta function at the produced point.

divbit 10y ago
I think, in the case of an algebra class, the student could assume something like an integral / rational solution space. Otherwise, the solution is just to put the opposite symbol on the other side of the equation, e.g. (8192)^(1/3), which is maybe(?) what the teacher is asking, however would the teacher actually accept an answer written in the form 27^(1/3)? I would guess that I would not accept that. I understand what you are saying, but in this case, it could be argued that the 8192 case is actually a different question, because the underlying multiplicative group is different.
21 10y ago
Why does it matter the complexity of the solution check? If for some reason the counter example of the Reimann hyp would be checkable in exponential time (whatever that means), and if it would have required 10 years of computer time to check, how would that matter? The solution would still stand (assuming that everybody agrees that no mistake was made).
- Ar-Curunir 10y ago
  The question applies to the classroom setting we were talking about; teachers don't have access to supercomputers :P
divbit 10y ago
To expand on my previous response: you want a proof that is checkable in polynomial time; yes - completely agree. I was just playing the devil's advocate case, that maybe integer solutions could be assumed (if it was a low-level class, for example).

divbit 10y ago

I think, in the case of an algebra class, the student could assume something like an integral / rational solution space. Otherwise, the solution is just to put the opposite symbol on the other side of the equation, e.g. (8192)^(1/3), which is maybe(?) what the teacher is asking, however would the teacher actually accept an answer written in the form 27^(1/3)? I would guess that I would not accept that. I understand what you are saying, but in this case, it could be argued that the 8192 case is actually a different question, because the underlying multiplicative group is different.

21 10y ago

Why does it matter the complexity of the solution check? If for some reason the counter example of the Reimann hyp would be checkable in exponential time (whatever that means), and if it would have required 10 years of computer time to check, how would that matter? The solution would still stand (assuming that everybody agrees that no mistake was made).

Ar-Curunir 10y ago
The question applies to the classroom setting we were talking about; teachers don't have access to supercomputers :P

divbit 10y ago

To expand on my previous response: you want a proof that is checkable in polynomial time; yes - completely agree. I was just playing the devil's advocate case, that maybe integer solutions could be assumed (if it was a low-level class, for example).