Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Trudne problemy z rozszerzalnością
W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w trudny. Na przykład twierdzenie Koniga-Halla stwierdza, że ​​wszystkie sześcienne dwustronne wykresy można pokolorować …
1
Kolejny wariant PARTYCJI
Mam redukcję następującego problemu z partycją do pewnego problemu z planowaniem: Dane wejściowe: lista liczb całkowitych dodatnich w kolejności nie malejącej.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Pytanie: Czy istnieje wektor taki, że(x1,…,xn)∈{−1,1}n(x1,…,xn)∈{−1,1}n(x_1,\ldots,x_n)\in\{-1,1\}^n ∑i=1naixi=0and∑i=1naixi=0and\sum_{i=1}^na_ix_i=0\qquad\text{and} ∑i=1kaixi⩾0for all k∈{1,…,n}∑i=1kaixi⩾0for all k∈{1,…,n}\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\} Bez drugiego warunku jest to po prostu PARTYCJA, a więc NP-twardy. Ale drugi …
2
Możliwe do przewidzenia luki między złożonością drzewa decyzyjnego a „prawdziwą” złożonością
Tytuł jest trochę mylący: ale mam nadzieję, że pytanie nie brzmi: Grønlund and Pettie Nowa wynik pokazujący, że 3SUM ma tylko drzewo decyzyjne złożoność got me zastanawiasz się:O ( n3 / 2)O(n3/2)O(n^{3/2}) Czy istnieje prosty przykład problemu ze złożonością drzewa decyzyjnego ale który dopuszcza dolną granicę (w bardziej szczegółowym modelu) …
1
Funkcje jednokierunkowe w odniesieniu do różnych granic zasobów
Nieformalnie funkcje jednokierunkowe są definiowane w odniesieniu do algorytmów PTIME. Są obliczalne w czasie wielomianowym, ale nie są odwracalne w czasie wielomianowym średniego przypadku. Istnienie takich funkcji jest ważnym otwartym problemem w informatyce teoretycznej. Interesują mnie funkcje jednokierunkowe (niekoniecznie dla aplikacji kryptograficznych) zdefiniowane w odniesieniu do różnych granic zasobów. Takimi …
1
Jaka jest złożoność sprawdzenia, czy macierz można diagonalizować?
Biorąc pod uwagę macierzy A z racjonalnym pozycji. Jaką złożoność sprawdzenia A można diagonalizować?n×nn×nn\times nAAAAAA Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten problem? Wszelkie wskazówki / komentarze są mile widziane! Dzięki.
1
Formuła 3-CNF, która wymaga szerokości rozdzielczości
Przypomnijmy, że szerokość o rozdzielczości odrzucenia o wzorze CNF jest maksymalna liczba literałach w klauzuli występującego w . Dla każdego istnieją niezadowalające wzory w 3-CNF st. Każde odrzucenie rozdzielczości wymaga szerokości co najmniej .F.RRRfaFFw F F wRRRwwwfaFFfaFFwww Potrzebuję konkretnego przykładu niezadowalającej formuły w 3-CNF (tak małej i prostej, jak to …
1
Produkt pośredni
Problem podziału jest słabo NP-zupełny, ponieważ ma wielomianowy (pseudo-wielomianowy) algorytm czasowy, jeśli wejściowe liczby całkowite są ograniczone przez jakiś wielomian. Jednak 3-partycja jest silnym problemem NP-zupełnym, nawet jeśli wejściowe liczby całkowite są ograniczone przez wielomian. Zakładając, , Czy możemy udowodnić, że pośrednie problemy NP-zupełne muszą istnieć? Jeśli odpowiedź brzmi „tak”, …
2
Czy istnienie całkowitego problemu wyszukiwania
Łatwo zauważyć, że jeśli to istnieją całkowite N P problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa).N P ∩ c o N P ≠ PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}N P.NP\mathsf{NP} Czy odwrotna jest również prawda, tj Czy istnienie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.