<p>From what I can tell, you have proposed a (heuristic) algorithm for solving the Satisfiability Problem. But you have not given an argument for the correctness of your algorithm or an analysis of the asymptotic runtime, so this does not prove <span class="math-container">$P=NP$</span>.</p>
<p>Also, I want to make sure I understand your algorithm correctly. First, am I correct in assuming the statement is assumed to be in CNF? Next, I want to make sure I understand how you translate clauses to constraints. Consider the clause <span class="math-container">$(x_1 \lor \neg x_2 \lor \neg x_3 \lor x_4 \lor x_5)$</span>. Am I correct that this would correspond to the constraint <span class="math-container">$x_1 - x_2 - x_3 + x_4 + x_5 \geq -3$</span>? Finally, am I correct that, after each solve of the LP, you set some of the decision variable to <span class="math-container">$1$</span> or <span class="math-container">$-1$</span> (corresponding to &quot;true&quot; or &quot;false&quot;), and repeat this process until a satisfying assignment is found, or it can be determined that there is no satisfying assignment?</p>
<p>Assuming I am correct about the above, there are a few issues with your approach. First, the way you are translating clauses to constraints is incorrect. Looking at my example above, the constraint can be satisfied by setting all of the variables to 0. Indeed, for any clause of two or more literals the corresponding constraint is satisfied when all of the variables are 0. Second you claim, &quot;After the function is minized, some variables become within -1+eps or 1-eps ranges.&quot; But this it is possible that no variables are near -1 or +1. As such, it is not clear how too bound the number of iterations needed by your algorithm. It is not even clear your algorithm is guaranteed to terminate. Finally, is it not possible that in the only satisfying assignments, that a particular variable <span class="math-container">$x_k$</span> is set to -1, but the LP assigns a value close to 1 to a variable, and thus you round it up to 1. It seems your algorithm would incorrectly determine that this instance is unsatisfiable.</p>

