Download PDFOpen PDF in browserOn Feasibly Solving NPComplete ProblemsEasyChair Preprint 11063, version 25 pages•Date: October 23, 2023AbstractONEINTHREE 3SAT consists in knowing whether a Boolean formula $\phi$ in $3CNF$ has a truth assignment such that each clause contains exactly one true literal or exactly two true literals. $\textit{ONEINTHREE 3SAT}$ remains $\textit{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 $\textit{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 $\textit{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
