Aplicaciones de la teoría de la complejidad.

18

La teoría de la complejidad parece capturar algo fundamental sobre la estructura del universo, ya que formaliza la noción intuitiva de que algunos problemas son más difíciles que otros.

Scott Aaronson predijo : "El supuesto de dureza NP eventualmente será visto como análogo a la segunda ley de la termodinámica o imposibilidad de señalización superluminal".

Los llamados "problemas difíciles" son la base de la criptografía moderna.

¿Hay alguna otra aplicación que utilice, dependa o ejemplifique la existencia de problemas computacionalmente difíciles?

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

Respuestas:

14

El número más reciente del CACM tiene un artículo de Faliszewski, Hemaspaandra y Hemaspaandra sobre el uso de la teoría de la complejidad en el ámbito de la teoría de la elección social y el diseño electoral en particular. Un ejemplo de tal resultado es que, si bien el teorema de Arrow garantiza que cualquier sistema electoral es 'pirateable', podría ser NP-difícil hacerlo.

Suresh Venkat
fuente
1
No leí ese documento, pero parece que el autor está diseñando sistemas seguros de votación electrónica. ¿No es una aplicación de criptografía para sistemas de seguridad? Tenga en cuenta que el OP solicita aplicaciones de problemas difíciles a campos distintos de la criptografía.
MS Dousti
2
No, eso no está del todo bien. Están analizando las matemáticas de los sistemas de votación e intentando entender cómo la perspectiva de la teoría de la complejidad cambia las elecciones de diseño. Por ejemplo, entre tres esquemas que se parecen, uno es NP-difícil de hackear y los otros no. Es una vista computacional sobre la teoría de la elección social, al igual que la criptografía moderna brinda una perspectiva computacional sobre la codificación de secretos.
Suresh Venkat
7

Esta encuesta de 2009 realizada por Daskalakis examina la complejidad de calcular los equilibrios de Nash. Su trabajo anterior con Goldberg y Papadimitriou demostró que calcular exactamente tales equilibrios es completo para PPAD. Esta no es una afirmación tan fuerte como si el problema fuera NP-duro, pero aún proporciona evidencia de que calcular los equilibrios de Nash es intratable, lo que pone en duda el poder predictivo de los equilibrios de Nash. Una salvación sería demostrar un PTAS para equilibrios -Nash para la precisión deseada . Pero el mejor actual es un algoritmo de aproximación no ajeno que se ejecuta en el tiempo cuasipolinomial en .ϵ 1 / ϵϵϵ1/ϵ

Daniel Apon
fuente
Un aparte: la criptografía es obviamente una aplicación positiva de un problema computacionalmente difícil. Este sería un ejemplo de una aplicación de un teorema de complejidad fuera del campo de complejidad que es negativo . ¿Estás particularmente interesado en uno sobre el otro, @rphv?
Daniel Apon el
1
Estoy interesado en aplicaciones positivas y negativas. Si la existencia de problemas computacionalmente difíciles es análoga a 2LOT o C, entonces siento que deberíamos toparnos con ejemplos / consecuencias a menudo, al igual que a menudo nos encontramos con objetos del mundo real que 'encarnan' esas propiedades (motores de automóviles, electricidad, etc.) Incluso si no "obtenemos nada" (como la criptografía) del hecho de que existen problemas difíciles, creo que podría ser útil considerar la existencia de problemas difíciles al pensar en el mundo. En otras palabras, "¿Cómo afecta la existencia de problemas difíciles a nuestras vidas?"
rphv
3

Para agregar a la respuesta de Dana que básicamente dice que la dureza se puede convertir en aleatoriedad. La existencia de funciones duras con límite inferior de complejidad de circuito exponencial se puede utilizar para desrandomizar eficientemente cada algoritmo probabilístico en . Esto implicaría .P = B P PBPPP=BPP

Mohammad Al-Turkistany
fuente
2

Suponiendo que existan funciones "duras" (para una variedad de definiciones de "duras"), podemos construir generadores pseudoaleatorios.

Dana Moshkovitz
fuente