CC BY-SA 4.0
2024-04-30T18:51:02.143Z
The objective function drives variable values to converge to 1 or -1, away from zeroes. If LP solver can't find a solution at some iteration, then the boolean formula is not satisfiable. Yes, I use CNF with DIMACS interface. Before each iteration, all variables receive initial values of +-1: e.g. I set them all to -1 (False) before the first iteration, and in the next iterations I set to False whatever's less than +0, and True for greater than -0. These values are just to warmup the LP solver - it can completely reassign the values. `eps` must be small enough to avoid wrong roundings.
Serge Rogatch
CC BY-SA 4.0
2024-04-30T18:52:59.927Z
About the bound on the number of iterations - I would try to prove it's divide and conquer, i.e. at least half of some options set is eliminated in each iteration.
Serge Rogatch
CC BY-SA 4.0
2024-04-30T19:10:39.827Z
In general, just because the objective function encourages solutions away from 0 doesn't guarantee that the optimal solution can't be relatively close to 0. If your choice of objective really does guarantee that at least one variable will be close to 1 or -1, you will need to provide a proof. Also, you will need to be able to determine an eps small enough that there will be no rounding errors, and you will need to be able to do that in polynomial time.
NaturalLogZ
CC BY-SA 4.0
2024-04-30T19:12:44.530Z
The solution is always maximally away from zero: every variable must receive a +1 or -1 standing for True or False.
Serge Rogatch
CC BY-SA 4.0
2024-04-30T19:35:37.310Z
I was referring to the LP specifically.
NaturalLogZ
CC BY-SA 4.0
2024-04-30T19:37:44.420Z
In LP, the objective function drives the solution away from zero: it drives the positive variables from the previous iteration towards +1, and drives negative variables from the previous iteration towards -1. I said this many times, in the post and in the comments.
Serge Rogatch
CC BY-SA 4.0
2024-04-30T18:41:14.457Z
2024-04-30T18:41:14.457Z
NaturalLogZ
<p>I've posted the full <a href="https://www.academia.edu/118325445/P_NP_a_reduction_of_Boolean_Satisfiability_problem_to_Linear_Programming_and_Long_Arithmetic" rel="nofollow noreferrer">article here</a>. The source code is <a href="https://github.com/srogatch/bsat-circulation/blob/lin-prog/CpuSolver.h" rel="nofollow noreferrer">available here</a>.</p>
<p>Basically, in the Linear Programming (LP) task, we solve a system of inequalities: one inequality per BSAT clause. In each inequality, put <code>+x[i]</code> if <code>i</code>-th boolean variable appears straight in this clause, and <code>-x[i]</code> if the variable appears negated. Each inequality has a lower bound to be satisfiable: <code>2-N[j]</code>, where <code>N[j]</code> is the number of variables in <code>j</code>-th inequality. We limit each variable to <code>-1 &lt;= x[i] &lt;= +1</code>.</p>
<p>We run multiple iterations of LP solving. In each iteration, we minimize the following function:</p>
<pre><code>f(x[0],..,x[N-1]) = sum( i, -x[i] * (4^(-i)) )
</code></pre>
<p>Obviously, to get any sensible precision for optimizing such a function, we need long arithmetic - with precision of at least <code>2*N</code> bits.
After the function is minized, some variables become within <code>-1+eps</code> or <code>1-eps</code> ranges. We consider such variables assigned <code>False</code> and <code>True</code> respectively. The other variables have <code>abs(x[i]) &lt; 1-eps</code> and we consider them unassigned.</p>
<p>Next, we reorder the variables so that <code>x[0]</code> becomes the one with the smallest absolute value, <code>x[1]</code> becomes the next smallest, etc., and in the end of the new order of variables there are assigned variables (whose <code>abs(x[i]) &gt;= 1-eps</code>).</p>
<p>We repeat the process from solving the LP task, with a warm start, temporarily assigning <code>True</code> to variables whose <code>x[i]&gt;-0</code> and <code>False</code> to variables whose <code>x[i]&lt;+0</code> (for those unfamiliar, machine arithmetic has signed zero - it distinguishes between <code>+0</code> and <code>-0</code>).</p>
<p>The solution is tested for 20 variables and base <code>4</code> as above - it converges in 2-3 iterations.
If we use base <code>2</code>, it converges in 3-4 iterations.
The solution also converges for 100 variables and base <code>1.1</code>, but it takes hundreds of iterations because variable assignments interfere with each other. I just don't yet have an LP solver with multi-precision (i.e. beyond the machine's <code>double</code> data type, which has only 53-63 bits of precision).</p>
<p>Do you see any flaws or counterexamples to this algorithm?</p>

<sat><linear-programming><reductions><p-vs-np><open-problem>
Can you find a counterexample / disprove my P=NP solution?
Serge Rogatch
# Can you find a counterexample / disprove my P=NP solution?

(Asked by: username_0 on 2024-04-30)

I've posted the full article here. The source code is available here.
Basically, in the Linear Programming (LP) task, we solve a system of inequalities: one inequality per BSAT clause. In each inequality, put +x[i] if i-th boolean variable appears straight in this clause, and -x[i] if the variable appears negated. Each inequality has a lower bound to be satisfiable: 2-N[j], where N[j] is the number of variables in j-th inequality. We limit each variable to -1 <= x[i] <= +1.
We run multiple iterations of LP solving. In each iteration, we minimize the following function:
f(x[0],..,x[N-1]) = sum( i, -x[i] * (4^(-i)) )

