EuDML | Browse

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

Subjects
03-XX Mathematical logic and foundations
03Fxx Proof theory and constructive mathematics
03F20 Complexity of proofs

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 4 of 4

A note on bounded arithmetic

P. Pudlák (1990)

Fundamenta Mathematicae

A note on proofs of falsehood.

Jan Krajicek (1987)

Archiv für mathematische Logik und Grundlagenforschung

An upper bound on the space complexity of random formulae in resolution

Michele Zito (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in $k$ -CNF on $n$ variables and $m = Δ n$ clauses is $O (n \cdot Δ^{- \frac{1}{k - 2}})$ .

An Upper Bound on the Space Complexity of Random Formulae in Resolution

Michele Zito (2010)

RAIRO - Theoretical Informatics and Applications

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is $O (n \cdot Δ^{- \frac{1}{k - 2}})$ .

Currently displaying 1 – 4 of 4

Page 1