EuDML | Browse

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}})$ .

Binary consistent choice on pairs and a generalization of Konig's infinity lemma

Paul Howard (1984)

Fundamenta Mathematicae

Computational complexity of a statistical theoremhood testing procedure for propositional calculus with pseudo-random inputs

Ivan Kramosil (1981)

Kybernetika

Die Vollständigkeit einer unverzweigten Variante des "analytischen" Entscheidungsverfahrens der klassischen Logik.

P. Lorenzen (1977)

Archiv für mathematische Logik und Grundlagenforschung

Ein Satz über reproduktive Lösungen.

S.B. Presic (1972)

Publications de l'Institut Mathématique [Elektronische Ressource]

Eine semantische Charkterisierung der durch die Implikation allein darstellbaren Wahrheitsfunktionen.

R. Villars (1966)

Archiv für mathematische Logik und Grundlagenforschung

Essai sur la généralisation naturelle de la logique usuelle (premier mémoire)

Dominique Dubarle (1989)

Mathématiques et Sciences Humaines

From two- to four-valued logic

Chris Brink (1993)

Banach Center Publications

The purpose of this note is to show that a known and natural four-valued logic co-exists with classical two-valued logic in the familiar context of truth tables. The tool required is the power construction.

Currently displaying 1 – 20 of 62

Page 1 Next

Displaying 1 – 20 of 62

A Completness Theorem For One Class Of The Propositional Calculi

A generalization of the propositional calculus for purposes of the theory of logical nets with probabilistic elements

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

A measure theoretic approach to logical quantification

An application of logical-probabilistic expressions to the realization of stochastic automata

An introduction to algorithmic logic. Metamathematical investigations in the theory of programs

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

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

Binary consistent choice on pairs and a generalization of Konig's infinity lemma

Computational complexity of a statistical theoremhood testing procedure for propositional calculus with pseudo-random inputs

Die Vollständigkeit einer unverzweigten Variante des "analytischen" Entscheidungsverfahrens der klassischen Logik.

Ein Satz über reproduktive Lösungen.

Eine semantische Charkterisierung der durch die Implikation allein darstellbaren Wahrheitsfunktionen.

Essai sur la généralisation naturelle de la logique usuelle (premier mémoire)

From two- to four-valued logic

GUHA - metoda systematického vyhledávání hypotéz

GUHA - metoda systematického vyhledávání hypotéz. II

Harmonische Analysis bei Aussagenkalkülen.

How Berger, Felzenbaum and Fraenkel revolutionized Covering Systems the same way that George Boole revolutionized Logic.

How to generalize logic programming to arbitrary set of clauses.

Currently displaying 1 – 20 of 62