Referencias para técnicas de prueba TCS

38

¿Hay alguna referencia (en línea o en forma de libro) que organice y discuta los teoremas de TCS mediante la técnica de prueba? Garey y Johnson hacen esto para los diversos tipos de construcciones de widgets necesarios para las pruebas de integridad de NP (particularmente en el capítulo 3 de su libro), pero me pregunto si hay algo que trate las técnicas de prueba en TCS de manera más amplia.

Entonces, por ejemplo, los temas pueden incluir la diagonalización, desglosada por el tipo de construcción utilizada; pruebas por historiales de cómputo; construcciones de cuadros; argumentos de incompresibilidad, etc. Supongo que podría cortar una teoría estándar del texto de cómputo y reorganizar las secciones, pero sería genial si hay algo por ahí que también proporcione algunos comentarios adicionales y muestre dónde hay puntos en común entre las técnicas que están siendo usado.

Para ser claros, dado que cualquier texto va a usar pruebas, lo que realmente me interesa encontrar es una referencia donde las técnicas de prueba en sí sean el tema real.

Además del capítulo 3 de Garey y Johnson, aquí hay otro ejemplo parcial que se me acaba de ocurrir: en Li y Vitanyi , en el capítulo 6, discuten el método de incompresibilidad y dan ejemplos de cómo aplicar la técnica.

reference-request proof-techniques Kurt
fuente
este libro es ideal para la complejidad computacional cs.princeton.edu/theory/complexity
Marcos Villagra
¡Esta es una pregunta tan amplia que su alcance es todo el campo! votar para cerrar a menos que se pueda reducir significativamente. Además, es muy probable que deba ser una wiki comunitaria, ya que no hay una respuesta definitiva única.
Suresh Venkat
1
No estoy buscando una lista de técnicas de prueba; Esperaba que ya hubiera una referencia de esta naturaleza en algún lugar al que alguien pudiera señalarme. ¿Por qué no dejar esto abierto un poco más hasta que más ojos hayan tenido la oportunidad de verlo?
Kurt
55
No puedo evitar pensar que estoy siendo malentendido aquí. Si la pregunta es demasiado amplia, entonces debería haber muchas respuestas posibles. No conozco ninguna respuesta directa (obviamente, o no hubiera preguntado), y tal vez solo un par de respuestas parciales.
Kurt
1
El problema es que la técnica de prueba en un subcampo de TCS no suele pasar a otro campo. Creo que los matemáticos suelen estudiar pruebas en sus cursos para aprender técnicas de prueba. Por ejemplo, la diagonalización no se aplica para probar que un programa es correcto, mientras que los invariantes son de poca o ninguna utilidad en la teoría de la computabilidad; Las técnicas de prueba de la complejidad amortizada solo son relevantes para ese subcampo. La reducción es inusual porque se aplica en computabilidad, complejidad y criptografía demostrable. Google "teoremas gratis" para una técnica relevante solo para programas en ciertos idiomas.
Blaisorblade

Respuestas:

36

The Complexity Theory Companion por Hemaspaandra y Ogihara . No es exhaustivo en términos de técnicas (imagino que tal libro no lo es), pero creo que califica como una respuesta a su pregunta. Aquí están los títulos de los capítulos:

  • La técnica de auto-reducción.
  • La técnica de función unidireccional.
  • La técnica de dividir y conquistar torneos.
  • La técnica de aislamiento.
  • La técnica de reducción de testigos.
  • La técnica de interpolación polinómica.
  • La técnica del grupo no solucionable.
  • La técnica de restricción aleatoria.
  • La técnica polinómica.
Joshua Grochow
fuente
1
¡Gracias! De la propaganda del editor, "... el libro es --- a diferencia de otros textos sobre complejidad --- organizado por técnica más que por tema" definitivamente parece lo que tenía en mente. (Tengo que admitir que no reconozco muchos de los títulos de los capítulos; este libro probablemente será un poco difícil para mí)
Kurt
25

Aquí hay otro libro donde los capítulos están más enfocados en técnicas de prueba.

"Combinatoria extrema con aplicaciones en informática", por Stasys Jukna. Es un buen libro y cubre una gran cantidad de combinatoria que puede necesitar en TCS. Por supuesto, su tema no incluye diagonalización, cuadros, etc., pero es una colección de técnicas combinadas ordenadas que buscan una aplicación (y en varios lugares del texto, las aplicaciones se detallan).

Un "primer borrador" de la segunda edición está disponible aquí .

Ryan Williams
fuente
Gracias, parece un texto realmente útil: me adelanté y me pedí una copia.
Kurt
15

Hay un wiki dedicado a diferentes técnicas de prueba: http://www.tricki.org/ (parece estar inspirado en Timothy Gowers).

ilyaraz
fuente
Ah, eso tiene el potencial de ser exactamente lo que esperaba. Veo que tienen entradas de marcador de posición para la complejidad computacional y los algoritmos, pero lamentablemente, hasta ahora están en blanco.
Kurt
Puedes mejorar estas secciones, creo.
ilyaraz
De hecho, probablemente aprendería un tema mejor escribiendo una nueva entrada que leyendo una existente ... un buen proyecto a largo plazo, tal vez.
Kurt
13

Otra técnica que es útil en muchas partes de la informática teórica:

Noga Alon y Joel H. Spencer, The Probabilistic Method (3rd edition), Wiley, ISBN 0470170204.

András Salamon
fuente
12

S. Fenner, L. Fortnow, S. Kurtz y L. Li. El juego de herramientas de un constructor de oráculo. Information and Computation, 182 (2): 95-136, 2003. (también disponible en la página de inicio de Lance ).

Este es básicamente un documento de encuesta sobre el uso de la genérica en la construcción de "oráculos de diseño" (es decir, oráculos diseñados para tener varias propiedades). Aunque es un documento, creo que califica como una respuesta a la pregunta porque se centra en la técnica y sus usos, en lugar de cualquier resultado en particular. [Pero esto es mucho más específico que el Complexity Theory Companion, por lo que pensé que debería estar en una respuesta separada].

Joshua Grochow
fuente
7

Hemos comenzado algunas preguntas de referencia sobre cs.SE que cubren problemas TCS típicos (hasta ahora introductorios). Además de la relevancia general, algunas respuestas contienen métodos que pueden no ser conocidos por todos los investigadores, por ejemplo en estos:

También tenemos ¿Cómo no resolver P = NP? que es más sobre antitecnicas.

Raphael
fuente
1

En el mismo espíritu de las notas de Sanjeev Arora que publicó @umar, me gustan las notas de clase y los ejercicios de Madhur Tulsiani para su clase "Mathematical Toolkit" publicada en la página web del curso . Además del excelente material de Arora, sus notas tienen una buena cobertura de la teoría de gráficos espectrales, así como del método de actualización de pesos multiplicativos.

rahulmehta95
fuente