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

PRELIMINARES
- Palavras e idiomas
- Representação K-adic
- Funções Parciais
- Gráficos
- Lógica proposicional
- Cardinalidade
- Álgebra elementar
INTRODUÇÃO À COMPUTABILIDADE
- Turing Machines
- Turing-Machine Conceitos
- Variações de Turing Machines
- Tese de Igreja
- RAMs
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
INTRODUÇÃO À TEORIA DE COMPLEXIDADE
- Classes de complexidade e medidas de complexidade
- Pré-requisitos
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
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
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
COMPLEXIDADE NONUNIFORME
- Famílias de circuitos polinomiais de circuitos
  - Aconselhamento Classes
- As hierarquias baixa e alta
PARALELISMO
- Máquinas Alternativas de Turing
- Famílias uniformes de circuitos
- Problemas altamente paralelizáveis
- Condições de uniformidade
- Máquinas Alternativas de Turing
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
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
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

homeyou