Je voudrais demander des suggestions de bons textes qui introduisent la complexité du circuit. Des indications sur les avancées récentes et les problèmes ouverts dans ce domaine seraient également utiles.
15
Je voudrais demander des suggestions de bons textes qui introduisent la complexité du circuit. Des indications sur les avancées récentes et les problèmes ouverts dans ce domaine seraient également utiles.
Pour commencer, il y a bien sûr le livre d'Arora et Barak Computational Complexity: A Modern Approach . À partir de là, les parties 3 et 4 du livre de Jukna intitulé Boolean Function Complexity: Advances and Frontiers constituent un excellent matériel de lecture. En outre, Ryan Williams donne un bon cours sur la complexité des circuits dont les notes de cours pourraient être mises en ligne, espérons-le :)
En plus de ceux suggérés par Arnab, je recommanderais également le livre suivant:
la source
Modèles de calcul par John E Savage (plus d'infos / détail / avis sur amazon ). C'est en grande partie un manuel de premier cycle, mais il est remarquable pour son point de vue centré sur les circuits. comprend de nombreux sujets avancés / preuves, et son gratuit en ligne, et est très bien hyperlien (TOC, refs, index, etc.).
la source