Pytania otagowane jako cc.complexity-theory

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

1
Równoważność dwóch definicji kompletności i solidności w interaktywnych systemach dowodowych
Kompletność i solidność w interaktywnych systemach dowodowych są nieformalnie definiowane jako: Kompletność: Jeśli stwierdzenie jest prawdziwe, szczery Prover może przekonać uczciwego weryfikatorem tego faktu WHP . Poprawność: jeśli oświadczenie jest fałszywe, oszust nie może przekonać uczciwego weryfikatora (o ważności fałszywego oświadczenia) Termin „bicz” jest albo interpretowany jako „z prawdopodobieństwem większym …
4
Czy diagonalizacja oddaje istotę separacji klasowej?
Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji diagonalizowanej maszyny Turinga. Oto kilka powiązanych pytań: Czy istnieją dowody separacji klas nieoparte na …
1
Jaka jest złożoność (być może zwięzłego) Nurikabe?
Nurikabe to układanka wypełniająca siatki oparta na ograniczeniach, luźno podobna do Saperów / Nonogramów; liczby są umieszczane na siatce, która ma być wypełniona wartościami włączania / wyłączania dla każdej komórki, przy czym każda liczba wskazuje region połączonych komórek „on” o tej wielkości, a także pewne drobne ograniczenia w obszarze komórek …
1
Złożoność przestrzeni dla średnich przypadków
Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją jakieś z analizą średnich przypadków (np. Granica jest zachowana, nawet jeśli algorytm jest dozwolony błądzić …
4
Klasa złożoności NEXP
Mam problem, który jest w NEXP NP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego).NPNP^{\text{NP}} Czy jest coś znanego na temat NEXP NP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne problemy niż ogólne (biorąc …
1
Dlaczego problemy z uzupełnianiem NP nie mają podobnych współczynników aproksymacji?
Ponieważ 2 problemy NP-zupełne są z definicji redukowalne względem siebie, więc rozwiązanie jednego z nich można uzyskać za pomocą czarnej skrzynki rozwiązującej drugi, dlaczego nie mają podobnych współczynników aproksymacji (w odniesieniu do ich odpowiedników optymalizacyjnych )? Wydaje mi się, że pewne stałe lub nawet wielomianowe znoszenie może być zrozumiane, ale …
1
Lemma i derandomizacja Borela-Cantellego
Czytałem artykuł zatytułowany Losowe wyrocznie z (poza) programowalnością . Ostatni akapit sekcji 2.3 brzmi: [Stosując nasze nowatorskie podejście] nie ma potrzeby stosowania dobrze znanych klasycznych asymptotycznych (i jednolitych) technik derandomizacji opartych na lemacie Borela-Cantellego . Zgodnie z naszą najlepszą wiedzą, podejście to jest nowością w tym dokumencie. Rzuciłem okiem na …
1
Twierdzenie PCP - etap redukcji alfabetu
To, co następuje, może wydawać się głupie (i to prawdopodobnie odzwierciedla moje słabe zrozumienie - więc proszę o wyrozumiałość) Miałem zapytanie dotyczące twierdzenia PCP. Wiemy, że po pierwszych trzech krokach mianowicie. Redukcja stopnia, ekspansja i amplifikacja odstępów , mamy wykres ograniczeń z ulepszoną przerwą i dużym rozmiarem alfabetu (jak Σ …
5
Wystąpienie redukcji FPT, która nie jest redukcją czasu wielomianowego
W sparametryzowanej złożoności ludzie używają redukcji stałych parametrów (FPT), aby udowodnić twardość W [t]. Teoretycznie redukcja FPT nie jest redukcją czasu wielomianowego, ponieważ może działać wykładniczo w parametrze k. Ale w praktyce wszystkie redukcje FPT, które widziałem, są redukcjami czasu p, co oznacza, że ​​dowody twardości W [t] prawie zawsze …
1
NP vs co-NP i logika drugiego rzędu
Załóżmy, że NP = co-NP i wielomian ogranicza długość dowodu niezadowolenia dla instancji 3-CNF . Czy są więc jakieś wyniki w jakiej formie może przyjąć jakiś dowód niezadowolenia dla długości ? Tzn. Ogólnie, czy taki dowód musiałby na przykład wykorzystać pełną moc logiki drugiego rzędu nad nieskończonymi strukturami (zdaję sobie …
2
Które gry 2P1R są potencjalnie ostre?
Dwukomorowe gry na jedną rundę (2P1R) są niezbędnym narzędziem do uzyskania stopnia zbliżenia. Konkretnie, równoległe powtarzanie dwóch rundowych gier z dwiema proverami pozwala zwiększyć rozmiar luki w decyzyjnej wersji problemu aproksymacji. Zobacz wywiad ankiety Ran Raz na CCC 2010, aby uzyskać przegląd tego tematu. Równoległe powtarzanie gry ma zadziwiającą właściwość …
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.