Non basta sapere come programmare: bisogna anche sapere che cosa si può davvero calcolare in modo efficiente. La teoria della complessità risponde proprio a questa domanda. Questo libro offre un accesso chiaro, rigoroso e progressivo ai temi centrali dell’informatica teorica: P e NP, riduzioni, NP-completezza, approssimazione, sistemi di prova interattivi, teoria PCP e complessità della comunicazione. Con uno stile didattico e intuitivo, Lucien Sina spiega non solo i risultati, ma anche le idee che li rendono comprensibili. Esempi, dimostrazioni ed esercizi con soluzioni aiutano a consolidare i contenuti e a sviluppare un vero senso per i limiti del calcolo efficiente. La teoria della complessità mostra quanto siano profondamente intrecciate teoria e pratica dell’informatica — e perché conoscere i confini del possibile sia spesso il primo passo per ampliarli in modo creativo.
