3 ms·
An NP-hard problem is still possible to be solved. Impractical but possible. An undecideable solution cannot be proven true.
by raverbashing 8y ago
An NP-hard problem is still possible to be solved. Impractical but possible.
An undecideable solution cannot be proven true.
- pfortuny 8y agoYes but there are very fee practical instances of undecidable problems (by instance I mean a specific concrete here-are-the-numbers problem, not a general statement about “equations”).
- pas 8y agoAre there any at all? If you have exact numbers you can decide in finite time. Always, if I'm not mistaken. So, unless there is an infinity encoded in the exact problem somehow, you can always solve it by simple brute force enumeration. Look at the busy beaver, it's completely possible theoretically to simply enumerate all the possible states of a tape for a given N, and play the corresponding Turing machines. Even if calculating this is physically impossible, and proven to be impossible to generalize for any N. (That is the BB functions are uncomputable, but of course not exact values.)
- pfortuny 8y agoGödel’s sentence comes to mind. Yes, it is not “practical” but it is undecidable.
- pas 8y agoGodel's sentence is not an exact problem. It's a big number representing a claim (a theorem) about Godel numbers and the sentence itself. There's nothing to calculate there. It's a proof by construction for Godel's incompleteness theorem.
- threatofrain 8y agoA non-computable problem might still be practically "better" because its solution might be approximated precisely and more cheaply, such as the approximation of a real number.