Please note that this newsitem has been archived, and may contain outdated information or links.
7 - 8 July 2018, Workshop on Proof Complexity 2018 (PC 2018), Oxford, England
Proof complexity is the study of the complexity of theorem proving procedures. The central question in proof complexity is: given a theorem F and a proof system P, what is the size of the smallest proof of F in the system P? Moreover, how difficult is it to construct a small proof? Many ingenious techniques have been developed to try to answer these questions, which bare tight relations to intricate theoretical open problems from computational complexity (such as the celebrated P vs. NP problem), mathematical logic (e.g. separating theories of Bounded Arithmetic) as well as to practical problems in SAT/QBF solving.
The workshop will be part of FLoC and will be affiliated with the conferences SAT'18 and LICS'18.
We welcome 1-2-page abstracts presenting (finished, ongoing, or if clearly stated even recently published) work on proof complexity. Particular topics of interest are Proof Complexity, Bounded Arithmetic, Relations to SAT/QBF solving, and Relations to Computational Complexity. The abstracts will appear in electronic pre-proceedings that will be distributed at the meeting. Accepted communications must be presented at the workshop by one of the authors.
Please note that this newsitem has been archived, and may contain outdated information or links.