Under the assumptions of an E-language requiring exponential NP-oracle circuits and a P/poly demi-bit, strong propositional proof systems lack the strong feasible disjunction property.
Kraj´ ıˇ cek, Proof complexity generators
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Failure of the strong feasible disjunction property
Under the assumptions of an E-language requiring exponential NP-oracle circuits and a P/poly demi-bit, strong propositional proof systems lack the strong feasible disjunction property.