Y a-t-il des problèmes connus de NP qui sont supposés être en moyenne exponentiellement durs?

12

ETH déclare que SAT ne peut pas être résolu dans le pire des cas en temps sous-exponentiel. Et le cas moyen? Y a-t-il des problèmes naturels dans le NP qui sont supposés être exponentiellement durs dans le cas moyen?

Par cas moyen, on entend le temps de fonctionnement moyen avec une distribution uniforme sur les entrées.

cc.complexity-theory np average-case-complexity Anonyme
la source
6
vous avez besoin d'une définition du «cas moyen» pour que votre question soit mathématiquement significative.
Yixin Cao
2
vzn, je ne comprends pas la pertinence de votre commentaire. Je ne pose pas de question sur un problème ouvert ici, il est évident qu'il n'y a pas de problèmes connus pour être difficiles en moyenne. Je demande s'il y a des candidats qui sont supposés être durs dans le cas moyen. Veuillez lire attentivement la question avant de commenter.
Anonyme
1
@vzn Exactement! Je suis tout à fait d'accord, mon sens est qu'il semble difficile pour une telle conjecture de faire un pas significatif en avant ou de changer substantiellement les directions de recherche que vous avez mentionnées.
usul
3
OP, notez que le temps de fonctionnement prévu n'est pas AFAIK la quantité habituelle que nous examinons dans la dureté moyenne du boîtier. voir un aperçu de la théorie de la complexité moyenne des cas de Levin
Sasho Nikolov
1
Sasho Nikolov, je connais la théorie de Levin. Cependant, il existe également une complexité de cas moyen plus simple utilisée pour analyser le comportement des algorithmes sur une distribution spécifique remontant à [Karp 1986] qui est plus courante dans les algorithmes. Je suis conscient que le problème de tuilage et quelques autres problèmes sont complets pour DistNP. Cependant, je ne sais pas s'ils sont supposés être exponentiellement durs en moyenne en utilisant le sens simple du cas moyen dû à Karp.
Anonyme

Réponses:

12

On peut supposer que le problème d'apprentissage de la parité avec bruit (LPN) à taux d'erreur constant nécessite le temps . L'algorithme connu le plus rapide (Blum-Kalai-Wasserman) utilise le temps 2 O ( n / log n ) .2n1−o(1)2O(n/log⁡n)

Ryan O'Donnell
la source
Je vous remercie. Pourriez-vous s'il vous plaît donner des références où je peux en savoir plus sur le problème LPN?
Anonyme
2
@Anonymous: Cet article énonce plusieurs conjectures sur la dureté du LPN: M. Alekhnovich. «Plus d'informations sur la complexité moyenne des cas par rapport à la complexité approximative. Dans Proc. du 44e Symposium sur les fondations de l'informatique, pp, 298-307, 2003.
Yury
Yury, merci pour la référence: math.ias.edu/~misha/papers/average.ps
Anonyme
11

Ce n'est pas tout à fait la même chose que "tous les algorithmes", mais dans SODA'04, Achlioptas Beame et Molloy ont suggéré que chaque algorithme de retour arrière devrait nécessiter un temps exponentiel sur des instances 3SAT aléatoires avec variables et c n clauses, avec c choisi dans une plage de valeurs proche de le seuil de satisfiabilité.ncnc

David Eppstein
la source
Je vous remercie. Y a-t-il une raison pour laquelle ils ne conjecturent pas l'affirmation plus forte selon laquelle le k-SAT aléatoire limité au rapport de clause proche du seuil de satisfiabilité est exponentiellement difficile?
Anonyme
4
Je suppose que c'est parce qu'ils peuvent prouver des résultats sur des algorithmes de retour en arrière qui ne sont pas conditionnels à P ≠ NP.
David Eppstein
6

Il existe plusieurs générateurs de nombres aléatoires que nous n'avons pas d'algorithmes de temps polynomiaux pour la rupture. Je suppose que vous pourriez les considérer comme difficiles en moyenne. Consultez les générateurs sur www.ecrypt.eu.org/stream/ Il y en a bien sûr d'autres, vous pouvez en rechercher la plupart en ligne.

