Pytania otagowane jako complexity-classes

Klasy złożoności obliczeniowej i ich relacje

6
Czy istnieje naturalny problem w czasie quasi-wielomianowym, ale nie w czasie wielomianowym?
László Babai niedawno udowodnił, że problem z izomorfizmem grafowym występuje w quasipolomomialnym czasie . Zobacz także jego przemówienie na Uniwersytecie w Chicago, notatkę z przemówień Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Zgodnie z twierdzeniem LADNER, o ile P.≠NP.P≠N.P.P \neq NP , a …
4
Złożoność komunikacji… Klasy?
Dyskusja : Spędziłem ostatnio trochę czasu na nauce różnych rzeczy w złożoności komunikacji. Na przykład ponownie zapoznałem się z odpowiednim rozdziałem w Arora / Barak, zacząłem czytać kilka artykułów i zamówiłem książkę Kushilevitz / Nisan. Intuicyjnie chcę porównać złożoność komunikacji ze złożonością obliczeniową. W szczególności uderza mnie fakt, że złożoność …
1
Czy wszystkie klasy złożoności mają charakterystykę języka liścia?
Języki liścia są pięknym sposobem na jednolite zdefiniowanie wielu klas złożoności. Większość klas złożoności jest zwykle określana przez model obliczeniowy (np. Deterministyczna / losowa TM) i związany z zasobami (czas dziennika, przestrzeń wielopunktowa itp.). Jednak w sformułowaniu języka liścia istnieje tylko jeden model obliczeń, a klasa jest określona przez podanie …
1
Czy istnieje lepsza niż liniowa dolna granica dla faktoringu i dziennika dyskretnego?
Czy istnieją odniesienia, które zawierają szczegółowe informacje na temat dolnych granic obwodu dla konkretnych trudnych problemów pojawiających się w kryptografii, takich jak faktoring liczb całkowitych, problem logarytmu dyskretnego z liczbami pierwszymi / złożonymi i jego wariant nad grupą punktów krzywych eliptycznych (i ich wielowymiarowych odmian abelowych) i ogólne ukryty problem …
1
Konsekwencje UP są równe NP
EDYCJA na 2011/02/08: Po znalezieniu i przeczytaniu niektórych odniesień postanowiłem rozdzielić oryginalne pytanie na dwa osobne. Oto część dotycząca UP vs NP, w części dotyczącej klas syntaktycznych i semantycznych zobacz Korzyści dla klas syntaktycznych i semantycznych . UPUP\mathsf{UP} (jednoznaczny czas wielomianowy, patrzwikiizoodla odniesienia) jest zdefiniowany jako języki ustalone przez maszynyNPNP\mathsf{NP} …
4
Parzystość i
Parzystość i są jak nierozłączne bliźniaki. Tak przynajmniej wyglądało przez ostatnie 30 lat. W świetle wyników Ryana wznowione zostanie zainteresowanie małymi klasami.AC0AC0AC^0 Furst Saxe Sipser do Yao do Hastad są ograniczeniami parzystości i losowymi. Razborov / Smolensky jest przybliżonym wielomianem z parzystością (ok, mod bramki). Aspnes i wsp. Stosują słaby …
1
Układanka do cięcia pałeczek
Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2. Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? 1 , 2 , … , n1,2),…,n{1,2,\ldots,n} Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna dyskusja: http://www.iwriteiam.nl/cutsticks.html Co jeszcze wiadomo na …
1
Najbardziej znane wspólne pojemniki dla / przez NP i Parity-P?
Parzystość-P jest zbiorem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji). Zatem Parity-P jest w zasadzie PP „s karłowate młodsze rodzeństwo: podczas liczy PP czy liczba przyjmujących ścieżkach NP-maszyna jest większość, czy nie ( …
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.