Obviously, to get any sensible precision for optimizing such a function, we need long arithmetic - with precision of at least 2*N bits.
After the function is minized, some variables become within -1+eps or 1-eps ranges. We consider such variables assigned False and True respectively. The other variables have abs(x[i]) < 1-eps and we consider them unassigned.
Next, we reorder the variables so that x[0] becomes the one with the smallest absolute value, x[1] becomes the next smallest, etc., and in the end of the new order of variables there are assigned variables (whose abs(x[i]) >= 1-eps).
We repeat the process from solving the LP task, with a warm start, temporarily assigning True to variables whose x[i]>-0 and False to variables whose x[i]<+0 (for those unfamiliar, machine arithmetic has signed zero - it distinguishes between +0 and -0).
The solution is tested for 20 variables and base 4 as above - it converges in 2-3 iterations.
If we use base 2, it converges in 3-4 iterations.
The solution also converges for 100 variables and base 1.1, but it takes hundreds of iterations because variable assignments interfere with each other. I just don't yet have an LP solver with multi-precision (i.e. beyond the machine's double data type, which has only 53-63 bits of precision).
Do you see any flaws or counterexamples to this algorithm?

**Tags:** sat, linear-programming, reductions, p-vs-np, open-problem


---

## 1 answers

### Answer by username_1 on 2024-04-30. Score: 3

From what I can tell, you have proposed a (heuristic) algorithm for solving the Satisfiability Problem. But you have not given an argument for the correctness of your algorithm or an analysis of the asymptotic runtime, so this does not prove $P=NP$.

Also, I want to make sure I understand your algorithm correctly. First, am I correct in assuming the statement is assumed to be in CNF? Next, I want to make sure I understand how you translate clauses to constraints. Consider the clause $(x\_1 \lor \neg x\_2 \lor \neg x\_3 \lor x\_4 \lor x\_5)$. Am I correct that this would correspond to the constraint $x\_1 - x\_2 - x\_3 + x\_4 + x\_5 \geq -3$? Finally, am I correct that, after each solve of the LP, you set some of the decision variable to $1$ or $-1$ (corresponding to "true" or "false"), and repeat this process until a satisfying assignment is found, or it can be determined that there is no satisfying assignment?

Assuming I am correct about the above, there are a few issues with your approach. First, the way you are translating clauses to constraints is incorrect. Looking at my example above, the constraint can be satisfied by setting all of the variables to 0. Indeed, for any clause of two or more literals the corresponding constraint is satisfied when all of the variables are 0. Second you claim, "After the function is minized, some variables become within -1+eps or 1-eps ranges." But this it is possible that no variables are near -1 or +1. As such, it is not clear how too bound the number of iterations needed by your algorithm. It is not even clear your algorithm is guaranteed to terminate. Finally, is it not possible that in the only satisfying assignments, that a particular variable $x\_k$ is set to -1, but the LP assigns a value close to 1 to a variable, and thus you round it up to 1. It seems your algorithm would incorrectly determine that this instance is unsatisfiable.

> **Comments:**
> **username_0**: The objective function drives variable values to converge to 1 or -1, away from zeroes. If LP solver can't find a solution at some iteration, then the boolean formula is not satisfiable. Yes, I use CNF with DIMACS interface. Before each iteration, all variables receive initial values of +-1: e.g. I set them all to -1 (False) before the first iteration, and in the next iterations I set to False whatever's less than +0, and True for greater than -0. These values are just to warmup the LP solver - it can completely reassign the values. `eps` must be small enough to avoid wrong roundings.  
> **username_0**: About the bound on the number of iterations - I would try to prove it's divide and conquer, i.e. at least half of some options set is eliminated in each iteration.  
> **username_1**: In general, just because the objective function encourages solutions away from 0 doesn't guarantee that the optimal solution can't be relatively close to 0. If your choice of objective really does guarantee that at least one variable will be close to 1 or -1, you will need to provide a proof. Also, you will need to be able to determine an eps small enough that there will be no rounding errors, and you will need to be able to do that in polynomial time.  
> **username_0**: The solution is always maximally away from zero: every variable must receive a +1 or -1 standing for True or False.  
> **username_1**: I was referring to the LP specifically.  
> **username_0**: In LP, the objective function drives the solution away from zero: it drives the positive variables from the previous iteration towards +1, and drives negative variables from the previous iteration towards -1. I said this many times, in the post and in the comments.  

---

