Recientemente comencé a leer mucho sobre la complejidad de las pruebas y realmente he disfrutado lo que he estado leyendo. Realmente me gustaría aprender más sobre esto, pero estoy teniendo dificultades para encontrar un buen material para principiantes para comenzar. ¿Alguien podría recomendar algunos conceptos básicos?
cc.complexity-theory
lo.logic
proof-complexity
Yugioh Mishima
fuente
fuente
Respuestas:
Depende del tipo de nivel de "principiante" que desee tener. No creo que haya un texto de nivel universitario realmente bueno sobre la complejidad de la prueba (esto probablemente sea cierto para la mayoría de las subáreas especializadas en complejidad). Pero para un principiante (nivel de posgrado), recomendaría algo así como comprender bien el tamaño exponencial básico límite inferior en las refutaciones de resolución del principio de casillero (a través de restricciones aleatorias, compensación de tamaño de ancho e interpolación factible), y ampliar a partir de eso señalar más. Esto podría lograrse (aproximadamente) de la siguiente manera:
Stasys Jukna, Combinatoria extrema con aplicaciones en informática, 2001, Springer-Verlag, Sección 4.8.
Eli Ben-sasson y Avi Wigderson, Las pruebas cortas son estrechas - Resolución simplificada (2000), JACM.
P. Beame y T. Pitassi, Complejidad de prueba proposicional: pasado, presente y futuro, Tendencias actuales en informática teórica: entrando en el siglo XXI (G. Paul, G. Rozenberg y A. Salomaa, editores), World Scientific Publishing , 2001, págs.42-70.
Pavel Pudlák, límites inferiores para resolución y corte de planos, pruebas y cálculos monótonos, The Journal of Symbolic Logic, vol. 62 (1997), no. 3, págs. 981-998.
También puede consultar el texto más extenso y autónomo:
Para el lado más lógico de la complejidad de la prueba, como sugirió Kaveh, puede comenzar a leer los primeros capítulos de:
fuente
Para el lado más algebraico de la complejidad de la prueba, recomiendo comenzar con el trabajo de la encuesta de Pitassi de 1996:
Para obtener una descripción general rápida, también puede consultar el Capítulo 5 del libro Clote - Kranakis ya mencionado por Iddo, que tiene una sección sobre sistemas de prueba algebraicos.
El primer artículo de investigación que recomendaría leer (tanto porque es seminal como porque es una lectura agradable) es el documento en el que se introdujo el sistema de prueba Groebner o de cálculo polinómico:
fuente
Encuentro que estas notas introductorias son fáciles de leer: Conferencias IAS de Paul Beame
fuente
La encuesta de complejidad de prueba de propósito general más reciente y actualizada es probablemente la de Nathan Segerlind:
Nathan Segerlind: la complejidad de las pruebas proposicionales. Boletín de Symbolic Logic 13 (4): 417-481, 2007 ( http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps ).
Y ahora, advertencias para dos autoenchufes desvergonzados ...
Una encuesta aún más reciente, pero más centrada en preguntas sobre el tamaño de prueba, el espacio de prueba y las compensaciones de espacio de tamaño, es:
Jakob Nordström. Juegos de guijarros, complejidad de prueba y compensaciones espacio-temporales. Métodos lógicos en informática, volumen 9, número 3, artículo 15, septiembre de 2013 ( http://www.lmcs-online.org/ojs/viewarticle.php?id=674 ).
También hay algunas notas de clase de un curso algo reciente que di sobre el "espectro de gama baja" de la complejidad de la prueba (es decir, sistemas de prueba comparativamente débiles como resolución, cálculo polinómico y planos de corte) y conexiones a la resolución SAT. Estas notas se pueden encontrar en http://www.csc.kth.se/~jakobn/teaching/proofcplx11/#scribe-notes (algunas todavía están en progreso, pero las que están disponibles deben estar en buena forma).
fuente