No estoy seguro de la traducción del título. "nutshell" es algo así como cáscara de nuez, y es un término utilizado para referirnos a que un tema esta explicado en forma breve pero completo a la vez. En este caso el tema sería Complejidad Computacional.
Complejidad computacional es un área de las ciencias de la computación teórica que estudia la dificultad de resolver problemas computacionales. La dificultad de un problema computacional se mide en términos de los recursos computacionales necesarios para resolver ese problema, por ejemplo, tiempo, memoria, conectividad en la red, número de procesadores etc. El objetivo principal es crear una clasificación (estricta) de problemas computacionales. Esa clasificación son las clases de complejidad. Por ejemplo, los problemas que no requieren mucho tiempo ni mucha memoria se les llama problemas de tipo P. Problemas que requieren mas tiempo, pero aun con poca memoria son NP, y así.
También existe la complejidad computacional cuántica, que estudia la complejidad de las máquinas cuánticas. Más adelante voy a preparar una entrada sobre el tema.
Me gustaría compartir una serie de cursos impartidos en UC Berkeley dictados por Luca Trevisan sobre complejidad computacional. Los materiales para su curso los fue distribuyendo via su propio blog. Fue capaz de explicar temas relativamente difíciles de una forma breve y a la vez clara. Simplemente me encanta las matemáticas de esta área, sin dudad una de las invenciones más bellas de la mente humana.
Para más detalles sobre el área recomiendo el libro Computational Complexity: A Modern Approach. Este libro está muy actualizado, y explica los conceptos de una forma bien clara
