Pytania otagowane jako cc.complexity-theory

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

2
Prosty dowód na najgorszy przypadek Ω (n lg n) wyjątkowości / odrębności?
Istnieje kilka dowodów na dolną granicę logiczną dla problemu wyjątkowości / odrębności elementu (opartej na drzewach obliczeń algebraicznych lub argumentach przeciwnych), ale szukam takiego, który byłby wystarczająco prosty do zastosowania w pierwszym kursie analizy i projektowania algorytmów. Taki sam „poziom trudności” jak dolna granica sortowania byłby w porządku. Również każde …
2
Zliczanie roztworów wzorów Monotone-2CNF
Formuła Monotone-2CNF to formuła CNF, w której każda klauzula składa się z dokładnie 2 literałów dodatnich. Teraz mam wzór Monotone-2CNF . Niech S będzie zbiorem satysfakcjonujących zadań F. Mam również wyrocznię O, która może podać następujące informacje:FFFSSSFFFOOO Kardynalność zbioru (tj. Liczba rozwiązań F ).SSSFFF Biorąc pod uwagę zmienną : xxx …
1
Czy „Czy permutacja jest automorfizmem grafu w moim zestawie?” NP-kompletny?
Załóżmy, że mamy zestaw S grafów (wykresy skończone, ale ich nieskończona liczba) i grupę P permutacji, która działa na S. Instancja: permutacja pw P. Pytanie: Czy istnieje wykres g w S, który dopuszcza automorfizm p? Czy ten problem NP-zupełny dla niektórych zestawów S? Łatwo byłoby sprawdzić, czy wykres dopuszcza permutację …
2
Wyczerpujący symulator protokołów zerowej wiedzy w losowym modelu Oracle
W artykule zatytułowanym „On Deniability in Common Reference String and Random Oracle Model” Rafael Pass pisze: Zauważamy, że udowadniając bezpieczeństwo zgodnie ze standardową definicją zerowej wiedzy w modelu RO [Random Oracle], symulator ma dwie zalety w stosunku do zwykłego symulatora modelu, a mianowicie: Symulator może zobaczyć, na jakich wartościach strony …
2
Hierarchia naprzemienna
Dzięki Immerman i Szelepcsényi wiadomo, że jeśli f = Ω ( log ) (nawet w przypadku funkcji niemożliwych do zbudowania w przestrzeni).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) W tym samym artykule Immerman stwierdza, że ​​naprzemienna hierarchia przestrzeni logicznej się zawala, co oznacza, że (definicja ograniczonej naprzemiennej maszyny Turinga i tego, co jest hierarchię …
2
Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie ukierunkowanym występuje niewyważony wierzchołek, musi istnieć inny. Ale zazwyczaj klasa jest …
4
Czy możemy szybko wygenerować idealnie jednolicie mod 3 lub rozwiązać problem NP?
Szczerze mówiąc, nie wiem zbyt wiele o tym, jak generowana jest liczba losowa (komentarze są mile widziane!), Ale załóżmy następujący model teoretyczny: Możemy uzyskać liczby całkowite jednolicie losowe z a naszym celem jest wyprowadza liczbę całkowitą jednolicie losową z [1,3].[ 1 , 2 n ][1,2n][1,2^n] Oto proste rozwiązanie, którego oczekiwany …
1
Czy występują problemy z „NP-Intermediate-Complete”?
Załóżmy, że P NP.≠≠\ne Twierdzenie Ladnera mówi, że istnieją problemy pośrednie NP (problemy w NP, które nie są ani w P, ani w NP-Complete). Znalazłem w Internecie kilka zawoalowanych odniesień, które sugerują (myślę), że istnieje wiele „poziomów” wzajemnie redukowalnych języków w ramach NPI, które zdecydowanie nie wszystkie się zlewają. Mam …
1
Dlaczego te dwie definicje PPAD są równoważne?
Klasa złożoności PPAD jest zwykle definiowana przez stwierdzenie, że Koniec linii jest kompletny z PPAD. Koniec linii to problem z wyszukiwaniem. Dane wejściowe składają się z ukierunkowanego wykresu, w którym każdy węzeł ma co najwyżej stopień i stopień 1. Wykres jest podawany przez funkcję obliczeniową wielomianową która zwraca poprzednika i …
3
Gra na kilku wykresach
Rozważ następującą grę na ukierunkowanym wykresie ważonym solGG z chipem w pewnym węźle. Wszystkie węzły solGG oznaczone są literą A lub B. Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B). Początkowo Alice i Bob mają odpowiednio mZAmAm_A i mbmBm_B dolarów. …
1
Entropia i złożoność obliczeniowa
Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć odpowiedź.F(n)F(n)F(n)F(n)F(n)F(n)
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.