On the public citation graph

Complexity of finding short resolution proofs

https://doi.org/10.1007/bfb0029974
0 signed · 42 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-56992-8_22openalex-snapshot
Solving 3-satisfiability in less than 1, 579n steps
inferredcites →https://doi.org/10.1016/0166-218x(85)90050-2openalex-snapshot
Solving satisfiability in less than 2n steps
inferredcites →https://doi.org/10.1016/0196-6774(86)90032-5openalex-snapshot
Algorithms for maximum independent sets
inferredcites →https://doi.org/10.1016/0304-3975(85)90144-6openalex-snapshot
The intractability of resolution
inferredcites →https://doi.org/10.1016/0304-3975(91)90315-sopenalex-snapshot
Counting the number of solutions for instances of satisfiability
inferredcites →https://doi.org/10.1109/sct.1995.514725openalex-snapshot
Intractability of read-once resolution
inferredcites →https://doi.org/10.1109/sfcs.1996.548486openalex-snapshot
Simplified and improved resolution lower bounds
inferredcites →https://doi.org/10.1109/tc.1986.1676847openalex-snapshot
An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
inferredcites →https://doi.org/10.1145/237814.237860openalex-snapshot
Using the Groebner basis algorithm to find proofs of unsatisfiability

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/spmi.2002.1039openalex-snapshot
A complete set of transformation rules for quantum Boolean circuits with CNOT gates
inferred← citeshttps://doi.org/10.1007/3-540-36184-7_7openalex-snapshot
On Determining the Minimum Length, Tree-Like Resolution Refutation of 2SAT, and Extended 2SAT Formulas
inferred← citeshttps://doi.org/10.1007/978-3-030-14812-6_36openalex-snapshot
Read-Once Certification of Linear Infeasibility in UTVPI Constraints
inferred← citeshttps://doi.org/10.1007/978-3-319-78455-7_23openalex-snapshot
Optimal Length Tree-Like Refutations of Linear Feasibility in UTVPI Constraints
inferred← citeshttps://doi.org/10.1007/978-3-540-24605-3_6openalex-snapshot
Density Condensation of Boolean Formulas
inferred← citeshttps://doi.org/10.1007/978-3-540-28639-4_20openalex-snapshot
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets
inferred← citeshttps://doi.org/10.1007/bf03037305openalex-snapshot
Transformation rules for CNOT-based quantum circuits and their applications
inferred← citeshttps://doi.org/10.1007/bfb0029943openalex-snapshot
Mathematical Foundations of Computer Science 1997
inferred← citeshttps://doi.org/10.1007/bfb0055766openalex-snapshot
Minimum propositional proof length is NP-hard to linearly approximate
inferred← citeshttps://doi.org/10.1007/s00037-025-00271-wopenalex-snapshot
Quantum Automating TC0-Frege Is LWE-Hard
inferred← citeshttps://doi.org/10.1007/s00153-009-0152-4openalex-snapshot
Pool resolution is NP-hard to recognize
inferred← citeshttps://doi.org/10.1007/s00453-019-00554-zopenalex-snapshot
A Polynomial Time Algorithm for Read-Once Certification of Linear Infeasibility in UTVPI Constraints
inferred← citeshttps://doi.org/10.1007/s10472-021-09762-2openalex-snapshot
Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
inferred← citeshttps://doi.org/10.1007/s12532-021-00202-0openalex-snapshot
Computational aspects of infeasibility analysis in mixed integer programming
inferred← citeshttps://doi.org/10.1016/j.dam.2006.04.014openalex-snapshot
Density condensation of Boolean formulas
inferred← citeshttps://doi.org/10.1016/j.dam.2020.10.016openalex-snapshot
Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints
inferred← citeshttps://doi.org/10.1016/j.procs.2021.11.021openalex-snapshot
Automating Tree-Like Resolution in Time n(log ) Is ETH-Hard
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.005openalex-snapshot
On finding short resolution refutations and small unsatisfiable subsets
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.01.039openalex-snapshot
The NP-hardness of finding a directed acyclic graph for regular resolution
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.02.018openalex-snapshot
Finding a tree structure in a resolution proof is NP-complete
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.08.017openalex-snapshot
Copy complexity of Horn formulas with respect to unit read-once resolution
inferred← citeshttps://doi.org/10.1017/s096012952000016xopenalex-snapshot
NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
inferred← citeshttps://doi.org/10.1017/s0960129523000300openalex-snapshot
Constrained read-once refutations in UTVPI constraint systems: A parallel perspective
inferred← citeshttps://doi.org/10.1023/b:amai.0000012871.08577.0bopenalex-snapshot
Upper and Lower Bounds on the Complexity of Generalised Resolution and Generalised Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1109/focs.2019.00038openalex-snapshot
Automating Resolution is NP-Hard
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743514openalex-snapshot
Exponential separations between restricted resolution and cutting planes proof systems
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959895openalex-snapshot
Resolution is not automatizable unless W[P] is tractable
inferred← citeshttps://doi.org/10.1145/3357713.3384248openalex-snapshot
Automating cutting planes is NP-hard
inferred← citeshttps://doi.org/10.1145/3406325.3451080openalex-snapshot
Automating algebraic proof systems is NP-hard
inferred← citeshttps://doi.org/10.1145/976706.976711openalex-snapshot
Optimal length tree-like resolution refutations for 2SAT formulas
inferred← citeshttps://doi.org/10.2307/2694916openalex-snapshot
Minimum propositional proof length is NP-hard to linearly approximate
inferred← citeshttps://doi.org/10.33915/etd.3843openalex-snapshot
Analyzing Satisfiability and Refutability in Selected Constraint Systems
inferred← citeshttps://doi.org/10.70675/5732022dzaf3bz44e9zae98z41d4facf3deaopenalex-snapshot
Contributions à la résolution du problème de la Satisfiabilité Propositionnelle
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.