Recentemente, comecei a ler muito sobre a complexidade das provas e realmente gostei do que estava lendo. Eu realmente gostaria de aprender mais sobre isso, mas estou tendo dificuldades para encontrar um bom material para iniciantes, para começar. Alguém seria capaz de recomendar alguns princípios?
cc.complexity-theory
lo.logic
proof-complexity
Yugioh Mishima
fonte
fonte
Respostas:
Depende do tipo de nível "iniciante" que você deseja ter. Eu não acho que exista um bom texto de nível de graduação sobre a complexidade da prova (isso provavelmente é verdade para a maioria das subáreas especializadas em complexidade). Mas para fontes iniciantes (nível de pós-graduação), eu recomendaria, algo como entender bem o tamanho exponencial básico mais baixo nas refutações de resolução do princípio do buraco de pombo (via restrições aleatórias, troca de tamanho de largura e interpolação viável) e expandir a partir disso apontar mais. Isso pode ser alcançado (aproximadamente) da seguinte maneira:
Stasys Jukna, Combinação Extremal com Aplicações em Ciência da Computação, 2001, Springer-Verlag, Seção 4.8.
Eli Ben-sasson e Avi Wigderson, Short Proofs are Narrow - Resolução simplificada (2000), JACM.
P. Beame e T. Pitassi, Complexidade da prova proposicional: Passado, presente e futuro, Tendências atuais da ciência da computação teórica: Entrando no século XXI (G. Paul, G. Rozenberg e A. Salomaa, editores), World Scientific Publishing , 2001, pp. 42--70.
Pavel Pudlák, Limites inferiores para resolução e provas de planos de corte e cálculos monótonos, The Journal of Symbolic Logic, vol. 62 (1997), n. 3, pp. 981-998.
Você também pode consultar o texto mais autônomo e longo:
Para o lado mais lógico da complexidade da prova, como sugeriu Kaveh, você pode começar a ler os primeiros capítulos de:
fonte
Para o lado mais algébrico da complexidade da prova, recomendo começar com o trabalho de pesquisa de Pitassi em 1996:
Para uma rápida visão geral, você também pode consultar o Capítulo 5 do livro Clote - Kranakis já mencionado por Iddo, que possui uma seção sobre sistemas de prova algébrica.
O primeiro trabalho de pesquisa que eu recomendo a leitura (tanto por ser seminal quanto por ser uma leitura agradável) é o artigo em que o sistema de prova de cálculo de Groebner ou Polynomial foi introduzido:
fonte
Acho estas notas introdutórias de aula fáceis de ler: as palestras IAS de Paul Beame
fonte
A pesquisa de complexidade à prova de propósito geral mais recente e atualizada é provavelmente a de Nathan Segerlind:
Nathan Segerlind: A complexidade das provas proposicionais. Boletim da Lógica Simbólica 13 (4): 417-481, 2007 ( http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps ).
E agora, avisos para dois auto-plugues descarados ...
Uma pesquisa ainda mais recente, mas mais focada em questões relacionadas ao tamanho e ao espaço da prova e às trocas de espaço por tamanho, é:
Jakob Nordström. Jogos de calhau, complexidade de prova e compensações de tempo e espaço. Métodos lógicos em ciência da computação, volume 9, edição 3, artigo 15, setembro de 2013 ( http://www.lmcs-online.org/ojs/viewarticle.php?id=674 ).
Há também algumas notas de aula de um curso um pouco recente que eu dei sobre o "espectro low-end" da complexidade da prova (isto é, sistemas de prova comparativamente fracos, como resolução, cálculo polinomial e planos de corte) e conexões com a solução SAT. Essas notas podem ser encontradas em http://www.csc.kth.se/~jakobn/teaching/proofcplx11/#scribe-notes (algumas ainda estão em andamento, mas as que estão disponíveis devem estar em boa forma).
fonte