Pytania otagowane jako cc.complexity-theory

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

3
Zliczanie liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich?
Jest -hard znaleźć czynnik stały przybliżenie najdłuższego cyklu sześciennych Hamiltona wykresach. Sześcienne wykresy hamiltonowskie mają co najmniej dwa cykle hamiltonowskie.NPNPNP Jakie są najbardziej znane wartości górnej i dolnej granicy liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich? Biorąc pod uwagę sześcienny wykres hamiltonowski, jaka jest złożoność znalezienia liczby cykli hamiltonowskich? Czy …
2
Algorytmy SC ^ 2 dla łączności st
Savitch podał algorytm deterministyczny do rozwiązania łączności st przy użyciu przestrzeni , sugerując, że N L ⊆ D S P A C E ( log 2 n ) . Algorytm Savitcha działa w czasie . Poważnym otwartym problemem jest to, czy łączność st może zostać rozwiązana przez algorytm deterministyczny w …
2
Trudne problemy NP na grafach ekspanderów?
W prezentacji z 2006 r. Zatytułowanej WYKRESY EKSPANDERA - CZY POZOSTAJĄ ŻADNE TAJEMNICE? Nati Linial postawił następujący otwarty problem: Które -hard obliczeniowa problemu na wykresie pozostają trudne, gdy ogranicza się do wykresów ekspandera?NPNPNP Od tego czasu postęp poczyniono udowodnić taki wynik dla -hard problemu?NPNPNP
1
Czy dowody, że permanent nie jest w mundurze
Jest to kontynuacja tego pytania i jest związana z tym pytaniem Shivy Kinali. Wydaje się, że dowody w tych dokumentach ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) używają twierdzeń hierarchicznych. Chcę wiedzieć, czy dowody są „ czystymi ” twierdzeniami o diagonalizacji, czy też używają czegoś więcej niż zwykła diagonalizacja. Więc …
3
Czy są jakieś klasy funkcji, które wymagają obliczalnie różnych zasobów do obliczenia w porównaniu do obliczenia ich odwrotności?
Przepraszamy z góry, jeśli to pytanie jest zbyt proste. Zasadniczo chcę wiedzieć, czy są jakieś funkcje o następujących właściwościach:f(x)f(x)f(x) Weź na gdy domena i domena kodowa są ograniczone do ciągów bitowych. Następniefn(x)fn(x)f_n(x)f(x)f(x)f(x)nnn fn(x)fn(x)f_n(x) jest iniekcyjny fn(x)fn(x)f_n(x) jest przejmujący fn(x)fn(x)f_n(x) zajmuje znacznie mniej zasobów (albo przestrzeń / czas / głębokość obwodu …
6
Globalne właściwości klas dziedzicznych?
Dziedziczna klasa struktur (np. Wykresy) to taka, która jest zamknięta pod indukowaną podbudową, lub równoważnie, jest zamknięta pod usunięciem wierzchołków. Klasy wykresów, które wykluczają nieletnie, mają ładne właściwości, które nie zależą od konkretnej wykluczonej nieletniej. Martin Grohe wykazał, że dla klas grafów z wyłączeniem drobnych istnieje algorytm wielomianowy dla izomorfizmu, …
10
Nieprzerwalność problemów NP-zupełnych jako zasada fizyki?
Zawsze intryguje mnie brak danych liczbowych z matematyki eksperymentalnej za lub przeciw pytaniu P vs NP. Podczas gdy hipoteza Riemanna zawiera pewne dowody potwierdzające weryfikację numeryczną, nie znam podobnych dowodów na pytanie P vs NP. Ponadto nie jestem świadomy żadnych bezpośrednich konsekwencji dla świata fizycznego istnienia nierozwiązywalnych problemów (lub istnienia …
2
Czy APX jest zawarty w NP?
Mówi się, że problem P występuje w APX, jeśli istnieje pewna stała c> 0, tak że istnieje algorytm aproksymacji czasu wielomianowego dla P ze współczynnikiem aproksymacji 1 + c. APX zawiera PTAS (widoczne po prostu przez wybranie dowolnej stałej c> 0) i P. Czy APX jest w NP? W szczególności, …
1
vs
W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje parzystości problemy (zobacz to pytanie ), ale być …
5
Jaka jest klasa złożoności podprogramów kwantowych przyjmujących dowolne stany kwantowe jako dane wejściowe?
Klasa złożoności BQP odpowiada podprogramom kwantowym w czasie wielomianowym, przyjmującym klasyczne dane wejściowe i wyrzucającym probabilistyczny sygnał klasyczny. Porada kwantowa modyfikuje to, aby uwzględnić kopie niektórych z góry określonych stanów porady kwantowej, ale jak zwykle z klasycznymi danymi wejściowymi. Jaka jest klasa złożoności podprogramów kwantowych czasu wielomianowego przyjmujących dowolne stany …
2
Analogi kwantowe klas złożoności SPACE
Często rozważamy klasy złożoności, w których jesteśmy ograniczeni ilością miejsca, które może wykorzystać nasza maszyna Turinga, na przykład: DSPACE(f(n))DSPACE(f(n))\textbf{DSPACE}(f(n)) lub NSPACE(f(n))NSPACE(f(n))\textbf{NSPACE}(f(n)) . Wydaje się, że we wczesnej teorii złożoności odniesiono duży sukces z tymi klasami, takimi jak twierdzenie o hierarchii przestrzeni i tworzenie ważnych klas, takich jak LL\textbf{L} i PSPACEPSPACE\textbf{PSPACE} …
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.