3 ms·

If this were the situation I would agree with you, however an independent programmer has implemented his algorithm and posted it on github with instructions (ht

If this were the situation I would agree with you, however an independent programmer has implemented his algorithm and posted it on github with instructions (https://github.com/anjlab/sat3 https://github.com/anjlab/sat3) on how to run it on k-SAT instances. Because of this, I believe it increases the claim's reputability; it is easier to confirm or reject his algorithm and claim.

kenjackson 16y ago
First, it doesn't appear to be independent as the author on the blog says he/we prepared it. Second, doesn't mean much. It's almost as likely there's a bug in the code as in a proof. The only advantage is you can run some tets on it, but if it's wrong the tests may actually give you a false sense of security. Lastly, if you prove P=NP you submit to FOCS or STOC. Let them review it. Otherwise its just another Archimedes Plutonium.
- sonoffett 16y ago
  Perhaps you're right regarding the first point, I'm just going off what he states in the OP: "Also two independent versions of the algorithm in programming languages have been implemented." My point is that a constructivist proof that P=NP along with working code (again I'm assuming it's implemented correctly, as it appears vetted by Romanov) is easier to prove incorrect as it's easier for someone who perhaps doesn't have the theoretical background to find pathological examples where it breaks down (and a much wider audience fits in this category, including most of HN). I agree with your point about the false sense of security however--an inability to find such pathological cases is not sufficient to prove P=NP. In order to truly verify the claim a rigorous analysis of the proof will be necessary--but in this situation it's much easier to show what this guy is saying is false than in the Deolalikar case.

3 ms·

If this were the situation I would agree with you, however an independent programmer has implemented his algorithm and posted it on github with instructions (ht

by sonoffett 16y ago

kenjackson 16y ago
First, it doesn't appear to be independent as the author on the blog says he/we prepared it. Second, doesn't mean much. It's almost as likely there's a bug in the code as in a proof. The only advantage is you can run some tets on it, but if it's wrong the tests may actually give you a false sense of security. Lastly, if you prove P=NP you submit to FOCS or STOC. Let them review it. Otherwise its just another Archimedes Plutonium.
- sonoffett 16y ago
  Perhaps you're right regarding the first point, I'm just going off what he states in the OP: "Also two independent versions of the algorithm in programming languages have been implemented." My point is that a constructivist proof that P=NP along with working code (again I'm assuming it's implemented correctly, as it appears vetted by Romanov) is easier to prove incorrect as it's easier for someone who perhaps doesn't have the theoretical background to find pathological examples where it breaks down (and a much wider audience fits in this category, including most of HN). I agree with your point about the false sense of security however--an inability to find such pathological cases is not sufficient to prove P=NP. In order to truly verify the claim a rigorous analysis of the proof will be necessary--but in this situation it's much easier to show what this guy is saying is false than in the Deolalikar case.