W dniu 2013-05-12 18:23, A.L. pisze:

>
> Problem jest niekompletnie zdefiniowany i jako taki nie moze byc
> rozwiazany

http://en.wikipedia.org/wiki/Lights_Out_%28game%29
i odnośniki 2-4.


O, właśnie, Ty będziesz wiedział. Znalezienie jakiegokolwiek
rozwiązania jest wielomianowe, ale aby znaleźć rozwiązanie
optymalne trzeba rozwiązać jeszcze jeden prolbem. Obierajac
go z otoczki:

Mamy zero-jedynkowy wektor X długości L oraz k wektorów y_j
(tej samej długości).

Teraz bierzemy podzbiór {y_j} i wszytko (x i wybrane y_j) xorujemy
po współrzędnych (dadajemy modulo 2).

Problemem jest znalezienie podzbioru {y_j}, który da minimalną
liczbę jedynek (minimalną normę wektora, ponieważ 0-1, wszytko
jedno jaką).

Śmierdzi mi to NP-trudnym (tzn znlazłem jedynie algorytm wykladniczy
względem k:), ale pewności nie mam (dość podobne do dyskretnego
programowania liniowego, ale jednak zdecydowanie nie to samo).

Wiesz coś o takim problemie? Sformułowanie wygląda tak, jakby
było znane;)

pzdr
bartekltg