2
$\begingroup$

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem we have a solution then it means the problem has a question. For example we can transform the problem of MAx-Clique to the following set of polynomials

$P=\{x_i^2-x_i, x\in [n]\}\cup \{x_ix_j, (i,j)\notin E\}$

I want to know there is any list of problems like this? If you know any paper or book such that there lots of problems like the above one which can transform it to set of polynomials please let me know and have it.

$\endgroup$
  • 3
    $\begingroup$ Every problem in NP can be written like this. For the proof, reduce 1-in-3-SAT to this problem. $\endgroup$ – Yuval Filmus Feb 7 at 4:20
2
$\begingroup$

We all know that 3SAT is NP-complete. Here is how to reduce 3SAT to your problem.

Suppose that the 3SAT instance has variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. The new instance will have variables $x_1,\ldots,x_n,y_1,\ldots,y_m,z_1,\ldots,z_m$, and the following polynomials:

  • $x_i^2 - x_i$ for each $i \in [n]$ and $y_j^2 - y_j, z_j^2 - z_j$ for each $j \in [m]$.
  • For a clause $C_\ell$ of the form $x_i \lor x_j \lor x_k$: $x_i + x_j + x_k - y_\ell - z_\ell - 1$.
  • If a clause has negated variables, say $x_i$ appears as $\overline{x_i}$, then replace $x_i$ with $1-x_i$ in the polynomial stated above.

Why does this work, the first type of polynomials constrain all variables to be $0,1$. The polynomial $x_i + x_j + x_k - y_\ell - z_\ell - 1$ states that $x_i + x_j + x_k = 1 + y_\ell + z_\ell$, and since $y_\ell,z_\ell$ occur only in this polynomial, this is the same as $1 \leq x_i + x_j + x_k \leq 3$, that is, $x_i + x_j + x_k \geq 1$, or equivalently, $x_i \lor x_j \lor x_k$.

$\endgroup$
  • $\begingroup$ Thank you, do you have any reference in which there are poly-time reduction of some NP problems to 3SAT? $\endgroup$ – GhD Feb 7 at 22:21
  • $\begingroup$ Cook’s theorem shows how to reduce any NP problem to 3SAT. $\endgroup$ – Yuval Filmus Feb 8 at 3:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.