Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > METAMATHEMATICS:
Reports tagged with Metamathematics:
TR24-190 | 22nd November 2024
Jiawei Li, Yuhao Li, Hanlin Ren

Metamathematics of Resolution Lower Bounds: A TFNP Perspective

This paper studies the \emph{refuter} problems, a family of decision-tree \mathrm{TFNP} problems capturing the metamathematical difficulty of proving proof complexity lower bounds. Suppose \varphi is a hard tautology that does not admit any length-s proof in some proof system P. In the corresponding refuter problem, we are given (query ... more >>>




ISSN 1433-8092 | Imprint