Unikalne testy porównawcze

To pytanie jest prawdopodobnie na granicy między tematem i nie na temat, jednak widziałem tutaj podobne pytania, dlatego zadam to pytanie.

Ja realizacji Unikalny $k$ -sat solver, którego wejście jest $k$ wzór -cnf o co najwyżej $1$ spełniająca zadania. Aby przetestować jego praktyczne zachowanie, potrzebuję zestawu takich formuł. Szukałem ich w Internecie i nic nie znalazłem (podczas gdy z drugiej strony bardzo łatwo jest znaleźć pakiety zwykłych formuł $k$ CNN).

Gdzie mogę znaleźć unikalne instancje $k$ SAT?

Ewentualnie z przyjemnością znałbym również każdą procedurę generowania wyjątkowo satysfakcjonujących instancji. Jedyne znane mi podejście to generowanie obsadzonych instancji SAT : losowo generujesz przypisanie $n$ zmiennych, a następnie generujesz tylko te klauzule, które zgadzają się z takim przypisaniem. Podejście to jest niezadowalające dla moich celów z następujących powodów:

• Otrzymany wzór może mieć dalsze niepożądane, satysfakcjonujące zadania.
• Aby upewnić się, że formuła jest wyjątkowo spełniona przez pożądane przypisanie, należy wprowadzić wszystkie możliwe klauzule, które się z nią zgadzają. W ten sposób powstałyby formuły ze zbyt wieloma klauzulami, które prawdopodobnie będą łatwe do rozwiązania, a zatem nie będą reprezentatywne dla najgorszego zachowania solvera. Nie jest dla mnie oczywiste, w jaki sposób możemy skutecznie wymusić wyjątkowość, zachowując rozsądną liczbę klauzul.

Jak możemy wygenerować wyjątkowo satysfakcjonujące formuły z rozsądną liczbą klauzul? Przez rozsądny rozumiem daleki od maksymalnego .$2^k \cdot {n \choose k}$

