Short Resolution refutations of Ref(φ) yield satisfying assignments for φ in polynomial time via a PV1-formalizable construction, and the Proof Analysis Problem is NP-complete for Extended Frege.
2020.102930
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
verdicts
UNVERDICTED 4representative citing papers
Introduces a rank measure for FO logic and proves a rank-preserving Gaifman normal form, yielding a simplified proof for almost-linear time decision of FO properties on nowhere-dense structures.
A geometric iteration method is developed for generalised perfect set forcing P(F), enabling its iteration with ≤κ supports along well-founded partial orders while preserving cardinals ≤κ⁺.
Satisfiability of propositional logic with nonemptiness atom NE in team semantics is NP-complete, validity coNP-complete, and model checking polynomial-time.
citing papers explorer
-
The Proof Analysis Problem
Short Resolution refutations of Ref(φ) yield satisfying assignments for φ in polynomial time via a PV1-formalizable construction, and the Proof Analysis Problem is NP-complete for Extended Frege.
-
A Rank-Preserving Gaifman Normal Form
Introduces a rank measure for FO logic and proves a rank-preserving Gaifman normal form, yielding a simplified proof for almost-linear time decision of FO properties on nowhere-dense structures.
-
Iterating Generalised Perfect Set Forcing Along Well-Founded Orders
A geometric iteration method is developed for generalised perfect set forcing P(F), enabling its iteration with ≤κ supports along well-founded partial orders while preserving cardinals ≤κ⁺.
-
Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
Satisfiability of propositional logic with nonemptiness atom NE in team semantics is NP-complete, validity coNP-complete, and model checking polynomial-time.