Założenia antologii złożoności

32

W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń, albo hipotezy losowej wyroczni. Najważniejszym i powszechnie uznawanym założeniem jest to, że PH się nie rozpada. Ich słowami:

W jednym podejściu zakładamy jako działającą hipotezę, że PH ma nieskończenie wiele poziomów. Zatem każde założenie, które sugerowałoby, że PH jest skończone, jest uważane za nieprawidłowe. Na przykład Karp i Lipton wykazali, że jeśli NP ⊆ P / poli, to PH zapada się do . Uważamy więc, że SAT nie ma obwodów wielomianowych. Podobnie uważamy, że kompletne komplety Turinga i wiele jeden kompletów dla NP nie są rzadkie, ponieważ Mahaney pokazał, że te warunki zawalą PH. Można nawet wykazać, że dla dowolnego k ≥ 0, oznacza, że ​​PH jest skończone. Dlatego uważamy, żeΣ2)P.P.S.ZAT.[k]=P.S.ZAT.[k+1]P.S.ZAT.[k]P.S.ZAT.[k+1] dla wszystkich k ≥ 0. Zatem jeśli hierarchia wielomianowa jest rzeczywiście nieskończona, możemy opisać wiele aspektów złożoności obliczeniowej NP.

Oprócz założenia, że ​​PH nie załamuje się, istnieje wiele innych założeń dotyczących złożoności. Na przykład:

  1. Yao uważa, że ​​możliwe jest następujące założenie: .RPϵ>0DTIME(2nϵ)
  2. Nisan i Wigderson przyjmują kilka założeń związanych z derandomizacją.

Główną ideą tego pytania jest to, co mówi jego tytuł: być antologią założeń teoretycznych złożoności. Byłoby wspaniale, gdyby przestrzegano (w miarę możliwości) następujących konwencji:

  1. Samo założenie;
  2. Pierwszy artykuł, w którym dokonano założenia;
  3. Interesujące wyniki, w których zastosowano założenie;
  4. Jeśli założenie kiedykolwiek zostało obalone / dowiedzione, lub czy kiedykolwiek została omawiana jego wiarygodność.

This post is meant to be a community wiki; if an assumption is already cited, please edit the post and add new information rather than making a new post.


Edycja (31.10.2011): Niektóre założenia kryptograficzne i informacje o nich są wymienione w następujących witrynach:

  1. Wiki Prymitywów kryptograficznych i trudnych problemów w kryptografii .
  2. Założenia kryptograficzne Helgera Lipmy i trudne problemy .
Sadeq Dousti
źródło
2
Miły. David Johnson zrobił coś podobnego dla wyników złożoności użytych do wykazania twardości przybliżenia w ostatniej kolumnie.
Suresh Venkat,
@Suresh: Link do kolumny Johnsona jest bardzo mile widziany.
MS Dousti,
Wymaganie pierwszego papieru może być trudne.
András Salamon,
@ András: Tak. Z tego powodu dodałem zwrot „kiedykolwiek to możliwe”. Możesz zacytować papier, który Twoim zdaniem jest pierwszy. Ponieważ jest to CW, jeśli ktoś zna starszy wynik, po prostu poprawia post.
MS Dousti,

Odpowiedzi:

