W innym wątku Joe Fitzsimons zapytał o „najlepsze obecne dolne granice 3SAT”. Chciałbym pójść w drugą stronę: jakie są najlepsze obecne górne granice 3SAT? Innymi słowy, jaka jest złożoność czasowa najbardziej wydajnego solvera SAT? W szczególności, czy można sobie wyobrazić algorytm...
To pytanie dotyczy złożoności obwodu. (Definicje znajdują się na dole). Yao Beigel-Tarui wykazała, że każdy C C 0 rodziny obwód wielkość y jest równoważny rodziny obwodu o rozmiarze s s O l r ( log s ) głębokości dwóch , w którym brama wyjściowa jest funkcją symetryczną, a drugi etap składa od N D...
Stosując algorytm przenoszenia patrzeć w przyszłość możemy obliczyć dodatek za pomocą wielomianu głębokość rozmiar 5 (lub 4?) C 0 rodzinę obwodu. Czy można zmniejszyć głębokość? Czy możemy obliczyć dodanie dwóch liczb binarnych przy użyciu wielomianowej rodziny obwodów o głębokości mniejszej niż...
Rozumiem, że kompletność Turinga wymaga nieograniczonej pamięci i nieograniczonego czasu. Jednak w tej usłudze jest skończona ilość atomów, co ogranicza pamięć. Na przykład, chociaż jest irracjonalne, nie ma sposobu na przechowywanie więcej niż pewnej liczby cyfr, nawet jeśli do tego celu zostały...
Niech G będzie drzewem na 2n wierzchołkach. Szerokość grzbietu G, tw (G) = 1. Załóżmy teraz, że dodajemy n krawędzi do G, aby uzyskać wykres H. Łatwa górna granica na tw (H) wynosi n + 1. Czy jest to w zasadzie najlepszy możliwy? Wydaje się, że tw (H) powinno być O (sqrt (n)), ale jest to tylko...
Rozważ następujący prosty model obwodu monotonicznego: każda bramka jest tylko binarnym OR. Jaka jest złożoność funkcji f ( x ) = A x,f(x)=Axf(x)=Ax gdzie AAA jest logiczną macierzą n × nn×nn \times n z O ( n )O(n)O(n) 0? Czy można to obliczyć za pomocą obwodów OR o rozmiarach liniowych? Bardziej...
Chciałbym poznać aktualny stan przejścia fazowego dla losowego k-sat, biorąc pod uwagę n zmiennych i klauzul m, co jest najlepiej znanym c = m / n dla górnych i dolnych
Załóżmy, że rozważamy 3-SAT ze zmiennymi i klauzulami c . Badam metodę, która wydaje się zajmować czas / przestrzeń O ( v 2 + log c ) w celu rozwiązania dowolnego problemu SAT pasującego do tego opisu, z błędem, który można dostosować do dowolnej kwoty. Jest jednak pewien haczyk.vvvdoccO ( wer2 +...
Czy problem CNF SAT NP jest trudny, gdy całkowita liczba (ale nie szerokość) klauzul 3-lub więcej-terminowych jest ograniczona stałą? A co powiesz konkretnie, kiedy istnieje tylko jedna taka
Pozwolić xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} dla i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}, z obietnicą, że x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (gdzie suma się skończyła ZZ\mathbb{Z}). Jaka jest złożoność ustalenia, czyx=1x=1x = 1? Zauważ, że w trywialny sposób...