4 ms·
The prize should be awarded for either finding a solution, or proving that no solution exists.
by m_eiman 15y ago
The prize should be awarded for either finding a solution, or proving that no solution exists.
- JonnieCache 15y agoYes. The two eventualities are equivalent for this purpose. Obviously the non-existence of a solution might itself be unprovable, so you'd still have to set some time limit. Oh Gödel, always there to ruin our plans.
- jules 15y agoObviously if no solution exists then that fact is also provable, since this is a finite problem. The problem is not that it might not be provable. The problem is that verifying a non-existence proof could be hard, because such a proof would probably be something like "I ran my solver for three weeks and it said that there are no solutions".