Applications de la théorie de la complexité

18

La théorie de la complexité semble saisir quelque chose de fondamental dans la structure de l'univers, en ce qu'elle formalise la notion intuitive que certains problèmes sont plus difficiles que d'autres.

Scott Aaronson prédit : "L'hypothèse de dureté NP sera finalement considérée comme analogue à la deuxième loi de la thermodynamique ou à l'impossibilité de la signalisation supraluminique."

Les soi-disant «problèmes difficiles» sont à la base de la cryptographie moderne.

Y a-t-il d' autres applications qui utilisent, dépendent ou illustrent l'existence de problèmes de calcul difficiles?

cc.complexity-theory soft-question big-picture rphv
la source

Réponses:

14

Le dernier numéro du CACM contient un article de Faliszewski, Hemaspaandra et Hemaspaandra sur l'utilisation de la théorie de la complexité dans le domaine de la théorie du choix social et de la conception des élections en particulier. Un exemple d'un tel résultat est que si le théorème d'Arrow garantit que tout système électoral est «piratable», il pourrait être difficile de le faire.

Suresh Venkat
la source
1
Je n'ai pas lu cet article, mais il semble que l'auteur conçoit des systèmes de vote électronique sécurisés. N'est-ce pas une application de la cryptographie aux systèmes de sécurité? Notez que l'OP demande des applications de problèmes difficiles à des domaines autres que la cryptographie.
MS Dousti
2
Non, ce n'est pas tout à fait ça. Ils étudient les mathématiques des systèmes de vote et tentent de comprendre comment la perspective de la théorie de la complexité modifie les choix de conception. Par exemple, parmi trois schémas qui se ressemblent, l'un est difficile à pirater NP et les autres ne le sont pas. C'est une vue informatique sur la théorie du choix social, un peu comme la crypto moderne donne une perspective informatique sur les secrets de codage.
Suresh Venkat
7

ϵϵ1/ϵ

Daniel Apon
la source
Un côté: la cryptographie est évidemment une application positive d'un problème de calcul difficile. Ce serait un exemple d'application d'un théorème de complexité en dehors du champ de complexité qui est négatif . Êtes-vous particulièrement intéressé par l'un par rapport à l'autre, @rphv?
Daniel Apon
1
Je suis intéressé par les applications positives et négatives. Si l'existence de problèmes de calcul difficiles est analogue à 2LOT ou C, alors je pense que nous devrions souvent nous heurter à des exemples / conséquences, tout comme nous rencontrons souvent des objets du monde réel qui `` incarnent '' ces propriétés (moteurs de voiture, électricité, etc.) Même si nous ne «tirons rien» (comme la crypto) du fait qu'il existe des problèmes difficiles, je pense qu'il pourrait être utile de considérer l'existence de problèmes difficiles en pensant au monde. En d'autres termes, "Comment l'existence de problèmes difficiles affecte-t-elle nos vies?"
rphv
3

BPPP=BPP

Mohammad Al-Turkistany
la source
2

En supposant que des fonctions "dures" existent (pour une variété de définitions de "dures"), nous pouvons construire des générateurs pseudo-aléatoires.

Dana Moshkovitz
la source