Computer Science – Logic in Computer Science
Scientific paper
2008-06-18
Computer Science
Logic in Computer Science
Submitted to the ACM Transactions on Computation Theory
Scientific paper
After examining the {\bf P} versus {\bf NP} problem against the Kleene-Rosser paradox of the $\lambda$-calculus [94], it was found that it represents a counter-example to NP-completeness. We prove that it contradicts the proof of Cook's theorem. A logical formalization of the liar's paradox leads to the same result. This formalization of the liar's paradox into a computable form is a 2-valued instance of a fuzzy logic programming paradox discovered in the system of [90]. Three proofs that show that {\bf SAT} is (NOT) NP-complete are presented. The counter-example classes to NP-completeness are also counter-examples to Fagin's theorem [36] and the Immermann-Vardi theorem [89,110], the fundamental results of descriptive complexity. All these results show that {\bf ZF$\not$C} is inconsistent.
No associations
LandOfFree
The Kleene-Rosser Paradox, The Liar's Paradox & A Fuzzy Logic Programming Paradox Imply SAT is (NOT) NP-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Kleene-Rosser Paradox, The Liar's Paradox & A Fuzzy Logic Programming Paradox Imply SAT is (NOT) NP-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Kleene-Rosser Paradox, The Liar's Paradox & A Fuzzy Logic Programming Paradox Imply SAT is (NOT) NP-complete will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-272493