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:

TR23-047 | 2nd April 2023
Hunter Monroe

Ruling Out Short Proofs of Unprovable Sentences is Hard

If no optimal propositional proof system exists, we (and independently Pudlák) prove that ruling out length $t$ proofs of any unprovable sentence is hard. This mapping from unprovable to hard-to-prove sentences powerfully translates facts about noncomputability into complexity theory. For instance, because proving string $x$ is Kolmogorov random ($x{\in}R$) is ... more >>>

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