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

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$\Sigma^P_2$$P^{\mathrm{SAT}[k]} = P^{\mathrm{SAT}[k+1]}$$P^{\mathrm{SAT}[k]} \ne P^{\mathrm{SAT}[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 \subseteq \bigcap\limits_{\epsilon > 0} DTIME(2^{n^\epsilon})$
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 .

• 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.

• 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: $\mu_p(NP) \neq 0$$P \neq NP$
  1. Jest to język jest -Complete dla NP, ale nie ≤ P m -Complete dla NP [1];$\leq_T^p$$\leq_m^p$
  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];$\alpha < 1$$\leq_{n^{\alpha}-tt}^p$
  4. Każdy język -kompletny dla NP ma gęsty wykładniczy rdzeń złożoności [2];$\leq_m^p$
  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 ).$E \neq NE$$EE \neq NEE$$EE \neq NEE$

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

• 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.

• Założenie: NEE ≠ EE .
• 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.