A Critique of Kumar's "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications on P versus NP problem."

2021/12/11 by Michael C. Chavrimootoo, Chavrimootoo, Michael C., Henry B. Welles +1
Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2112.06062

openalex publication_date 2021/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we analyze the argument made by Kumar in the technical report "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications on P versus NP problem." The paper claims to present a polynomial-time algorithm that decides CNF-SAT. We show that the paper's analysis is flawed and that the fundamental underpinning of its algorithm requires an exponential number of steps on infinitely many inputs.

Related

• Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and its Implications on P versus NP problem
• Complexity of the CNF-satisfiability problem
• Polynomial Time Algorithm for Boolean Satisfiability Problem
• A New Approach to CNF-SAT From a Probabilistic Point of View
• A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT