"For a SAT problem involving variables $x_i\\in [0, 1], 1\\leq i\\leq N$ and clauses $C_j, 1\\leq j\\leq M$ (with $C_{ji} = 1$ if $x_i$ appears positively in $C_j$, $C_{ji} = -1$ if $x_i$ appears negatively, and $0$ otherwise), we will define our energy function as a sum of squares of sub-energies for each clause.\n",

"\n",

"$$E = \\sum_{1\\leq j\\leq M}K_m^2$$\n",

"$$E = \\sum_{1\\leq j\\leq M}K_j^2$$\n",

"\n"

]

},

...

...

@@ -1484,11 +1484,11 @@

"cell_type": "markdown",

"metadata": {},

"source": [

"## Question 5) Write $K_m$\n",

"## Question 5) Write $K_j$\n",

"\n",

"Define (formally) $K_m$ as a function of the $C_ji$ and of the $x_i$, such that $K_m = 0$ iff clause $m$ is satisfied, and $K_m = 2^N$ if all $N$ variables appear in clause $m$ and are currently at the wrong value.\n",

"Define (formally) $K_j$ as a function of the $C_{ji}$ and of the $x_i$, such that $K_j = 0$ iff clause $j$ is satisfied, and $K_j = 2^N$ if all $N$ variables appear in clause $j$ and are currently at the _wrong_ value.\n",

"\n",

"One might want to define $s_i\\in[-1, 1]$ as a function of $x_i\\in[0, 1]$ for ease of writing."

"One might want to define $s_i\\in[-1, 1]$ as a function of $x_i\\in[0, 1]$ and then $K_j$ as a function of the $s_i$ for ease of writing."

]

},

{

...

...

@@ -1689,7 +1689,7 @@

"source": [

"## Question 8) Improving the search\n",

"\n",

"To avoid getting stuck in some local minima, we can add *Lagrange multipliers* $a_j, 1\\leq j\\leq M$.\n",

"To avoid getting stuck in some local minima, we can add *Lagrange multipliers* $a_j, 1\\leq j\\leq M$ so that the energy becomes $$E = \\sum_{1\\leq j\\leq M}a_j K_j^2$$\n",

"These are new variables that will have an exponential increase proportional to $K_j$.\n",

"\n",

"Add the 3 new variables and their ODEs with `add_ode`.\n",