The Complexity of Propositional Proofs (Q5444711)

scientific article; zbMATH DE number 5240886

Language	Label	Description	Also known as
English	The Complexity of Propositional Proofs	scientific article; zbMATH DE number 5240886

Statements

instance of

scholarly article

0 references

title

The Complexity of Propositional Proofs (English)

0 references

author

Nathan Segerlind

0 references

published in

Bulletin of Symbolic Logic

0 references

publication date

25 February 2008

0 references

full work available at URL

https://projecteuclid.org/euclid.bsl/1203350879

0 references

zbMATH Keywords

propositional proof complexity

0 references

resolution

0 references

Frege systems

0 references

pigeonhole principle

0 references

random restriction

0 references

survey

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems

0 references

Q4662832

0 references

On Interpolation and Automatization for Frege Systems

0 references

Lower bounds for cutting planes proofs with small coefficients

0 references

Short proofs are narrow—resolution made simple

0 references

Near optimal seperation of tree-like and general resolution

0 references

The Efficiency of Resolution and Davis--Putnam Procedures

0 references

Lower bounds for the weak pigeonhole principle and random formulas beyond resolution

0 references

On the automatizability of resolution and related propositional proof systems

0 references

Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms

0 references

Space Complexity in Propositional Calculus

0 references

The complexity of the pigeonhole principle

0 references

Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis

0 references

The proof complexity of linear algebra

0 references

A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution

0 references

Exponential separation between Res($k$) and Res($k+1$) for $k \leqslant \varepsilon\log n$

0 references

Q4220572

0 references

Provability of the pigeonhole principle and the existence of infinitely many primes

0 references

Existence and feasibility in arithmetic

0 references

A lower bound for the complexity of Craig's interpolants in sentential logic

0 references

Resolution cannot polynomially simulate compressed-BFS

0 references

The intractability of resolution

0 references

Hiding propositional constants in BDDs.

0 references

Outline of an algorithm for integer solutions to linear programs

0 references

Sharp thresholds of graph properties, and the $k$-sat problem

0 references

$\text{Count}(q)$ does not imply $\text{Count}(p)$

0 references

Resolution lower bounds for perfect matching principles

0 references

Lower bounds for the polynomial calculus

0 references

Resolution lower bounds for the weak pigeonhole principle

0 references

Linear-size constant-depth polylog-threshold circuits

0 references

Q5286672

0 references

Lower bounds for resolution and cutting plane proofs and monotone computations

0 references

Lower bounds to the size of constant-depth propositional proofs

0 references

Exponential lower bounds for the pigeonhole principle

0 references

Optimal proof systems imply complete sets for promise classes

0 references

Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations

0 references

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

0 references

Expander graphs and their applications

0 references

A machine program for theorem-proving

0 references

Space bounds for resolution

0 references

A new proof of the weak pigeonhole principle

0 references

On the complexity of resolution with bounded conjunctions

0 references

An accurate and scalable collaborative recommender

0 references

A Computing Procedure for Quantification Theory

0 references

Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs

0 references

Q4856172

0 references

An overview of backtrack search satisfiability algorithms

0 references

Cones of Matrices and Set-Functions and 0–1 Optimization

0 references

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

0 references

Some consequences of cryptographical conjectures for $S_2^1$ and EF

0 references

Propositional proof systems, the consistency of first order theories and the complexity of computations

0 references

On the weak pigeonhole principle

0 references

Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic

0 references

The relative efficiency of propositional proof systems

0 references

Many hard examples for resolution

0 references

Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)

0 references

Good degree bounds on Nullstellensatz refutations of the induction principle

0 references

Q4365127

0 references

Linear gaps between degrees for the polynomial calculus modulo distinct primes

0 references

Bounded arithmetic, proof complexity and two papers of Parikh

0 references

Propositional consistency proofs

0 references

Polynomial size proofs of the propositional pigeonhole principle

0 references

Q3794177

0 references

Q3002766

0 references

Homogenization and the polynomial calculus

0 references

Identifiers

zbMATH Open document ID

1133.03037

0 references

DOI

10.2178/bsl/1203350879

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5444711