Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Hunter Monroe:

TR22-076 | 16th May 2022
Hunter Monroe

Average-Case Hardness of Proving Tautologies and Theorems

We consolidate two widely believed conjectures about tautologies---no optimal proof system exists, and most require superpolynomial size proofs in any system---into a $p$-isomorphism-invariant condition satisfied by all paddable $\textbf{coNP}$-complete languages or none. The condition is: for any Turing machine (TM) $M$ accepting the language, $\textbf{P}$-uniform input families requiring superpolynomial time ... more >>>

TR09-056 | 20th June 2009
Hunter Monroe

Speedup for Natural Problems and coNP?=NP

Revisions: 2

Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a ... more >>>

ISSN 1433-8092 | Imprint