Download PDFOpen PDF in browserCurrent versionOn Feasibly Solving NPComplete ProblemsEasyChair Preprint 11063, version 15 pages•Date: October 9, 2023AbstractNAE3SAT consists in knowing whether a Boolean formula ϕ in 3CNF has a truth assignment such that for each clause at least one literal is true and at least one literal is false. NAE3SAT remains NPcomplete when all clauses are monotone. We create a polynomial time reduction which converts the monotone version into a bounded number of linear constraints on real numbers. Since the linear optimization on real numbers can be solved in polynomial time, then we can decide this NPcomplete problem in polynomial time. Certainly, the problem of solving linear constraints on real numbers is equivalent to solve the particular case when there is a linear optimization without any objective to maximize or minimize. If any NPcomplete can be solved in polynomial time, then we obtain that P = NP. Moreover, our polynomial reduction is feasible since it can be done in linear time. Keyphrases: Boolean formula, completeness, complexity classes, polynomial time
