Przełączanie bitów

Załóżmy, że mamy pole n bitów i k funkcji f_1, …, f_k, z których każda „przełącza” (neguje) jakiś niepusty podzbiór bitów. Chcemy móc przejść z jakiegoś zadanego stanu początkowego na stan z samymi zerami/jedynkami — chcemy wiedzieć, czy w ogóle istnieje taka kombinacja wywołań funkcji, żeby to osiągnąć; oraz chcemy móc znajdować rozwiązanie optymalne w sensie minimalizacji wywołań tych funkcji.

Jak nazywa się tego typu problem? Za czym góglać?

EDYCJA: alternatywnie, mamy k n-wymiarowych wektorów nad Z2 i szukamy zerowej/jednostkowej kombinacji liniowej.

CNF-SAT albo bardziej ogólnie https://en.wikipedia.org/wiki/Boolean_satisfiability_problem a przynajmniej jakaś wariacja na ten temat.
Jak chcesz to rozwiązać dla jakiegoś konkretnego, małego problemu, to pewnie Z3 sobie poradzi.

Można by to też sprowadzić do Subset-Sum w Z(2) -> niech każda funkcja f_i przedstawia n bitowy wektor gdzie 1 ma flipowany bit. Chcemy znaleźć podzbór takich f_i które po zsumowaniu w Z(2) (czyli po prostu xorowaniu) da nam wektor identyczny z twoim początkowym.

edit: To by się dało zrobić gdyby wśród tych twoich k funkcji istaniało n niezależnych liniowo, bo wtedy masz bazę tej przestrzeni i można z nich złożyć cokolwiek.

Może czegoś nie zrozumiałem, ale wydaje mi się, że to co chcesz osiągnąć, to rozwiązywać równania macierzowe x*A=b, gdzie nośnikiem (ciałem nad którym wykonujemy operacje) jest Z_2. Można to zrobić w czasie sześciennym względem większego z wymiarów A, za pomocą eliminacji Gaussa.
Przykładowy kod w Sagemath:

n = liczba_bitow
k = liczba_funkcji
F = Zmod(2)
VF = VectorSpace(F, n)
A = Matrix([VF.random_element() for _ in range(k)]) # losowe funkcje
b = vector(F, [0]*n) # wszystkie zera
x = A.solve_left(b)
print(x)
b = vector(F, [1]*n) # wszystkie jedynki
x = A.solve_left(b)
print(x)

Althorion napisał(a):

Załóżmy, że mamy pole n bitów i k funkcji f_1, …, f_k, z których każda „przełącza” (neguje) jakiś niepusty podzbiór bitów. Chcemy móc przejść z jakiegoś zadanego stanu początkowego na stan z samymi zerami/jedynkami — chcemy wiedzieć, czy w ogóle istnieje taka kombinacja wywołań funkcji, żeby to osiągnąć; oraz chcemy móc znajdować rozwiązanie optymalne w sensie minimalizacji wywołań tych funkcji.

Nie wiem, jak to się nazywa, ale deklaratywnie wydaje się proste. O ile dobrze rozumiem, to masz n-wymiarowy wektor początkowy i każda funkcji robi xor wejścia z n-wymiarowym wektorem liczb binarnych (z co najmniej jednym niezerowym elementem). W takim razie szukasz szukasz takiej sumy f_1, ..., f_k, żeby każdy z elementów wynikowego wektora miał odpowiednią parzystość (zależną od Twojego początkowego wektora). Ergo, liczysz sumę iloczynów b_1 * f_1 + b_2 * f_2 + ... + b_n * f_n gdzie b_k oznacza, czy bierzesz k-tą funkcję do sumy. Następnie minimalizujesz sumę b_1 + b_2 + ... + b_n.

W ILP bez problemu, bo b_1 * f_1 jest wektorem koniunkcji zmiennych binarnych, parzystość da się w miarę łatwo zapisać przy pomocy mnożenia lub rozkładu wynikowego elementu wektora na poszczególne bity.

Na oko coś takiego:

public static void Start() {
	var solver = new CplexMilpSolver(10);
	
	var initialVector = new int[] {1, 0, 1, 0};
	var functions = new int[][] {
		new int[]{1, 0, 0, 0},
		new int[]{0, 0, 1, 0},
		new int[]{1, 0, 1, 0}
	};
	
	var whichToTake = Enumerable.Range(0, functions.Length).Select(i => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();
	
	for(int i=0;i<initialVector.Length;++i){
		IVariable[] componentInputs = whichToTake.Select((b, j) => solver.Operation(OperationType.Conjunction, solver.FromConstant(functions[j][i]), b)).ToArray();
		IVariable componentSum = solver.Operation(OperationType.Addition, componentInputs);
		IVariable remainder = solver.Operation(OperationType.Remainder, componentSum, solver.FromConstant(2));
		solver.Set(ConstraintType.Equal, solver.FromConstant(initialVector[i]), remainder);
	}
	
	
	var goal = solver.Operation(OperationType.Addition, whichToTake);
	solver.AddGoal("Goal", solver.Operation(OperationType.Negation, goal));
	solver.Solve();
	
	for(int i=0;i<whichToTake.Length;++i){
		Console.WriteLine(i + " - " + solver.GetValue(whichToTake[i]));
	}
}