3 ms·
If's its legit proof, they author should be able to explain why SAT2 is in P and SAT3 is NP-complete. That's my BS test.
by waynecochran 9y ago
If's its legit proof, they author should be able to explain why SAT2 is in P and SAT3 is NP-complete. That's my BS test.
- 21 9y agoWhy? Proving something doesn't mean we understand all implications of said proof or how to apply it to a particular situation. Think about non-constructive proofs.
- wolfgke 9y ago> Think about non-constructive proofs. To me it does not seem that the author of the paper uses weird "coffeinated" non-constructive proof arguments in it.
- waynecochran 9y agoIt's an important special case. You need some sort of filter for all the crazy submissions of potential proofs. I am not the only one who uses this problem as the filter.
- Chinjut 9y agoWhether or not this proof stands, this author, a tenured professor whose professional research is in this area, seems exceedingly likely to know this very standard material.
- kevinwang 9y agoWhat's a good explanation of that?
- lorenzhs 9y ago2SAT is boring because given a clause with one unfulfilled literal, you know the other literal must be satisfied. There's no choice to be made. This limits backtracking enormously. It can even be solved in linear time (although that's nontrivial)
- Serfuzz 9y agoRegardless of whether the proof is legit, the author should be able to explain that. It's undergrad CS after all.