The fundamental question underlying directly or indirectly most of my research is this (I borrow last sentences from Sec.22.4 of my 2019 CUP book):

  • What is the nature of proof complexity?

That is, what are the intrinsic reasons that some formulas are hard to prove? Can the proof complexity of some formulas be traced to the computational complexity of associated computational tasks? Which mathematical structures relate to the existence of feasible proofs?

These questions have many technical mathematical facets, the most famous being the P vs. NP problem and its variants. Some of them are studied in my CUP books (1995, 2011 and 2019).

Imprint Privacy policy « This page (revision-9) was last changed on Wednesday, 26. July 2023, 15:47 by Krajicek Jan
  • operated by