Niejednolici kontra Jednolici Przeciwnicy

To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access .

Nieformalne oświadczenie: kiedy nierównomiernym przeciwnikom (tj. Wielorakiej rodzinie obwodów) udaje się przełamać schemat kryptograficzny, a jednolitym przeciwnikom (tj. Probabilistycznym wielomiejscowym maszynom Turinga) nie?

Oświadczenie teoretyczne dotyczące złożoności: Nie jest to dokładnie to samo, co powyższe oświadczenie nieformalne, ale tak naprawdę jestem zainteresowany tą wersją:

W czym leżą naturalne problemy $(\mathsf{NP} \cap \mathsf{P/poly}) - \mathsf{AvgP}$ ?

Innymi słowy, co trudno przeciętnie naturalne$\mathsf{NP}$problemy można rozwiązać za pomocą wielorakiej rodziny obwodów?

Słowo rozwiązane może być interpretowane jako najgorszy lub średni przypadek (ten drugi jest preferowany).

Jeśli problemów naturalnych nie da się łatwo znaleźć, dopuszczalne są również problemy sztuczne.

Nie ma prawie żadnego naturalnego problemu, który uważa się za P / poli, ale nie za P. Sztuczne przykłady można dostosować, aby odpowiedzieć na twoje pytanie.

Założyć $E \neq NE$, wówczas występuje jednoargumentowy język L w NP, który nie jest w P - unary oznacza, że ​​wszystkie ciągi w języku mają postać $1^n$ dla niektórych n.

Następnie zdefiniuj L 'jako zbiór wszystkich łańcuchów x takich, że $1^{length(x)}$ jest w L. To jest w NP, jest w P / poli i nie jest to średni czas wielomianowy