Bom texto sobre introdução à complexidade do circuito

15

Gostaria de pedir sugestões de bons textos que introduzam a complexidade do circuito. Qualquer indicação de avanços recentes e problemas em aberto nesse campo também seria útil.

shrm
fonte

Respostas:

14

Além dos sugeridos por Arnab, eu também recomendaria o seguinte livro:

Introdução à complexidade do circuito: uma abordagem uniforme por Heribert Vollmer

Robin Kothari
fonte
1

Modelos de computação por John E Savage (mais informações / detalhes / críticas na amazon ). é em grande parte mais um livro didático de graduação, mas é notável por seu ponto de vista central. inclui muitos tópicos / provas avançados, e é gratuito on-line, e possui um link muito bom (TOC, refs, índice, etc.).

vzn
fonte