Czy są znane problemy NP, które są przypuszczalnie średnio trudne wykładniczo?

12

ETH stwierdza, że ​​SAT nie może być rozwiązany w najgorszym przypadku w czasie podwykonawczym. Co z przeciętną sprawą? Czy istnieją naturalne problemy związane z NP, które są przypuszczalnie trudne w przeciętnym przypadku?

Średni przypadek oznacza średni czas pracy z równomiernym rozkładem na wejściach.

cc.complexity-theory np average-case-complexity Anonimowy
źródło
6
potrzebujesz definicji „przeciętnego przypadku”, aby twoje pytanie miało sens matematyczny.
Yixin Cao,
2
vzn, nie rozumiem znaczenia twojego komentarza. Nie pytam tutaj o otwarty problem, oczywiste jest, że nie ma problemów, które są średnio trudne. Pytam, czy są jacyś kandydaci , którzy przypuszczają, że są trudni w przeciętnym przypadku. Przeczytaj uważnie pytanie, zanim skomentujesz.
Anonimowy,
1
@vzn Dokładnie! Zdecydowanie zgadzam się, moim rozumieniu jest to, że wydaje się trudne do dowolnego takie przypuszczenie wnieść znaczący krok do przodu lub znacząco zmienić kierunki badań, które wymienione.
usul
3
OP, należy pamiętać, że oczekiwany czas pracy nie jest AFAIK zwykłą ilością, na którą patrzymy w średniej twardości obudowy. patrz sondaż na temat średniej teorii złożoności przypadku Levina
Sasho Nikolova
1
Sasho Nikolov, znam teorię Levina. Jednak istnieje również prostsza średnia złożoność przypadków wykorzystywana do analizy zachowania algorytmów w określonym rozkładzie sięgającym [Karp 1986], co jest bardziej powszechne w algorytmach. Wiem, że problem z kafelkami i kilka innych problemów jest kompletnych dla DistNP. Nie wiem jednak, czy są one przypuszczalnie średnio trudne wykładniczo, używając prostego znaczenia przeciętnego przypadku z powodu Karpa.
Anonimowy,

Odpowiedzi:

12

Można przypuszczać, że problem parzystości uczenia się z hałasem (LPN) przy stałym poziomie błędu wymaga czasu . Najszybszy znany algorytm (Blum-Kalai-Wasserman) wykorzystuje czas 2 O ( n / log n ) .2)n1-o(1)2)O(n/log⁡n)

Ryan O'Donnell
źródło
Dziękuję Ci. Czy możesz podać referencje, w których mogę przeczytać więcej na temat problemu z LPN?
Anonimowy,
2
@Anonimowy: W niniejszym artykule przedstawiono kilka domysłów dotyczących twardości LPN: M. Alekhnovich. „Więcej na temat przeciętnego przypadku w porównaniu do złożoności przybliżenia”. W Proc. 44. sympozjum na temat podstaw informatyki, s. 298–307, 2003.
Yury,
Yury, dzięki za odniesienie: math.ias.edu/~misha/papers/average.ps
Anonimowy
11

To nie to samo, co „każdy algorytm”, ale w SODA'04 Achlioptas Beame Molloy i zasugerował, że każdy algorytm wycofywania powinien wymagać wykładniczy czas na losowych przypadkach 3SAT z zmiennych i c n klauzul, z C zawiera się w przedziale wartości najbliższej próg satysfakcji.ndondo

David Eppstein
źródło
Dziękuję Ci. Czy istnieje powód, dla którego nie przypuszczają silniejszego stwierdzenia, że ​​losowy k-SAT ograniczony do współczynnika klauzuli zbliżonego do progu satysfakcji jest wykładniczo trudny?
Anonimowy,
4
Domyślam się, że to dlatego, że mogą udowodnić wyniki dotyczące algorytmów cofania, które nie są uzależnione od P ≠ NP.
David Eppstein,
6

Istnieje kilka generatorów liczb psuedorandom, które nie mają algorytmów wielomianu czasowego do zerwania. Sądzę, że można uznać je za trudne w przeciętnych przypadkach. Sprawdź generatory na www.ecrypt.eu.org/stream/ Są oczywiście inne, możesz zbadać większość z nich online.