William Hird
la source
Existe-t-il un PRN polytime particulier qui est supposé être exponentiellement dur en moyenne?
Anonyme
Le générateur de pas alternatif inventé par Gunther est une beauté pour plusieurs raisons. Il faut deux registres à décalage à rétroaction linéaire (LFSR) A & B et XOR les sorties mais la synchronisation des deux registres est contrôlée par un troisième LFSR (C) de sorte que les sorties A & B entrent dans la porte XOR de manière irrégulière. Étant donné que les bits de C contrôlent uniquement la synchronisation de A & B et n'apparaissent pas dans le flux de sortie, C peut être considéré comme une variable quasi cachée qui rompt la linéarité inhérente de A & B. Ceci est une explication simplifiée mais vous voudrez pour voir le circuit par vous-même.
William Hird
Je ne connais pas "Générateur d'étapes alternées inventé par Gunther". Est-il supposé être exponentiellement dur en moyenne?
Anonyme
1
Je ne sais pas comment répondre à votre commentaire tel que posé, mais l'ASG est considéré comme incassable tant que la longueur des clés pour les trois registres à décalage est d'environ 128 bits chacune. Si cela équivaut à être «exponentiellement difficile en moyenne», je suppose que votre réponse est oui.
William Hird
1
@Anonymous: Bien sûr, l'ASG "bare-bones" peut être rendu plus difficile à briser en utilisant trois ASG comme registres AB & C pour un autre ASG, Gunther y fait allusion dans son article original. C'est comme ajouter plus de tours à un chiffrement par bloc. Jusqu'où on peut amplifier la dureté par cette méthode est une question ouverte (et intéressante) :-)
William Hird
0

ma compréhension est que, bien qu'il existe certains candidats issus de la théorie de l'incassabilité de la cryptographie et des générateurs de nombres aléatoires [par exemple, certains cités dans Razborov / Rudich, Natural Proofs], la plupart des aspects de votre question sont reconnus comme des questions clés "encore ouvertes" par des experts Sur le terrain. depuis l'introduction à l'enquête complète, la complexité moyenne des cas par Bogdanov et Trevisan (2006) a quelques points liés. La conférence YouTube de Trevisan sur les résultats et les questions ouvertes de complexité moyenne des cas peut également être utile.



≠

≠

Les bonnes techniques pour appliquer une telle théorie aux problèmes naturels et aux distributions n'ont pas encore été découvertes. De ce point de vue, l'état actuel de la théorie de la complexité du cas moyen en NP est similaire à l'état de la théorie de l'inapproximabilité des problèmes d'optimisation du NP avant le théorème du PCP.

vzn
la source
2
Pas une réponse à ma question. Je pensais vous avoir expliqué que je ne cherchais pas de commentaires généraux sur des questions connexes, je recherchais des problèmes de candidats supposés difficiles .
Anonyme
1
peu importe! à mon humble avis "la théorie n'a pas de réponse substantielle à votre question pour le moment", avec quelques-unes des meilleures références / autorités disponibles sur le sujet est une réponse légitime à votre question, qui n'a pas été publiée uniquement pour vous
vzn
1
@Anonymous, je suis encore un peu confus quant à votre sens de "conjecturé". Nous pouvons tous avoir nos conjectures personnelles, il n'est donc pas clair si vous recherchez une opinion personnelle, une position sur une question ouverte partagée par de nombreuses personnes dans la recherche, ou quelque chose entre les deux. Cela peut aider à donner une déclaration plus précise de ce que vous recherchez. De plus, je trouve que les réponses telles que vzn sont instructives et informatives même si elles ne se rapportent pas directement à votre question exacte, donc je ne pense pas que de telles réponses devraient être si fortement découragées.
usul
2
Si vous avez lu mon commentaire auquel Peter Shor a répondu, je suis déjà au courant de problèmes cryptographiques qui sont supposés être superpolynomialement difficiles. Veuillez lire attentivement la question, je ne recherche pas de problèmes superpolynomialement difficiles, je recherche des problèmes exponentiellement difficiles.
Anonyme
2
Veuillez poursuivre la discussion pour discuter.
Jeffε