Zastosowania teorii złożoności

18

Teoria złożoności wydaje się uchwycić coś fundamentalnego w strukturze wszechświata, ponieważ formalizuje intuicyjne przekonanie, że niektóre problemy są trudniejsze niż inne.

Scott Aaronson przewidział : „Założenie o twardości NP będzie w końcu postrzegane jako analogiczne do drugiej zasady termodynamiki lub niemożności sygnalizacji nadświetlnej”.

Tak zwane „trudne problemy” są podstawą współczesnej kryptografii.

Czy są jakieś inne aplikacje, które wykorzystują, zależą lub ilustrują istnienie trudnych obliczeniowo problemów?

cc.complexity-theory soft-question big-picture

— rphv
źródło

14

W najnowszym numerze CACM znajduje się artykuł autorstwa Faliszewskiego, Hemaspaandry i Hemaspaandry na temat wykorzystania teorii złożoności w szczególności w dziedzinie teorii wyboru społecznego i projektowania wyborów. Jednym z przykładów takiego wyniku jest to, że chociaż twierdzenie Arrow daje gwarancję, że każdy system wyborczy jest „hakujący”, może to być trudne.

— Suresh Venkat
źródło

1

Nie przeczytałem tego artykułu, ale wydaje się, że autor projektuje bezpieczne systemy głosowania elektronicznego. Czy to nie jest zastosowanie kryptografii do systemów bezpieczeństwa? Zauważ, że OP prosi o zastosowanie trudnych problemów w polach innych niż kryptografia.

— MS Dousti,

2

Nie, to nie do końca prawda. Analizują matematykę systemów głosowania i starają się zrozumieć, w jaki sposób perspektywa teorii złożoności zmienia wybory projektowe. Na przykład spośród trzech schematów, które wyglądają podobnie, jeden jest trudny do zhakowania przez NP, a inne nie. Jest to obliczeniowe spojrzenie na teorię wyboru społecznego, podobnie jak współczesne krypto daje obliczeniową perspektywę kodowania tajemnic.

— Suresh Venkat

7

$\epsilon$ $\epsilon$ $1/\epsilon$

— Daniel Apon
źródło

Na marginesie: kryptografia jest oczywiście pozytywnym zastosowaniem trudnego obliczeniowo problemu. Byłby to przykład zastosowania twierdzenia o złożoności poza polem złożoności, które jest ujemne . Czy szczególnie interesuje Cię jedno nad drugim, @rphv?

— Daniel Apon

1

Interesują mnie zarówno pozytywne, jak i negatywne aplikacje. Jeśli istnienie trudnych obliczeniowo problemów jest analogiczne do 2LOT lub C, to czuję, że powinniśmy często wpadać na przykłady / konsekwencje tego, podobnie jak często spotykamy rzeczywiste obiekty, które „ucieleśniają” te właściwości (silniki samochodowe, elektryczność itp.) Nawet jeśli „nie dostaniemy niczego” (np. krypto) z powodu istnienia trudnych problemów, myślę, że warto rozważyć istnienie trudnych problemów podczas myślenia o świecie. Innymi słowy: „Jak istnienie trudnych problemów wpływa na nasze życie?”

— rphv

3

$BPP$ $P=BPP$

— Mohammad Al-Turkistany
źródło

2

Zakładając, że istnieją „twarde” funkcje (dla różnych definicji „twardych”), możemy konstruować generatory pseudolosowe.

— Dana Moshkovitz
źródło