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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Valerio Capraro Nov 1 '11 at 13:41
  • $\begingroup$ @ValerioCapraro Yes, each $x_i$ appears twice in my problem. Thanks, updated. $\endgroup$ – Bee San Nov 1 '11 at 13:44
  • $\begingroup$ Have you considered the possibility that your problem may be NP-complete? $\endgroup$ – Gerry Myerson Nov 2 '11 at 6:04
  • $\begingroup$ @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? $\endgroup$ – Bee San Nov 2 '11 at 7:28
  • $\begingroup$ 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. $\endgroup$ – Willie Wong Nov 2 '11 at 8:48
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Bee San Nov 1 '11 at 14:52
  • $\begingroup$ 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. $\endgroup$ – IIT Bombay Nov 1 '11 at 15:59
  • $\begingroup$ 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. $\endgroup$ – IIT Bombay Nov 1 '11 at 16:04
  • $\begingroup$ Fair enough, but I still need a deterministic algorithm that gives a guaranteed solution set/number of solutions. Thanks anyway. $\endgroup$ – Bee San Nov 2 '11 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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