2 ms·
Exactly. One of the most valuable things I ever learned in my philosophy classes was that when someone presents you with a valid proof of something (in this cas
by gwern 15y ago
Exactly. One of the most valuable things I ever learned in my philosophy classes was that when someone presents you with a valid proof of something (in this case 'NP-hard is intractable in general'), you have to check whether it is 'sound' - whether it actually applies to you or your beliefs or the material under discussion. The premises are conditions which may or may not be true, and you must check them. As Cook points out, often they don't apply.