Proof complexity generators
Auteur :
KrajÃÄek, Jan
Éditeur :
Cambridge University Press
ISBN :
9781009611701
Date de publication :
26 juin 2025
Dimensions :
22,8 x 15,2 x 0,8 cm
Poids :
210 g
Format :
Trade paperback (US)
Langue :
Anglais
Pays d'origine :
Grande Bretagne
This book presents a state-of-the-art theory in the field of proof complexity, aiming to construct hard propositional tautologies needed to solve the P vs. NP problem in the negative. The theory is introduced step by step, starting with the historic background, and several potential new avenues of research are highlighted.