Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with feasible disjunction property:
TR20-037 | 18th March 2020
Michal Garlik

Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It

We show that for every integer $k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then ... more >>>

TR22-120 | 24th August 2022
Jan Krajicek

On the existence of strong proof complexity generators

Revisions: 1 , 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:
\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>

ISSN 1433-8092 | Imprint