Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANGE AVOIDANCE PROBLEM:
Reports tagged with range avoidance problem:
TR22-120 | 24th August 2022
Jan Krajicek

On the existence of strong proof complexity generators

Comments: 1

The working conjecture from K'04 that there is a proof complexity generator hard for all
proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions
as follows:
\begin{itemize}
\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>




ISSN 1433-8092 | Imprint