scientific article; zbMATH DE number 1179974
From MaRDI portal
Publication:4399249
zbMATH Open0908.68164MaRDI QIDQ4399249FDOQ4399249
Authors: Toniann Pitassi, Paul Beame 
Publication date: 14 March 1999
Title of this publication is not available (Why is that?)
Recommendations
Cited In (45)
- Proving the infeasibility of Horn formulas through read-once resolution
- Characterizing propositional proofs as noncommutative formulas
- A syntactical proof of the Marriage Lemma.
- Reflections on Proof Complexity and Counting Principles
- Title not available (Why is that?)
- Short Proofs for the Determinant Identities
- Towards NP-P via proof complexity and search
- The complexity of the Hajós calculus for planar graphs
- The Complexity of Propositional Proofs
- Combinatorics of first order structures and propositional proof systems
- Proof compressions with circuit-structured substitutions
- Proof theory
- Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints
- Copy complexity of Horn formulas with respect to unit read-once resolution
- Mean-payoff games and propositional proofs
- Finding read-once resolution refutations in systems of 2CNF clauses
- Resolution lower bounds for the weak functional pigeonhole principle.
- Propositional proof systems and fast consistency provers
- Optimal length resolution refutations of difference constraint systems
- Different approaches to proof systems
- A finite-model-theoretic view on propositional proof complexity
- Complexity of propositional proofs (invited talk)
- Resolution lower bounds for perfect matching principles
- Rigorous results for random (\(2+p)\)-SAT
- A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
- A unified framework for DPLL(T) + certificates
- Unrestricted vs restricted cut in a tableau method for Boolean circuits
- Upper bounds on complexity of Frege proofs with limited use of certain schemata
- Propositional proof complexity
- Computational properties of argument systems satisfying graph-theoretic constraints
- NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
- Theorem Proving in Higher Order Logics
- Title not available (Why is that?)
- Title not available (Why is that?)
- Proof compression and NP versus PSPACE. II
- On the computational complexity of read once resolution decidability in 2CNF formulas
- The complexity of finding read-once NAE-resolution refutations
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Towards NP-P via proof complexity and search
- Narrow proofs may be maximally long
- Two party immediate response disputes: Properties and efficiency
- Title not available (Why is that?)
- A surprising relationship between descriptive complexity and proof complexity
- Logical Approaches to Computational Barriers
- Proof Compression and NP Versus PSPACE II: Addendum
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4399249)