Oto jeden ze sposobów wygenerowania unikalnej instancji SAT, biorąc pod uwagę instancję SAT φ , o której wiesz, że jest zadowalająca. Rozważ wzór ψ ( x $k$$\varphi$$\psi(x)$ podany przez

gdzie jest funkcją skrótu, która odwzorowuje przypisanie x na wartość k- bitową (dla niektórych małych wartości k ), a y jest losową wartością k- bit. Jeśli φ ma około 2 k spełniających zadania, to (heurystycznie) zakładamy, że ψ będzie miało dokładnie jedno zadowalające zadanie (ze stałym prawdopodobieństwem). Możemy sprawdzić, czy tak jest, używając solwera SAT (a mianowicie sprawdzić, czy iable jest zadowalające; jeśli tak, a x 0 jest zadowalające). Jeśli k nie jest znane, możesz znaleźć $h$$x$$k$$k$$y$$k$$\varphi$$2^k$$\psi$$\psi$$x_0$ to jedno zadowalające przypisanie, przetestuj, czy $\psi(x) \land x \ne x_0$$k$$k$ za pomocą wyszukiwania binarnego lub po prostu iterując po każdej wartości kandydującej (gdzie n jest liczbą zmiennych boolowskich w $k=1,2,\dots,n$$n$$x$ ).

Możesz dowolnie wybierać funkcję skrótu. Prawdopodobnie będziesz chciał uczynić to tak prostym, jak to możliwe. Jeden niezwykle prosta konstrukcja jest posiadanie wyłowić losowy podzbiór k bitów z x . Nieco bardziej zaawansowaną konstrukcją jest, aby i- ty bit h ( x ) był xor dwóch losowo wybranych bitów z x (wybranie osobnej pary pozycji bitów dla każdego i , niezależnie). Utrzymanie h prosty zachowa ψ stosunkowo prosta.$h$$k$$x$$i$$h(x)$$x$$i$$h$$\psi$

Ten rodzaj transformacji jest czasem używany / sugerowany, jako część schematu szacowania liczby spełniających przypisań do formuły $\varphi$ ; Dostosowałem go do twoich potrzeb.

W Internecie można znaleźć wiele stanowisk testowych instancji SAT i zastosować tę transformację do wszystkich, aby uzyskać kolekcję unikalnych instancji SAT.$k$

Inną możliwością byłoby wygenerowanie unikatowych instancji SAT z kryptografii. Załóżmy na przykład, że f : { 0 , 1 } n → { 0 , 1 } n jest kryptograficzną kombinacją jednokierunkową. Niech x będzie losowo wybranym elementem { 0 , 1 } n , a niech y = f ( x ) . Zatem wzór φ ( x ) podany przez f ( x y jest unikalny$k$$f:\{0,1\}^n \to \{0,1\}^n$$x$$\{0,1\}^n$$y=f(x)$$\varphi(x)$$f(x)=y$$k$ -SAT instance. Jako inny przykład wybierz losowo dwie duże liczby pierwsze i niech n = p q . Zatem wzór φ ( x , y ) podany przez x ⋅ y = n ∧ x > 1 ∧ y > 1 ∧ x ≤ y (z oczywistą korelacją między łańcuchami bitów a liczbami całkowitymi) jest unikalny$p,q$$n=pq$$\varphi(x,y)$$x \cdot y = n \land x>1 \land y>1 \land x \le y$$k$-Sat wystąpienie. Jednak te konstrukcje nie wydają się użytecznym sposobem na porównanie lub optymalizację twojego solvera. Wszystkie mają specjalną strukturę i nie ma powodu, aby sądzić, że ta struktura reprezentuje rzeczywiste problemy. W szczególności instancje SAT wyciągnięte z problemów kryptograficznych są niezwykle trudne, o wiele trudniejsze niż instancje SAT pochodzące z wielu innych rzeczywistych aplikacji solverów SAT, więc nie są one bardzo dobrą podstawą do testowania twojego solvera.

Ogólnie rzecz biorąc, wszystkie techniki wymienione w tej odpowiedzi mają tę wadę, że generują Unikalne $k$ instancje SAT o określonej strukturze, więc mogą nie być tym, czego szukasz - a przynajmniej nie chcieć polegać wyłącznie na podstawie formuł wygenerowanych w ten sposób. Lepszym podejściem byłoby zidentyfikowanie aplikacji Unique -SAT (kto Twoim zdaniem zamierza użyć twojego solvera i do jakiego celu?), A następnie spróbować uzyskać realistyczne przykłady z tych domen aplikacji.$k$

W pokrewnym temacie zobacz także Generowanie interesujących problemów optymalizacji kombinatorycznej

Możesz rozważyć algorytmy używane do generowania łamigłówek Sudoku - prawdopodobnie uogólnione $n \times n$ - since (usually) Sudoku puzzles are supposed to have a unique solution. On the other hand, Sudoku puzzles are also usually guaranteed to have at least one solution... But finding that solution could still be a good benchmark for your solver.

You might use a Sudoku-generator together with a reduction to SAT, or you might think about how to apply the techniques used in Sudoku generation to more directly generate Unique SAT instances. For the former, obviously your SAT instances will have some structure, but it's unclear to me whether it's more or less structure than e.g. planting a solution or using the witness isolation technique. Probably depends on your needs and your solver.

Jedyne znane mi odniesienie to: Sudoku Puzzles Generating: from Easy to Evil.

$\Theta(n)$ constraints and then convert them to 3SAT instances.

imho one of the best ways to create "presumably hard" SAT instances while controlling the number of solutions is from integer factoring instances/circuits encoded in binary. the code is not very complex, it uses mainly EE addition circuits, and does not lead to "large" SAT instances. the number of solutions is equal to the number of factors (including "permutations" of the factors). therefore prime numbers generate exactly two solutions, $(1,p),(p,1)$. a single solution can be guaranteed with a further "comparison" constraint that restricts the factors to $a<b$ or that $a \neq 1$ or $b \neq p$.

also with this approach is it is relatively easy to find numbers with roughly however many factors/solutions are desired. the "smoother" the number, the more factors.

various researchers over the years have created this factoring SAT code (eg for DIMACS competition/arcihve which has stored some factoring instances in the past) but unfortunately there does not seem to be a publicly available version. see also the 1st link below for a ref where the code was written/implemented apparently for a graduate course.

• Reducing the integer factorization problem to an NP-Complete problem
• Generating 3SAT circuit for Integer factorization example

another empirical/iterative approach that may be useful for some, to create more "unstructured" instances: create random SAT instances $e_n$ near the transition point (the region where the equation has a probability 50% between "solvable and unsolvable"), and then solve the equation. if it is unsolvable, throw away and restart. if it is solvable, add clauses that restrict the solution "not" to be the found solution, obtaining $e_{n+1}$, and re-solve. repeat if necessary. when the equation $e_{n+1}$ is no longer solvable, the $e_n$ must have had a single/unique solution.

You can easily generate directly Unique SAT formulas with reasonable size $(|F|<n+2^k)$

Let $m$ be the unique model - say $m$ contains only "0"s (rename the variables later if needed).
Let $F$ a $k$-SAT formula satisfied only by $m$ - the maximum size of $F$ is the total number of clauses satisfied by $m$ i.e. $(2^k-1) \binom{n}{k}$.

Take the $\binom{k}{1}$ clauses that eliminate all models assigning exactly one "1" among $x_1,x_2 \ldots x_k$:
$(\lnot x_1, x_2 \ldots x_k)(x_1, \lnot x_2 \ldots x_k)\ldots (x_1,x_2 \ldots \lnot x_k)$

Take the $\binom{k}{2}$ clauses that eliminate all models assigning exactly two "1" among $x_1,x_2 \ldots x_k$:
$(\lnot x_1, \lnot x_2, x_3 \ldots x_k)(\lnot x_1,x_2, \lnot x_3 \ldots x_k)\ldots (x_1,x_2 \ldots \lnot x_{k-1} \lnot x_k)$

Keep going until taking the only $\binom{k}{k}$ clause that eliminates all models assigning "1" to each variables among $x_1,x_2 \ldots x_k$.

The only models which are not yet eliminated assign all $x_1,x_2 \ldots x_k$ to "0". Since $m$ is a model, then take any set of $n-k$ clauses that eliminate all models assigning "1" to $x_i (k<i\leq n)$ and $0$ to any $k-1$ variables among $x_1,x_2 \ldots x_k$, for instance:
$(\lnot x_{k+1}, x_1 \ldots, x_{k-1}) \ldots (\lnot x_n, x_1 \ldots x_{k-1})$.

Then $|F|=\sum_{i=1}^k \binom{k}{i} +n-k = 2^k-1+n-k$

To get more clauses, add any clause containing at least one negated variable. To get an unsatisfiable formula, just add a clause with $k$ unnegated variables.