Método de forzamiento utilizado en el papel de relativización de Baker-Gill-Solovay y la Prueba de independencia de hipótesis continua de Cohen

En general, estoy interesado en el método de forzamiento utilizado por Baker-Gill-Solovay y Cohen. Estoy buscando tantas fuentes como pueda tener en cuenta en relación con la técnica en sí o su uso. ¿Alguien tiene sugerencias?

Para más usos del forzado (a través de los llamados oráculos genéricos) en la teoría de la complejidad, consulte The Oracle Builder's Toolkit ( disponible gratuitamente en la página de inicio de Fortnow ) por Fenner, Fortnow, Kurtz y Li. Ofrecen una teoría general de los oráculos genéricos y muestran sus numerosas aplicaciones en complejidad.

Si está interesado en cómo los oráculos en complejidad son como pruebas de independencia en la teoría de conjuntos, es posible que le interesen los siguientes documentos:

• Arora, Impagliazzo, Vazirani. Técnicas relativizantes versus no relativizantes: el papel de la verificación local .

• Impagliazzo, Kabanets, Kolokolova. Un enfoque axiomático para la algebrización . ( versión completa disponible gratuitamente en la página de inicio de Kabanets )

Para los usos del forzamiento en la teoría de conjuntos, vea el libro Set Theory ( Set Theory on Amazon ) de Jech, especialmente las partes II y III del libro (no debe confundirse con "Introducción a la teoría de conjuntos" de Hrbáček y Jech).

Para una excelente introducción al forzamiento en la teoría de conjuntos, está la famosa publicación USENET de Timothy Chow "Forcing for dummies" , así como el artículo más formal que surgió de él, "Una guía para principiantes para forzar" .

Para los usos de forzar técnicas similares en la complejidad de la prueba, es posible que desee ver:

• M. Ajtai. La complejidad del principio del casillero . En Actas del 29º Simposio Anual de IEEE sobre Fundamentos de Ciencias de la Computación, White Plains, NY, 1988, pp. 346–355; y

• M. Ajtai. La complejidad del principio del casillero . Combinatorica 14 (1994), no. 4, 417–433.

El método de prueba es un análogo aritmético de forzamiento (del tipo ya utilizado por Paris y Wilkie). Más combinatorios (y límites inferiores mejorados) se encuentran en J. Krajıcek, P. Pudlak y A. Woods, límites inferiores exponenciales al tamaño de la profundidad acotada Pruebas de frege del principio del palomar , Algoritmos de estructuras aleatorias, 7 (1995), pp. 15-39. y T. Pitassi, PW Beame y R. Impagliazzo, Límites inferiores exponenciales para el principio del casillero , Comput. Complejidad, 3 (1993), pp. 97-140.

Ver también:

• $p$

• Soren Riis. Finización en aritmética limitada . 1994, BRICS, Departamento de Informática de la Universidad de Aarhus.

Recientemente, Jan Krajicek publicó un libro que unifica estas técnicas de forzamiento:

• J. Krajicek. Forzar con variables aleatorias y complejidad de prueba . Cambridge University Press, diciembre de 2010. ( Borrador disponible en la página de inicio de Krajicek )

ver también Forzar en la teoría de la prueba de Avigad, 30pp, 2004. cita BGS75 pero no en detalle. Hay alguna referencia a Scott / Solovay como una reformulación de forzar a modelos con valores booleanos.

Las ideas para forzar han influido en la complejidad computacional; por ejemplo, la separación de clases de complejidad relavitizadas a un oráculo (por ejemplo, como en BGS75) a menudo se puede ver como versiones de forzamiento dependientes de los recursos.