Failure of the strong feasible disjunction property
This result addresses a foundational question in proof complexity, showing that a key property fails under standard complexity assumptions, which is incremental as it builds on prior work.
The paper tackles the problem of whether proof systems have the strong feasible disjunction property, proving that no sufficiently strong proof system admits this property under two computational complexity hypotheses.
A propositional proof system $P$ has the strong feasible disjunction property iff there is a constant $c \geq 1$ such that whenever $P$ admits a size $s$ proof of $\bigvee_i α_i$ with no two $α_i$ sharing an atom then one of $α_i$ has a $P$-proof of size $\le s^c$. It was proved by K. (2025) that no proof system strong enough admits this property assuming a computational complexity conjecture and a conjecture about proof complexity generators. Here we build on Ilango (2025) and Ren et al. (2025) and prove the same result under two purely computational complexity hypotheses: - there exists a language in class E that requires exponential size circuits even if they are allowed to query an NP oracle, - there exists a P/poly demi-bit in the sense of Rudich (1997).