4 papers
Regular resolution effectively simulates resolution
Sam Buss, Emre Yolcu
Regular resolution is a refinement of the resolution proof system requiring that no variable be resolved on more than once along any path in the proof. It is known that there exist…
Lower bounds for set-blocked clauses proofs
Emre Yolcu
We study propositional proof systems with inference rules that formalize restricted versions of the ability to make assumptions that hold without loss of generality, commonly used…
Exponential separations using guarded extension variables
Emre Yolcu, Marijn J. H. Heule
We study the complexity of proof systems augmenting resolution with inference rules that allow, given a formula in conjunctive normal form, deriving clauses that are not necess…
An Automated Approach to the Collatz Conjecture
Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
We explore the Collatz conjecture and its variants through the lens of termination of string rewriting. We construct a rewriting system that simulates the iterated application of t…