Teoretyczne informatyka upper-bounds

8

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 subwykładniczy (a jednak super-wielomianowy) dla SAT?

43 cc.complexity-theory ds.algorithms sat upper-bounds

3

Charakterystyka stałej głębokości

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 …

40 cc.complexity-theory circuit-complexity upper-bounds

2

Czy dodawanie można przeprowadzić na głębokości mniejszej niż 5?

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ż uzyskana za pomocą algorytmu carry look forward?AC0AC0AC^0 Czy są …

21 cc.complexity-theory circuit-complexity lower-bounds upper-bounds

1

Jakie są granice obliczeń w tym wszechświecie?

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 użyte wszystkie atomy we wszechświecie.ππ\pi Jakie są zatem …

17 computability upper-bounds

2

Złożoność obwodu OR gęstego operatora liniowego

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? …

14 ds.algorithms circuit-complexity upper-bounds

2

Jak duża szerokość może mieć drzewo plus połowa jego krawędzi?

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ć …

14 upper-bounds treewidth

2

Czy Almost-2-SAT NP-hard jest trudny?

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 klauzula?

10 np-hardness sat upper-bounds

2

Czy obwody quasi-wielomianowe dla 3-SAT są banalne?

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 ( …

10 ds.algorithms sat upper-bounds

1

Jakie są obecnie najbardziej znane górne i dolne granice progu (nie) satysfakcji dla losowego k-sat i / lub 3-sat?

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 granic.

10 cc.complexity-theory sat lower-bounds upper-bounds phase-transition

2

Dokładna złożoność problemu w

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 leży problem ∩m≥2AC0[m]∩m≥2AC0[m]\cap_{m \geq 2}{\mathsf{AC}^0[m]} ponieważ x≡1modmx≡1modmx \equiv 1\bmod{m}iff . Pytanie brzmi: czy problem leży w ? …

9 reference-request complexity-classes circuit-complexity upper-bounds

Pytania otagowane jako upper-bounds