Hacker News Reader

Comment by divbit | Hacker News Reader

I don't necessarily disagree with you, but imo it definitely matters how the problem is worded and presented, or if it is otherwise made clear what type of work will be accepted. Silly examples: suppose someone disproves the Riemann hypothesis through a computer search which finds a zero-crossing counter-example. Their counterexample is not a 'wrong' answer, even though they have essentially just done a more complicated version of 1^3 = 1, 2^3 = 8, ... and merely providing whatever computer code they used would probably be accepted by anyone. Example in the other direction might be the original four-color-theorem proof, which was partially by exhaustive computer aided search.

View on HN

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.

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.

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

The question applies to the classroom setting we were talking about; teachers don't have access to supercomputers :P

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

Reply on news.ycombinator.com