Original Article: Computability and Complexity Theory
Author: Steven Homer and Alan L. Selman

Teoria da computabilidade e complexidade

Segunda edição

Steven Homer e Alan L. Selman

Springer Verlag New York, 2011

ISBN 978-1461406815

 

Esta edição revisada e expandida da Teoria da Computabilidade e Complexidade compreende materiais essenciais que são o conhecimento central na teoria da computação. O livro é autônomo, com um capítulo preliminar descrevendo conceitos e notações matemáticas chave e capítulos subseqüentes que se deslocam dos aspectos qualitativos da teoria da computação clássica para os aspectos quantitativos da teoria da complexidade. Capítulos dedicados sobre indecidibilidade, NP-completeness e computação relativa encerram a primeira edição, que enfoca as limitações da computabilidade e as distinções entre viável e intratável.

O novo conteúdo substancial nesta segunda edição inclui:

*um capítulo sobre não-conformidade estudando circuitos booleanos, aulas de conselhos e o importante resultado de Karp-Lipton

*definições e propriedades das classes de complexidade probabilística fundamental

*um estudo da máquina de Turing alternada e classes de circuitos uniformes

*uma introdução às aulas de contagem, incluindo os resultados de Valiant e Vazirani e de Today

*um tratamento completo da prova de que o IP é idêntico ao PSPACE

Tópicos e recursos:

*Os materiais concisos e focados cobrem os conceitos e resultados mais fundamentais no campo da teoria da complexidade moderna, incluindo a teoria da NP-completude, NP-dureza, a hierarquia polinomial e problemas completos para outras classes de complexidade

*Contém informações que, de outro modo, existem apenas na literatura de pesquisa e a apresentam de forma unificada e simplificada; por exemplo, sobre complementos de classes de complexidade, problemas de busca e problemas intermediários em teoria de complexidade NP, não uniforme e paralela, aulas de complexidade probabilística, aulas de contagem e sistemas de prova interativa.

*Fornece informações básicas de fundo matemático, incluindo seções sobre lógica e teoria dos números e álgebra

*Apoiado por inúmeros exercícios e problemas suplementares para fins de reforço e auto-estudo.

Com sua acessibilidade e organização bem planejada, este texto / referência é um excelente recurso e guia para aqueles que procuram desenvolver uma base sólida na teoria da computação. Graduados iniciantes, graduados avançados e profissionais envolvidos em informática teórica, teoria da complexidade e computabilidade encontrarão o livro uma ferramenta de aprendizagem essencial e prática..

 

Índice


  1. PRELIMINARES
    • Palavras e idiomas
    • Representação K-adic
    • Funções Parciais
    • Gráficos
    • Lógica proposicional
    • Cardinalidade
    • Álgebra elementar
  2. INTRODUÇÃO À COMPUTABILIDADE
    • Turing Machines
    • Turing-Machine Conceitos
    • Variações de Turing Machines
    • Tese de Igreja
    • RAMs
  3. DESABILITAÇÃO
    • Problemas de decisão
    • Problemas indecidíveis
    • Funções de emparelhamento
    • Conjuntos computavelmente enumeráveis
    • Parando Problemas, Reduções e Conjuntos Completos
    • S-m-n Teorema
    • Teorema de Recursão
    • Teorema de arroz
    • Turing Reductions e Oracle Turing Machines
    • Teorema de Recursão, Continuação
    • referências
    • Problemas adicionais de lição de casa
  4. INTRODUÇÃO À TEORIA DE COMPLEXIDADE
    • Classes de complexidade e medidas de complexidade
    • Pré-requisitos
  5. RESULTADOS BÁSICOS DA TEORIA DE COMPLEXIDADE
    • Compressão linear e aceleração
    • Funções construtivas
    • Redução de fita
    • Relacionamentos de inclusão
      • Relações entre as Classes Padrão
    • Resultados de separação
    • Técnicas de tradução e preenchimento
    • Relações entre as Classes Padrão - Continuação
      • Complementos de Classes de Complexidade: O teorema de Immerman-Szelepcsenyi
    • Problemas adicionais de lição de casa
  6. NONDETERMINISMO E NP-INTEGRIDADE
    • Caracterizando NP
    • A Classe P
    • Enumerações
    • NP-Completude
    • O teorema de Cook-Levin
    • Mais problemas NP-Complete
    • Problemas adicionais de lição de casa
  7. COMPUTABILIDADE RELATIVA
    • NP-Dureza
    • Problemas de pesquisa
    • A Estrutura do NP
      • Número Composto e Isomorfismo Gráfico
      • Reflexão
    • A Hierarquia Polinomial
    • Problemas completos para outras classes de complexidade
    • Problemas adicionais de lição de casa
  8. COMPLEXIDADE NONUNIFORME
    • Famílias de circuitos polinomiais de circuitos
      • Aconselhamento Classes
    • As hierarquias baixa e alta
  9. PARALELISMO
    • Máquinas Alternativas de Turing
    • Famílias uniformes de circuitos
    • Problemas altamente paralelizáveis
    • Condições de uniformidade
    • Máquinas Alternativas de Turing
  10. CLASSES DE COMPLEXIDADE PROBABILISTA
    • A Classe PP
    • A Classe RP
      • A Classe ZPP
    • A Classe BPP
    • Funções de Hash aleatoriamente escolhidas
      • Operadores
    • O problema do isomorfismo gráfico
    • Problemas adicionais de lição de casa
  11. INTRODUÇÃO NAS CLASSES DE CONTABILIDADE
    • Satisfação Única
    • Teorema de Toda
      • Resultados em BPP e Parity P
    • Problemas adicionais de lição de casa
  12. SISTEMAS DE PROVA INTERNACIONAL
    • O Modelo Formal
    • O problema do gráfico não isomorfista
    • Arthur-Merlin Games
    • IP está incluído na PSPACE
    • PSPACE está incluído no IP
    • Problemas adicionais de lição de casa