2
$\begingroup$

If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time.

If we have an $n$-variable degree $2$ system how many constraints do we need to ascertain whether there exists a $0/1$ solution in polynomial time? What is the condition analogous to rank? Are there any standard algorithms? What is best known complexity?

$\endgroup$
2
  • 1
    $\begingroup$ Are the coefficients integers? $\endgroup$
    – S. Carnahan
    Commented Jan 10, 2016 at 5:05
  • $\begingroup$ @S.Carnahan integer coefficients. $\endgroup$
    – Turbo
    Commented Jan 10, 2016 at 6:13

1 Answer 1

1
$\begingroup$

EDIT Arbitrary large number of equations doesn't guarantee you polynomial time neither for the linear, nor for the quadratic system.

Take hard to solve linear or quadratic system.

Add arbitrary integer linear combinations of the equations.

You can add unbounded number of equations, but this does give you any new information and doesn't change the rank of the linear system.


Partial answer. Since you essentially detect unique linear solutions and it is NP-complete, likely you can't hope for better for quadratic.

This is modification for overdetermined systems over finite fields.

Over $0/1$ we have $x^2=x$, so replace all $x^2$ with $x$, maybe giving some linear terms.

Try "monomial linearization". Replace each $x_i x_j$ by new variable $y_{ij}$ having in mind $x_i x_j=x_j x_i$ and keep the linear monomials.

This is linear system in at most $A=n(n-1)/2+n$ variables.

So if you have $A$ or more equations, you can hope for unique solution.

If unique solution exists over integers, first fix the linear variables (if any).

If a $0/1$ solution exists, the unique solution must be of the form $a y_{ij}=0$ or $a y_{ij}=a$ and the latter cases fixes $x_i,x_j=1$, while in the former all non-fixed to $1$ variables are zero.

Likely this will work for randomly generated quadratic instances, possibly showing no solution.

$\endgroup$
5
  • 1
    $\begingroup$ making $y_{ij}=y_{ji}$ still leaves dependency among variables also checking a rank $n$ $n\times n$ system has a $0/1$ assignment is trivial. $\endgroup$
    – Turbo
    Commented Jan 10, 2016 at 19:45
  • $\begingroup$ @Turbo Of course there are dependencies. I don't claim this is universal, but you want polynomial time. The linear system with $y_{ij}$ is solved over the integers and it might have integer solutions, leading to $0/1$. As I wrote, I need unique solution of the bigger linear system (like you do in the linear case). $\endgroup$
    – joro
    Commented Jan 11, 2016 at 5:44
  • $\begingroup$ @Turbo I edited. Arbitrary large number of equations doesn't guarantee you polynomial time neither for the linear, nor for the quadratic system. $\endgroup$
    – joro
    Commented Jan 11, 2016 at 6:15
  • $\begingroup$ if you have $n$ equations that form a full rank system it is trivial to test (just solve the linear system using Gaussian elimination and check if it is $0/1$). $\endgroup$
    – Turbo
    Commented Jan 12, 2016 at 4:51
  • $\begingroup$ @Turbo Yes, this is true. But arbitrary many equations doesn't mean full rank as I wrote. So the answer to "how many equations are needed for quadratic" is clear as explained. $\endgroup$
    – joro
    Commented Jan 12, 2016 at 5:30

You must log in to answer this question.