Anwendungen der Komplexitätstheorie

18

Die Komplexitätstheorie scheint etwas Grundlegendes über die Struktur des Universums zu erfassen, indem sie die intuitive Vorstellung formalisiert, dass einige Probleme schwieriger sind als andere.

Scott Aaronson prognostizierte : "Die NP-Härteannahme wird letztendlich als analog zum zweiten Hauptsatz der Thermodynamik oder als Unmöglichkeit der überluminalen Signalübertragung angesehen."

Sogenannte "harte Probleme" sind die Basis der modernen Kryptographie.

Gibt es andere Anwendungen, die rechnerisch schwierige Probleme nutzen, von ihnen abhängen oder deren Existenz veranschaulichen?

cc.complexity-theory soft-question big-picture rphv
quelle

Antworten:

14

Die jüngste Ausgabe des CACM enthält einen Artikel von Faliszewski, Hemaspaandra und Hemaspaandra über die Anwendung der Komplexitätstheorie im Bereich der Theorie sozialer Entscheidungen und des Wahldesigns . Ein Beispiel für ein solches Ergebnis ist, dass der Satz von Arrow zwar garantiert, dass ein Wahlsystem „hackbar“ ist, dies jedoch möglicherweise nur schwer möglich ist.

Suresh Venkat
quelle
1
Ich habe dieses Papier nicht gelesen, aber es scheint, dass der Autor sichere E-Voting-Systeme entwirft. Ist das nicht eine Anwendung der Kryptographie auf Sicherheitssysteme? Beachten Sie, dass das OP nach Anwendungen für schwierige Probleme auf anderen Gebieten als der Kryptographie fragt .
MS Dousti
2
Nein, das ist nicht ganz richtig. Sie beschäftigen sich mit der Mathematik von Wahlsystemen und versuchen zu verstehen, wie die Perspektive der Komplexitätstheorie die Designentscheidungen verändert. Zum Beispiel ist eines von drei Schemata, die ähnlich aussehen, schwer zu hacken und das andere nicht. Es ist eine rechnerische Sicht auf die Theorie der sozialen Wahl, ähnlich wie die moderne Krypto eine rechnerische Sicht auf die Verschlüsselung von Geheimnissen bietet .
Suresh Venkat
7

ϵϵ1/ϵ

Daniel Apon
quelle
Nebenbei bemerkt: Kryptographie ist offensichtlich eine positive Anwendung eines rechnerisch schwierigen Problems. Dies wäre ein Beispiel für die Anwendung eines Komplexitätssatzes außerhalb des Komplexitätsfeldes, der negativ ist . Interessieren Sie sich besonders für eine über die andere, @rphv?
Daniel Apon
1
Ich interessiere mich sowohl für positive als auch für negative Bewerbungen. Wenn die Existenz von rechenintensiven Problemen analog zu 2LOT oder C ist, dann sollten wir häufig auf Beispiele / Konsequenzen davon stoßen, so wie wir häufig auf reale Objekte stoßen, die diese Eigenschaften "verkörpern" (Automotoren, Elektrizität usw.) Auch wenn wir nichts (wie Krypto) aus der Tatsache "herausbekommen", dass harte Probleme existieren, halte ich es für nützlich, die Existenz harter Probleme in Betracht zu ziehen, wenn wir über die Welt nachdenken. Mit anderen Worten: "Wie wirkt sich die Existenz schwerer Probleme auf unser Leben aus?"
RPHV
3

BPPP=BPP

Mohammad Al-Turkistany
quelle
2

Unter der Annahme, dass "harte" Funktionen existieren (für eine Vielzahl von Definitionen von "hart"), können wir Pseudozufallsgeneratoren konstruieren.

Dana Moshkovitz
quelle