Existem referências (online ou em forma de livro) que organizam e discutem os teoremas do TCS pela técnica de prova? Garey e Johnson fazem isso para os vários tipos de construções de widgets necessários para as provas de completude do NP (particularmente no capítulo 3 do livro), mas estou pensando se há algo que trate as técnicas de prova no TCS de maneira mais ampla.
Por exemplo, os tópicos podem incluir diagonalização, discriminada ainda mais pelo tipo de construção usada; provas por histórias de computação; construções de quadros; argumentos de incompressibilidade, etc. Suponho que eu poderia apenas detalhar uma teoria padrão do texto de computação e reorganizar as seções, mas seria ótimo se houver algo lá fora que também forneça alguns comentários adicionais e mostre onde existem pontos em comum entre as técnicas utilizadas. usava.
Só para esclarecer, como qualquer texto usará provas, o que estou realmente interessado em encontrar é uma referência em que as técnicas de prova sejam o assunto real.
Além do capítulo 3 de Garey e Johnson, aqui está outro exemplo parcial que me ocorreu: em Li e Vitanyi , no capítulo 6 eles discutem o método da incompressibilidade e dão exemplos de como aplicar a técnica.
Respostas:
The Complexity Theory Companion de Hemaspaandra e Ogihara . Não é exaustivo em termos de técnicas (imagino que não exista), mas acho que se qualifica como resposta à sua pergunta. Aqui estão os títulos dos capítulos:
fonte
Aqui está outro livro em que os capítulos são mais focados em técnicas de prova.
"Combinatória Extremal com Aplicações em Ciência da Computação", por Stasys Jukna. É um bom livro e abrange muitas combinações que você pode precisar no TCS. É claro que seu assunto não inclui diagonalização, tabelas, etc., mas é uma coleção de técnicas combinatórias organizadas que procuram um aplicativo (e em vários locais do texto, os aplicativos são explicitados).
Um "rascunho inicial" da segunda edição está disponível aqui .
fonte
Sanjeev Arora tem um bom conjunto de notas que ele chama de "Um kit de ferramentas para teóricos"
fonte
O livro "Gemas da Ciência da Computação Teórica" é uma boa maneira de aprender muitas técnicas diferentes (embora você veja cada uma delas aplicada apenas uma vez):
http://www.calvin.edu/~rpruim/publications/gems/
fonte
Existe um wiki dedicado a diferentes técnicas de prova: http://www.tricki.org/ (parece inspirado em Timothy Gowers).
fonte
Outras técnicas são úteis em muitas partes da ciência da computação teórica:
Noga Alon e Joel H. Spencer, The Probabilistic Method (3a edição), Wiley, ISBN 0470170204.
fonte
S. Fenner, L. Fortnow, S. Kurtz e L. Li. Um kit de ferramentas do construtor oracle. Information and Computation, 182 (2): 95-136, 2003. (também disponível na página inicial de Lance ).
Este é basicamente um documento de pesquisa sobre o uso da genéricos na construção de "oráculos projetados" (ou seja, oráculos projetados para ter várias propriedades). Embora seja um artigo, acho que se qualifica como resposta à pergunta, porque está focado na técnica e em seus usos, e não em qualquer resultado específico. [Mas isso é muito mais específico que o Companheiro da teoria da complexidade, e é por isso que pensei que deveria estar em uma resposta separada.]
fonte
Iniciamos algumas perguntas de referência no cs.SE cobrem problemas típicos (até o momento introdutórios) do TCS. Além da relevância geral, algumas respostas contêm métodos que podem não ser conhecidos por todo pesquisador, por exemplo:
Também temos Como não resolver P = NP? que é mais sobre anti-técnicas.
fonte
No mesmo espírito das anotações de Sanjeev Arora que a @umar postou, gosto das anotações e exercícios da aula de Madhur Tulsiani para a aula "Mathematics Toolkit" publicada na página do curso . Além do excelente material de Arora, suas anotações têm uma boa cobertura da teoria dos grafos espectrais, bem como do método de atualização dos pesos multiplicativos.
fonte