On Feasibly Solving NP-Complete Problems

EasyChair Preprint 11063, version 1

Abstract

NAE-3SAT 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. NAE-3SAT remains NP-complete 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 NP-complete 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 NP-complete 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

@booklet{EasyChair:11063,
  author    = {Frank Vega},
  title     = {On Feasibly Solving NP-Complete Problems},
  howpublished = {EasyChair Preprint 11063},
  year      = {EasyChair, 2023}}