arXiv:1101.2018cs.CC
The Complexity of 3SAT_N and the P versus NP Problem
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
We introduce the NP-complete problem 3SAT_N and extend Tovey's results to a classification theorem for this problem. This theorem leads us to generalize the concept of truth assignments for SAT to aggressive truth assignments for 3SAT_N. We introduce the concept of a set compatible with the P and NP problem, and prove that all aggressive truth assignments are pseudo-algorithms. We combine algorithm, pseudo-algorithm and diagonalization method to study the complexity of 3SAT_N and the P versus NP problem. The main result is P != NP.
Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 A list of articles published on the P=NP debate is here http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month…
chucknthemView on HNParent context