William Hird
źródło
Czy jest jakiś konkretny PRNG w polityce czasowej, który jest przypuszczalnie średnio trudny wykładniczo?
Anonimowy,
Generator przemienny wymyślony przez Gunthera jest pięknem z kilku powodów. Zajmuje dwa rejestry przesuwne liniowego sprzężenia zwrotnego (LFSR) A i B, a XOR wyjścia, ale taktowanie dwóch rejestrów jest kontrolowane przez trzeci LFSR (C) tak, że wyjścia A i B wchodzą do bramki XOR w nieregularny sposób. Ponieważ bity C kontrolują tylko taktowanie A i B i nie pojawiają się w strumieniu wyjściowym, C można uznać za quasi ukrytą zmienną, która rozbija naturalną liniowość A i B. To jest uproszczone wyjaśnienie, ale będziesz chciał aby zobaczyć obwód dla siebie.
William Hird,
Nie znam „Generatora kroków naprzemiennych wymyślonego przez Gunthera”. Czy przypuszcza się, że jest średnio wykładniczo trudny?
Anonimowy,
1
Nie wiem, jak odpowiedzieć na postawiony komentarz, ale ASG uważa się za niezniszczalny, o ile długości kluczy dla trzech rejestrów przesuwnych wynoszą około 128 bitów każdy. Jeśli jest to równoznaczne z „przeciętnie trudnym wykładniczo”, sądzę, że twoja odpowiedź brzmi „tak”.
William Hird,
1
@Anonimowy: Oczywiście, ASG „bez kości” może być trudniejszy do złamania przez użycie trzech ASG jako rejestrów AB i C dla innego ASG, Gunther nawiązuje do tego w swoim oryginalnym artykule. To jak dodawanie kolejnych rund do szyfru blokowego. Jak daleko można zwiększyć twardość za pomocą tej metody jest otwarte pytanie (i interesujące) :-)
William Hird
0

Rozumiem, że choć niektórzy kandydaci z teorii niezniszczalności kryptografii i generatorów liczb losowych [np. niektórzy cytowani w Razborov / Rudich, Natural Proofs], większość aspektów twojego pytania jest uznawana przez ekspertów za zasadniczo kluczowe pytania „wciąż otwarte” na polu. od wprowadzenia do kompleksowej ankiety „ Średnia złożoność przypadków” autorstwa Bogdanova i Trevisana (2006) ma kilka powiązanych punktów. Pomocny może być także wykład Trevisana na youtube na temat ustaleń i otwartych pytań o średniej złożoności przypadków .



≠

≠

Właściwe techniki zastosowania takiej teorii do naturalnych problemów i dystrybucji nie zostały jeszcze odkryte. Z tego punktu widzenia obecny stan teorii złożoności średnich przypadków w NP jest podobny do stanu teorii niedopuszczalności problemów optymalizacji NP przed twierdzeniem PCP.

vzn
źródło
2
Brak odpowiedzi na moje pytanie. Wydawało mi się, że wyjaśniłem wam, że nie szukam ogólnego komentarza w powiązanych kwestiach, szukam domniemanych problemów kandydatów .
Anonimowy,
1
cokolwiek! imho „teoria nie ma w tej chwili istotnej odpowiedzi na twoje pytanie” wraz z jednymi z najlepszych / najbliższych referencji / autorytetów w sprawie jest uzasadnioną odpowiedzią na twoje pytanie, które zostało zamieszczone nie tylko dla ciebie
od
1
@Anonimowy, wciąż jestem trochę zdezorientowany co do twojego znaczenia słowa „domniemany”. Wszyscy możemy mieć osobiste przypuszczenia, więc nie jest jasne, czy szukasz osobistej opinii, stanowiska w sprawie otwartego pytania, które podziela wiele osób badających, czy czegoś pośredniego. Może to pomóc w dokładniejszym określeniu tego, czego szukasz. Ponadto uważam, że odpowiedzi takie jak vzn są pouczające i pouczające, nawet jeśli nie odnoszą się one bezpośrednio do twojego dokładnego pytania, więc nie widzę, aby takie odpowiedzi były tak bardzo odradzane.
usul
2
Jeśli przeczytałeś mój komentarz, na który odpowiedział Peter Shor, już wiem o problemach kryptograficznych, które są przypuszczalnie bardzo trudne. Przeczytaj uważnie pytanie, nie szukam problemów o wielobiegunowym charakterze, szukam wykładniczo trudnych.
Anonimowy,
2
Poproś o dalszą dyskusję na czacie.
Jeffε,