10
  • Założenie: wykładnicza hipoteza czasowa .
  • Po raz pierwszy cytowany w: Będąc folklorem, po raz pierwszy sformalizowano go w następującym artykule: Russell Impagliazzo i Ramamohan Paturi. 1999. Złożoność k-SAT . W materiałach z czternastej dorocznej konferencji IEEE na temat złożoności obliczeniowej ( COCO '99 ). IEEE Computer Society, Waszyngton, DC, USA, 237-240.
  • Zastosowania: Zakłada, że ​​nie można rozstrzygnąć problemu NP-zupełnego w czasie sub wykładniczym, a zatem implikuje, że P ≠ NP.
  • Status: otwarty.
Niesamowite
źródło
Myślę, że ETH zakłada, że ​​problemu 3-SAT nie można rozstrzygnąć w czasie sub wykładniczym. Odpowiedzi na ten post ( cstheory.stackexchange.com/questions/3620/... ) sugerują istnienie sub wykładniczych algorytmów czasowych dla niektórych problemów związanych z NP-zupełnymi, takich jak Planar Independent Set.
Mohammad Al-Turkistany
Jak pisze Mohammad, opis w „Użytkach” jest nieprecyzyjny lub po prostu zły.
Yoshio Okamoto
@YoshioOkamoto: To jest post na wiki społeczności. Dlaczego nie postarać się, aby post był precyzyjny, a nawet go poprawić?
MS Dousti,
Nie jestem pewny. Powiązana strona wikipedii zawiera więcej informacji, a moja edycja byłaby tylko powtórzeniem.
Yoshio Okamoto,
8
  • Założenie : NP nie ma p-miary 0
  • Po raz pierwszy cytowany w : Jack H. Lutz. Kategoria i miara w klasach złożoności . SIAM J. Comput. 19: 1100-1131, 1990.
  • Zastosowania : Jeżeli to P N P i: μp(N.P.)0P.N.P.
    1. Jest to język jest -Complete dla NP, ale nie P m -Complete dla NP [1];T.pmp
    2. W NP występuje para rozłącznych języków, które są nierozłączne z P [4];
    3. Dla każdego , co P N alfa - t t -hard język NP jest gęsta [3];α<1nα-ttp
    4. Każdy język -kompletny dla NP ma gęsty wykładniczy rdzeń złożoności [2];mp
    5. NP zawiera język odporny na P-bi [3];
    6. i e e N E E ([1] - patrztę odpowiedźna kilka konsekwencji E E N E, E ).miN.mimimiN.mimimimiN.mimi

O ile wiem, powyższe konsekwencje nie są znane do naśladowania tylko z założenia, że .P.N.P.

  • Status : otwarty

[1] J. Lutz i E. Mayordomo. Gotuj kontra Karp / Levin: oddzielanie pojęć kompletności, jeśli NP nie jest małe . Teoretyczna Komp. Sci. 164: 141-163, 1996.

[2] D. Juedez i J. Lutz. Złożoność i rozkład trudnych problemów . SIAM J. Comput 24 (2): 279–295, 1995.

[3] E. Mayordomo. Prawie każdy zestaw w czasie wykładniczym jest odporny na P-bi . Teoretyczna Komp. Sci. 136: 487-506, 1994.

[4] L. Fortnow, J. Lutz i E. Mayordomo. Nierozłączność i silne hipotezy dla rozłącznych par NP . W Jean-Yves Marion i Thomas Schwentick, redaktorzy, Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science, tom 5 Leibniz International Proceedings in Informatics (LIPIcs), strony 395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Niemcy, 2010.

Joshua Grochow
źródło
Doskonały. Wierzę, że możesz wyśledzić założenie do pracy doktorskiej Lutza z 1987 r. „ Kategoria związana z zasobami i miary w klasach wykładniczej złożoności ” lub do jego papierowej kategorii Baire i małych obwodów w przestrzeni wykładniczej z 1987 r. IEEE z 1987 r. (Która nie jest dostępna online !).
MS Dousti
6
  • Założenie: NEEEE .
  • Po raz pierwszy cytowany w: Mihir Bellare i Shafi Goldwasser. 1994. Złożoność decyzji a wyszukiwanie . SIAM J. Comput. 23, 1 (luty 1994), 97-119.
  • Zastosowania: Jeśli założenie się utrzymuje, w NP występują problemy, których wersja wyszukiwania nie (wielomianowo) redukuje do ich wersji decyzyjnej. Innymi słowy, przy danym założeniu, nie wszystkie języki w NP są redukowalne .
  • Status: otwarty.
Sadeq Dousti
źródło