3
$\begingroup$

The problem:

I have a system of N linear equations, with K unknowns; and K > N. Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1.

Here's an example with N=11 equations and K=15 unknowns:

$1 = x_1 + x_9$
$2 = x_{1} + x_{2} + x_{10}$
$2 = x_{2} + x_{3} + x_{11}$
$2 = x_{3} + x_{12}$
$2 = x_{9} + x_{4} + x_{13}$
$2 = x_{10} + x_{4} + x_{5} + x_{14}$
$2 = x_{11} + x_{5} + x_{6} + x_{15}$
$2 = x_{12} + x_{6}$
$2 = x_{13} + x_{7}$
$2 = x_{14} + x_{7} + x_{8}$
$1 = x_{15} + x_{8}$

Things that will always hold true in the general case:

  • Every coefficient is $1$.
  • In the entire collection of equations, each $x_i$ appears exactly twice.
  • There are exactly two equations of the form $x_i + x_j = 1$.
  • All the other equations will have $2$ as the constant.

Some observations:

  • If you sum all of the above equations and divide both sides by $2$, you get $\sum_{i=1}^{i=K}x_i=N-1$. In this case,
    $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} = 10$.
    So, in any solution, there will be exactly N-1 1's and K-(N-1) 0's.

My Questions:

  • How many solutions does this general system have?
  • Is there a fast way to find these solutions?

FWIW, I encountered this problem when trying to find the longest (hamiltonian) path between two points in a square lattice.

  • 0
    I think that you have to assume the property in your observation. It seems to me that it is not implied by the other three properties. Maybe you want that any $x_i$ appears twice.2011-11-01
  • 0
    @ValerioCapraro Yes, each $x_i$ appears twice in my problem. Thanks, updated.2011-11-01
  • 0
    Have you considered the possibility that your problem may be NP-complete?2011-11-02
  • 0
    @GerryMyerson Yes, that is why I've asked whether there might be a fast way to find the solutions. Hopefully the **number** of solutions can be found fast enough?2011-11-02
  • 0
    Migration is not possible from MSE to MO, as MO is not part of the StackExchange platform. If you want to ask the question there, please go ahead, but please as a courtesy edit your question here to include the MO link and also include this page in your MO version.2011-11-02
  • 0
    Also posted to MO, http://mathoverflow.net/questions/79811/ where it is getting some answers, so I vote to close here.2011-11-02

2 Answers 2

1

Determining whether a Hamiltonian path exists is NP-complete, so a fast solution to your problem applied to all pairs of vertices would prove $P=NP$.

Therefore, you cannot expect a fast algorithm to count the solutions.

0

If you're looking for a fast method, neural networks might be the way to go, and it should be possible to write an algorithm that is general enough (i.e. will work for any set of equations satisfying the same basic conditions). Google around for Hopfield Neural Networks, which are often used for combinatorial problem like this one.

  • 0
    I need a deterministic algorithm, so I'd say neural networks are not the way to go. That said, could you elaborate on how NNs could be applied to this problem?2011-11-01
  • 0
    Hopfield Neural Networks are often used in graph theoretic problems, like finding the shortest route. You can find many papers online. The key idea will be to assume you have N neurons, each of which represents a variable (i.e x (1-10) as in your case). You'll then define an energy function that will be minimum when your solution is correct. Eg if V is the output of one neuron, then the energy function will have V(1-V) as a term. That will move the variable V to either 1 or 0 when it converges. Moving on, if x1+x2=2, then (x1+x2-2)^2 will go to zero in the correct solution.2011-11-01
  • 0
    When you have an energy function, there are standard algorithms to use it to find the difference to be introduced at each iteration. Usually HNNs work well and will give you the optimal result, and not an approximation.2011-11-01
  • 0
    Fair enough, but I still need a deterministic algorithm that gives a guaranteed solution set/number of solutions. Thanks anyway.2011-11-02