Em geral, estou interessado no método de forçar usado por Baker-Gill-Solovay e Cohen. Estou procurando o maior número possível de fontes sobre a própria técnica ou seu uso. Alguém tem sugestões?
cc.complexity-theory
set-theory
djkern
fonte
fonte
Respostas:
Para mais usos de forçar (via chamados oráculos genéricos) na teoria da complexidade, consulte O Oracle Builder's Toolkit ( disponível gratuitamente na página inicial da Fortnow ) por Fenner, Fortnow, Kurtz e Li. Eles dão uma teoria geral dos oráculos genéricos e mostram suas muitas aplicações em complexidade.
Se você estiver interessado em saber como os oráculos em complexidade são como provas de independência na teoria dos conjuntos, você pode estar interessado nos seguintes artigos:
Arora, Impagliazzo, Vazirani. Técnicas de relativização versus não relativização: o papel da verificação local .
Impagliazzo, Kabanets, Kolokolova. Uma abordagem axiomática da algebrização . ( versão completa disponível gratuitamente na página inicial da Kabanets )
Para os usos de forçar na teoria dos conjuntos, consulte o livro Teoria dos Conjuntos ( Teoria dos Conjuntos na Amazônia ), de Jech, especialmente as Partes II e III do livro (não confunda com "Introdução à Teoria dos Conjuntos", de Hrbáček e Jech).
fonte
Para uma excelente introdução ao forçamento na teoria dos conjuntos, há o famoso post da USENET, de Timothy Chow, "Forçando para manequins" , bem como o artigo mais formal que surgiu a partir dele, "Um guia para iniciantes sobre forçar" .
fonte
Para usos de forçar técnicas semelhantes na complexidade da prova, você pode querer considerar:
M. Ajtai. A complexidade do princípio do buraco de pombo . Em Anais do 29º Simpósio Anual do IEEE sobre Fundamentos da Ciência da Computação, White Plains, NY, 1988, pp. 346–355; e
M. Ajtai. A complexidade do princípio do buraco de pombo . Combinatorica 14 (1994), n. 4, 417-433.
O método de prova é um análogo aritmético de forçar (do tipo já usado por Paris e Wilkie). Mais combinatórios (e limites inferiores melhorados) estão em J. Krajıcek, P. Pudlak e A. Woods, limites inferiores exponenciais ao tamanho das profundidades limitadas Provas de Frege do princípio do pombo , Random Structures Algorithms, 7 (1995), pp. 15-39. e T. Pitassi, PW Beame e R. Impagliazzo, Limites inferiores exponenciais para o princípio do buraco de pombo , Comput. Complexidade, 3 (1993), pp. 97-140.
Veja também:
Miklos Ajtai. A independência do módulop Princípios de contagem . ECCC 1994.
Soren Riis. Finitização em aritmética limitada . 1994, BRICS, Departamento de Ciência da Computação da Universidade de Aarhus.
Recentemente, Jan Krajicek publicou um livro que unifica essas técnicas de forçamento:
fonte
veja também Forcing in proof theory por Avigad, 30pp, 2004. ele cita BGS75, mas não em detalhes. há alguma referência a Scott / Solovay como uma reformulação do forçamento para modelos com valor booleano.
fonte