1. On a p-optimal proof system for the set of all satisfiable boolean formulas (SAT) (ps). Presented at 3rd International Conference on Machines, Computations and Universality, MCU'2001, Chisinau, Moldova, May 23-28, 2001.
2. A straightforward proof of Koebler-Messner's result (ps). Presented at 11th International Congress of Logic, Methodology and Philosophy of Science, LMPS'99. Abstract (ps) from Volume of abstracts of invited lectures and contributed papers published by the Faculty of Philosophy, Jagiellonian University.
3. On an optimal propositional proof system and the structure of easy subsets of TAUT (ps). To be published in Theoretical Computer Science.
4. Complexity-theoretic consequences of the existence of optimal proof systems (ps). Presented at Collegium Logicum 1998: Complexity , Vienna October 9-10, 1998.
5. On an optimal deterministic algorithm for SAT (ps). Presented at CSL’98 The final version in Springer Lecture Notes in Computer Science 1584 pp.179-187
6. On the development of Emil Post’s ideas in structural complexity theory (ps). Presented at Warsztaty Logiki, Informatyki i Filozofii Nauki w stulecie urodzin Emila Posta. Bia³ystok, 13-14 grudnia 1997. Emil Post was born in Augustow near Bialystok in 1897.
7. On an optimal quantified propositional proof system and a complete language for NP intersected with co-NP (ps). In Proc. 11th International Symposium on Fundamentals of Computing Theory, FCT’97 Lecture Notes in Computer Science #1279, pp. 423-428. Springer-Verlag, 1997.
Abstract
In this paper we develope a connection between optimal propositional proof systems and structural complexity theory - specifically there exists an optimal propositional proof system if and only if there is a suitable recursive presentation of the class of all easy (polynomial time recognizable) subsets of TAUT. As a corollary we have obtained the result that if there does not exist an optimal propositional proof system, then for every theory T there exist an easy subset of TAUT which is not T-provably easy.
9. “O pewnym sformu³owaniu problemu NP=co-NP?” Zeszyty naukowe Filii UW w Bia³ymstoku, Zeszyt 59, Tom VII, str. 19-32, 1988.
10. “On connections between parallel programs and nondeterministic sequential programs”. Fundamenta Informaticae 6, pp. 171- 183, 1983.
Abstract
This paper contains an affirmative answer to the following question: Does nondeterministic sequential program equivalent with respect to the set of final valuations exist for every parallel program with semantics defined in paper [3]? It also includes an example of the construction of a nondeterministic sequential program equivalent with respect to the set of final valuations to the given parallel program.
sadowski@math.uwb.edu.pl