Livre | Chapitre
A straightforward proof of Köbler-Messner's result
pp. 67-75
Résumé
Proof systems for classical propositional logic, previously studied only by logicians, now are the subject of intensive research in computer science. There is a special branch of Theoretical Computer Science, named as Proof Complexity Theory, which is concerned with proving lower bounds on the length of proofs in different propositional proof systems and with comparing their efficiency. The study on the complexity of propositional proof systems is motivated by the open question NP=co-NP? This question, closely related to the famous P=NP? problem, can be stated as a problem on the length of proofs in propositional calculus.
Détails de la publication
Publié dans:
Rojszczak Artur, Cachro Jacek, Kurczewski Gabriel (2003) Philosophical dimensions of logic and science: selected contributed papers from the 11th international congress of logic, methodology, and philosophy of science, Kraków, 1999. Dordrecht, Springer.
Pages: 67-75
DOI: 10.1007/978-94-017-2612-2_6
Citation complète:
Sadowski Zenon, 2003, A straightforward proof of Köbler-Messner's result. In A. Rojszczak, J. Cachro & G. Kurczewski (eds.) Philosophical dimensions of logic and science (67-75). Dordrecht, Springer.