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,

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^{n^{1-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 klauzul, z zawiera się w przedziale wartości najbliższej próg satysfakcji. $n$ $cn$ $c$

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

$\neq$

$\neq$

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ε,