P. Hájek, P. Pudlák: Metamathematics of first order arithmetic, Springer-Verlag/ASL Perspectives in Logic, 1993, 460 pp. (corrections)
P. Pudlák: The lengths of proofs, in Handbook of Proof Theory, S.R. Buss ed., Elsevier, 1998, pp.547-637.
P. Pudlák: Logical Foundations of Mathematics and Computational Complexity, a gentle introduction. Springer-Verlag, 2013, 695 pp. ( preface and table of contents, corrections)
P. Pudlák: A new proof of the congruence lattice representation theorem , Algebra Universalis, Vol.6, 1976, pp.269-275.
P. Pudlák, J. Tůma: Yeast graphs and fermentation of algebraic lattices. In: Coll. Math. Soc. Janos Bolyai, 14. Lattice Theory, Szeged, 1974 pp.301-341.
P. Pudlák: Distributivity of strongly representable lattices, Algebra Universalis, Vol.7, 1977, pp.85-92
P. Pudlák: Symmetric embeddings of finite lattices into finite partition lattices, Comm. Math. Univ. Carol. Vol.20, 1979, pp.183-187.
P. Pudlák, J. Tůma: Every finite lattice can be embedded in a finite partition lattice, Algebra Universalis, Vol.10, 1980, pp.74-95.
P. Pudlák, P.P. Pálfy: Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups, Algebra Universalis, Vol.11, 1980, pp.22-27.
P. Pudlák, J. Tůma: Regraphs and congruence lattices, Algebra Universalis Vol.17, 1984, pp.416-424.
P. Pudlák: On congruence lattices of lattices, Algebra Universalis Vol.20, 1985, pp.96-114. (correction)
J. Ježek, P. Pudlák, J. Tůma: On eqational theories of semilattices with operators, Bull. Austral. Math. Soc.42, (1990), pp.57-70.
P. Pudlák, V. Rodl: Partition theorems for systems of finite subsets of integers. Discrete Math., Vol.39, 1982, pp.67-73.
P. Pudlák: Boolean complexity and Ramsey theorems. In: Mathematics of Ramsey Theory, J.Nesetril and V.Rodl Eds., 1991, pp.246-252.
J. Nešetřil, P. Pudlák: A note on boolean dimension of posets. In: Proc. Irregularities of Partitions, Hungary.
P. Pudlák, P. Savický: On shifting networks, Theor. Comput. Sci. Vol.116, 1993, pp.415-419.
Alon N. P. Pudlák: Superconcentrators of depth 2 and 3; odd levels help (rarely), Journ. of Computer and System Sciences 48,1 (1994), pp.194-202.
N. Alon, P. Pudlák: Constructive lower bounds for off-diagonal Ramsey numbers, Israel Journ. of Math. 122 (2001), pp.243-251.
P. Pudlák: Cycles of nonzero elements in low rank matrices , Combinatorica 22 (2), 2002, pp.321-334 (correction)
N. Alon , P. Pudlák: Equilateral sets in lp, Geometric and Functional Analysis 13 (2003), pp. 467-482.
P. Pudlák: An application of Hindman's theorem to a problem on communication complexity, Combinatorics, Probability and Computing (2003) 12, pp. 661-670.
P. Pudlák, V. Rodl: Pseudorandom sets and explicit constructions of Ramsey graphs. Quaderni di Matematica, Vol. 13, Dipartimanto di Matematica, Seconda Universita di Napoli, Caserta - 2004, editor J. Krajíček, pp.327-346
P. Pudlák: On explicit Ramsey graphs and estimates of the number of sums and products. Topics in Discrete Mathematics, editors Klazar, Kratochvil, Loebl, Matousek, Thomas and Valter. Springer 2006, pp.169-175[a]
A. Kostochka, P. Pudlák, V. Rodl: Some constructive bounds on Ramsey numbers, Journal of Combinatorial Theory, Series B 100 (2010), pp. 439-445.
V. Cacic, P. Pudlák, G. Restall, A. Visser, A. Urquhart: Decorated linear order types and the theory of concatenation, Proc. Logic Colloquium 2007, ASL Lecture Notes in Logic, Cambridge 2010, pp. 1-13
D. Gavinsky and P. Pudlák: On the Joint Entropy of d-Wise-Independent Variables. Comment. Math. Univ. Carolin. 57,3, (2016) 333-343.
D. Gavinsky, P. Pudlák: Partition expanders. Theory of Computing Systems, Vol. 60, Issue 3, pp. 378-395 (2017) (Preliminary versions in: Proc. of 31st Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Dagstuhl, Germany, 433-447, 2014.)
D. Gavinsky and P. Pudlák: Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory of Computing Systems 64 (6), 2020, 1140-1154.
P. Pudlák and V. Rodl: Extractors for small zero-fixing sources. Combinatorica, 2022, Pages: 587 - 616.
P. Pudlák, V. Rodl: Colorings of k-sets with low discrepancy on small sets, 2024
H. Lefmann, P. Pudlák, P. Savický: On sparse parity check matrices, Codes, Designes and Cryptography 12, pp.107-130 (abstract published in Proc. COCOON 96).
R. Paturi, P. Pudlák: Circuit lower bounds and linear codes. Notes of Mathematical Seminars of St.Petersburg Department of Steklov Institute of Mathematics, vol. 316, Teoria slozhnosti vychislenij IX, E. A. Hirsch editor, 2004, pp.188-204.
A. Gál, K.A. Hansen, M. Koucký, P. Pudlák, and E. Viola. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Transactions on Information Theory, Vol. 59, No. 10, pp. 6611-6627 (preliminary version in: 44th Annual ACM Symposium on Theory of Computing, STOC'12, pp. 479-494, 2012).
P. Pudlák: Linear tree codes and the problem of explicit constructions. Linear Algebra and its Applications 490, 2016, 124-144.
P. Pudlák: On matrices potentially useful for tree codes. Information Processing Letters. Volume 174, March 2022, 106180.
P. Pudlák: Observational predicate calculus and complexity of computations, Comm. Math. Univ. Carol. Vol.16, 1975, No.2, pp.395-398.
P. Pudlák, S. Žák: Space complexity of computations. Math. Inst., CSAV, Prague, 1983, 30 pp.
P. Pudlák: Bounds for Hodes-Specker theorem. In: Logic and Machines LNCS 171, Springer Verlag, 1984 pp.421-445.
J. Morávek, P. Pudlák: New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. MFCS 1984: 416-424
P. Pudlák: A lower bound on the complexity of branching programs. In: Proc. MFCS'84 LNCS 176, Springer-Verlag, 1984 pp.480-489.
M. Ajtai , L. Babai , P. Hajnal , J. Komlos, P. Pudlák V. Rodl: Two lower bounds for branching programs. In:Proc. 18-th ACM STOC, 1986 pp.30-38.
A. Hajnal , W. Maass, P. Pudlák, M. Szegedy, G. Turan G: Threshold circuits of bounded depth. In: Proc. 28-th IEEE STOC, 1987 pp.99-110. (preliminary version of the journal article)
P. Pudlák, V. Rodl, P. Savický: Graph complexity, Acta Informatica, Vol.25, 1988 pp.515-535.
P. Duris, P. Pudlák: On the communication complexity of planarity. In: Fundamentals of Comp. Theor. '89, Springer-Verlag LNCS 380, 1989, pp.145-147.
Babai L. P. Pudlák V. Rodl Szemeredi E.: Lower bounds to the complexity of symmetric boolean functions, Theor. Comp. Sci. 74, 1990, pp.313-323.
J. Krajíček, P. Pudlák, J. Sgall : Interactive computations of optimal solutions. In: Proc. MFCS'90, Ed. B.Rovan, Springer-Verlag LNCS 452, 1990, pp.48-60.
P. Pudlák V. Rodl: A combinatorial approach to complexity, Combinatorica Vol.12(2), 1992, pp.221-226.
Hajnal A. Maass W. P. Pudlák Szegedy M. Turan G.: Threshold circuits of bounded depth. Journ. of Comput. and System Science 46 (1993), pp.129-154.
P. Pudlák, V. Rodl: Modified ranks of tensors and the size of circuits, in Proc. ACM STOC, 1993, pp.523-531.
P. Pudlák: AC0 circuit complexity. In: Proc. FCT, 1993, pp.106-120.
P. Pudlák: Unexpected upper bounds on the complexity of some communication games, in Proc. ICALP 1994,Springer-Verlag LNCS 820, pp.1-10.
P. Pudlák: Communication in bounded depth circuits, Combinatorica 14 (2) (1994), pp.203-216.
P. Pudlák V. Rodl: Some combinatorial-algebraic problems from complexity theory, Discrete Math. 136 (1994), pp.253-279.
Hastad J., Jukna S., P. Pudlák: Top-down lower bounds for depth-three circuits, Computational Complexity 5 (1995), pp.99-112 (extended abstract appeared in Proc. IEEE FOCS, 1993, pp.124-129).
P. Pudlák, J. Sgall: An upper bound for a communication game related to space-time trade-offs, in Mathematics of Paul Erdos, R.L. Graham and J. Nesetril eds., Vol I., Springer-Verlag 1997, pp.393-399.
P. Pudlák, V. Rodl, Sgall J.: Boolean circuits, tensor ranks and communication complexity, SIAM J. on Computing 26/3 (1997), pp.605-633. (comment),
P. Pudlák, Paturi R., Zane F.: Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science, December 1999. Preliminary version in Proc. 38-th FOCS, IEEE Computer Society 1997, pp. 566-574
Krause M., P. Pudlák: On the computational power of depth 2 circuits with threshold and modulo gates, Theoretical Computer Science 174 (1997), pp.137-156, (preliminary version in Proc. ACM STOC, 1994, pp.48-57)
B. Codenotti, P. Gemmell, J. Simon, P. Pudlák: On the amount of randomness needed in distributed computations, in Proc. OPODIS'97 , 1997, pp. 237-248
Krause M., P. Pudlák: Computing Boolean Functions by Polynomials and Threshold Circuits, Computational Complexity 7 (1998), pp. 346-370, preliminary version: On computing boolean functions by sparse real polynomials, appeared in Proc. IEEE FOCS 1995, pp.682-691.
P. Pudlák: Satisfiability - Algorithms and Logic, in Mathematical Foundations of Computer Science 1998, Springer LNCS 1450, pp.129-141.
Codenotti B., P. Pudlák, Resta J.: Some structural properties of low rank matrices related to computational complexity Theoretical Computer Sci. 235 (2000), pp. 89-107 ( ECCC TR97-043)
P. Pudlák: A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits. Information Processing Letters 74 (2000), pp.197-201. ( ECCC TR98-042)
A. Gal , P. Pudlák: Monotone complexity and the rank of matrices, Information Processing Letters 87 (2003), pp. 321-326.
M. Koucky, P. Pudlák, D. Therien: Bounded depth circuits: separating wires from gates. In Proc. 37th Annual ACM Symp. on Theory of Computing, 2005, pp.257-265
A. Chattopadhyay, N. Goyal, P. Pudlák, D. Therien: Lower bounds for circuits with MODm gates, Proc. 47th Annual Symp. on Foundations of Computer Science, IEEE 2006, pp.709-718 [a]
P. Hrubeš, A. Kulikov, P. Pudlák, S. Jukna: On convex complexity measures, Theoretical Computer Science 411 (2010), pp.1842-1854.
P. Pudlák: On reducibility and symmetry of disjoint NP-pairs, Theor. Comput. Science 295 (2003) 323-339, preliminary version in Proc. MFCS'01, 2001.
R. Paturi, P. Pudlák, M.E.Saks, F. Zane: An improved exponential-time algorithm for k-SAT, Journal of the ACM Vol.52, No.3, 2005, pp.337-364 (preliminary version in Proc. 39-th FOCS, IEEE 1998, pp. 628-637)
D. Gavinsky, P. Pudlák: Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity, Proc. 23rd Annual IEE Conference on Computational Complexity, 2008, pp. 332-339.
R. Paturi, P. Pudlák: On the complexity of circuit satisfiability, Proc. of the 2010 ACM STOC, pp. 241-249
M. Koucky, P. Nimbhorkar, P. Pudlák: Pseudorandom Generators for Group Products, Proc. of the 2011 ACM STOC, pp. 263-272.
P. Pudlák, D. Scheder and N. Talebanfard: Tighter Hard Instances for PPSZ Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 80, 1-13, 2017
P. Hrubeš and P. Pudlák: A note on monotone real circuits. Information Processing Letters, 131, pp. 15-19, 2018.
D. Lokshtanov, I. Mikhailin, R. Paturi, P. Pudlák: Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth. SODA 2018: 247-261
S. Gryaznov, P. Pudlák, N. Talebanfard: Linear Branching Programs and Directional Affine Extractors. Proc. Computational Complexity Conference 2022, Pages 4:1--4:16.
P. Pudlák: Some prime elements in the lattice of interpretability types, Trans. A.M.S., Vol.280, 1983, No.1, pp.225-275.
P. Pudlák: A definition of exponentiation by a bounded arithmetical formula, Comm. Math. Univ. Carol. Vol.24, 1983 No.4 pp.667-671.
P. Pudlák A. Sochor: Models of the Alternative Set Theory, Journ. Sym. Logic Vol.49, 1984 No.2 pp.570-585.
P. Pudlák A. Sochor: Elementary extensions of models of the Alternative Set Theory, Zeitschrift. fur Math. Logik, Vol.31, 1985 pp.309-316.
P. Pudlák: On the length of proofs of finitistic consistency statements in first order theories. In: Logic Colloquium 84, North Holland P.C., 1986 pp.165-196.
P. Pudlák: Improved bounds to the length of proofs of finitistic consistency statements. In: Contemporary mathematics Vol.65, 1987 pp.309-331.
P. Pudlák: Cuts, consistency statements and interpretations, Journ. Symb. Logic Vol.50, 1985, pp.423-441.
P. Pudlák: On a unification problem related to Kreisel's conjecture, Comm. Math. Univ. Carol., Vol 29,3, 1988 pp.551-556.
J. Krajíček, P. Pudlák:On the structure of initial segments of models of arithmetic, Arch. Math. Log. Vol.28, 1989, pp.91-98.
J. Mycielski, P. Pudlák, A.S. Stern: A lattice of chapters of mathematics, Memoirs AMS, Vol.84, No.426, 1990, 70 pp.
P. Pudlák: A note on bounded arithmetic, Fundamenta Mathematicae, Vol.136, No.2, 1990, pp.86-89.
J. Krajíček, P. Pudlák: Propositional provability and models of weak arithmetic. In: Proc. Computer Science Logic'89, Eds. Borger, Kleine-Buning, Richter, Springer-Verlag LNCS 440, 1990, pp.193-210.
P. Pudlák: Ramsey's Theorem in Bounded Arithmetic. In: Proc. Computer Science Logic'90, eds. E.Borger, H.Kleine Buning, M.M.Richter, W.Schonfeld, LNCS 533, Springer-Verlag, 1991, pp.308-317.
J. Krajíček, P. Pudlák Takeuti G.: Bounded arithmetic and polynomial hierarchy, Annals of Pure and Applied Logic 52,(1991), pp.143-154.
P. Pudlák: A note on applicability of the incompleteness theorem to human mind, Annals of Pure and Applied Logic 96 (1999), pp. 335-342 (pdf)
P. Pudlák: Some relations between subsystems of arithmetic and the complexity theory, Proc. Conf. Logic from Computer Science, Springer-Verlag 1992, pp.499-519.
M. Baaz, P. Pudlák: Kreisel's conjecture for LE1, in: Arithmetic Proof Theory and Computational Complexity, eds. P. Clote and J. Krajíček, Oxford Univ. Press 1993, pp.30-49.
P. Hájek , F. Montagna, P. Pudlák: Abbreviating proofs using metamathematical rules, in Arithmetic Proof Theory and Computational Complexity, eds. P. Clote and J. Krajíček, Oxford Univ. Press 1993, pp.197-221.
P. Pudlák: A bottom-up approach to foundations of mathematics, in Proc. Godel'96, Logical Foundations of Mathematics, Computer Science and Physics -- Kurt Godel's Legacy, P. Hájek ed., Springer Lecture Notes in Logic 6, pp.81-97.
P. Pudlák: On the lengths of proofs of consistency, Collegium Logicum, Annals of the Kurt-Godel-Society, Vol. 2, 1996, pp.65-86.
P. Pudlák: Parallel strategies, J. of Symb. Logic 68(4), 2003, pp.1242-1250.
P. Pudlák: Godel and computations, Proc. 21st IEEE Conference on Computational Complexity, 2006, pp.3-5, full version in ACM SIGACT News Vol. 37/4 (2006) pp.13-21
P. Pudlák: Randomness, pseudorandomness and models of arithmetic. New Studies in Weak Arithmetics, P. Cégielski and Ch. Cornaros Eds., CSLI Publications, Stanford, 2013, pp.199-216.
P. Glivicky and P. Pudlák: A wild model of linear arithmetic and discretely ordered modules. Mathematical Logic Quarterly, 63:8, pp. 501-5018, 2017.
J. Krajíček, P. Pudlák: The number of proof lines and the size of proofs in first order logic, Arch. Math. Log. Vol.27, 1988 pp.69-84.
J. Krajíček, P. Pudlák: Propositional proof systems, the consistency of first order theories and the complexity of computations, JSL Vol.54, No.3, 1989, pp.1063-1079.
J. Krajíček, P. Pudlák: Quantified propositional calculi and fragments of bounded arithmetic, Zeitschrift fur Math. Logik 36, 1990, pp.29-46.
P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi, P. Pudlák, A. Woods : Exponential lower bound to the size of bounded depth Frege proofs of the Pigeon Hole Principle, in Proc. ACM STOC, 1992, pp.200-220.
J. Krajíček,, P. Pudlák, Woods A.: Exponential lower bound to the size of bounded depth Frege proofs of the Pigeon Hole Principle, Random Structures and Algorithms, 7/1 (1995), pp.15-39.
Beame P., Impagliazzo R., J. Krajíček,, Pitassi T., P. Pudlák: Lower bounds on Hilbert's Nullstellensatz and propositional proofs, Proc. London Math. Soc. (3) 73 (1996), pp.1-26, (preliminary version in IEEE Proc. FOCS, 1994).
J. Krajíček, P. Pudlák: Some consequences of cryptographical conjectures for S21 and EF, in Logic and Computational Complexity, (proceedings of meeting held in Indianapolis 1994), Ed. D. Leivant, Springer LNCS 960, 1995, pp.210-220.
P. Pudlák, S.R. Buss: How to lie without being (easily) convicted and the lengths of proofs in proposotional claculus, in Computer Science Logic'94, Pacholski and Tiuryn eds., Springer-Verlag LNCS 933, 1995, pp.151-162.
P. Pudlák: Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic 62(3), 1997, pp.981-998.
Buss S., Impagliazzo R., J. Krajíček, P. Pudlák, A.A. Razborov J. Sgall: Proof Complexity in Algebraic Systems and constant depth Frege systems with a modular counting connective, Computational Complexity 6 (1996/97), pp. 256-298
P. Pudlák: Logic and Complexity: Independence results and the complexity of propositional calculus, in Proc. Internat. Congress of Math., Zurich, 1994 (45 min. invited lecture), pp.288-297.
P. Pudlák, J. Sgall: Algebraic models of computations and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic, ed. S. Buss, LNCS, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 39, 1998, pp. 279-295
P. Pudlák: On the complexity of propositional calculus. Sets and Proofs, Invited papers from Logic Colloquium'97, S. Barry Cooper and John K. Truss eds., Cambridge Univ. Press 1999, pp. 197-218
Impagliazzo R., P. Pudlák, Sgall J.: Lower bounds for the polynomial calculus and the Groebner basis algorithm. Comput. Complexity, 8(2) (1999), pp. 127-144.
P. Pudlák: Proofs as games , American Math. Monthly, June-July 2000, pp.541-550.
R. Impagliazzo, P. Pudlák: A lower bound for DLL algorithms for k-SAT, SODA 2000, pp. 128-136
S. Buss, P. Pudlák: On the computational content of intuitionistic propositional proofs Annals of Pure and Applied Logic 109 (2001), pp. 49-64.
A. Atserias, N. Galesi , P. Pudlák: Monotone simulations of nonmonotone proofs, J. of Computer and System Sciences 65 (2002), pp.626-638, (preliminary version in Proc. 16th IEEE Conf. on Computational Complexity 2001, 36-41)
P. Pudlák: Consistency and games - in search of new combinatorial principles. Proc. Logic Colloquium'03, Helsinki, eds. V. Stoltenberg-Hansen and J. Vaananen, Assoc. for Symbolic Logic 2006, pp.244-281
P. Pudlák: Superexponential computations in exponential domain (Extended abstract of a lecture at JAF, Seville 11.6.2007)
P. Pudlák: Quantum deduction rules, Annals of Pure and Applied Logic 157 (2009), pp.16-29.
P. Pudlák: Fragments of Bounded Arithmetic and the lengths of proofs, Journal of Symbolic Logic 73/4 (2008), pp. 1389-1406.
P. Pudlák: Twelve problems in proof complexity, Proc. 3rd International Computer Science Symposium in Russia, CSR 2008, pp.13-27
P. Pudlák: On extracting computations from propositional proofs. Proc. Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai, 2010, Leibnitz International Proceedings in Informatics, pp.30-41
P. Pudlák, N. Thapen: Alternating minima and maxima, Nash equilibria and Bounded Arithmetic, Annals of Pure and Applied Logic 163 (2012), pp. 604-614.
P. Pudlák: A lower bound on the size of resolution proofs of the Ramsey theorem, Information Processing Letters 112 (14-15), 2012, pp. 610-611.
A. Beckmann, P. Pudlák, N. Thapen: Parity games and propositional proofs, ACM Transaction on Computational Logic, Vol 15:2, article 17, 2014.
P. Pudlák: On the complexity of finding falsifying assignments for Herbrand disjunctions. Archive for Mathematical Logic, 54 (7), 2015, 769-783.
M. Lauria, P. Pudlák, V. Rodl and N. Thapen: The complexity of proving that a graph is Ramsey. Combinatorica 37:2, 253-268, 2017, (preliminary version in ICALP 2013, Lecture Notes in Computer Science Volume 7965, 2013, pp 684-695.)
N. Galesi, P. Pudlák and N. Thapen: The space complexity of cutting planes refutations. Computational Complexity Conference 2015, LIPIcs, Leibniz-Zentrum für Informatik, Dagstuhl, 2015, 433-447.
P. Pudlák: Incompleteness in the finite domain. Bulletin of Symbolic Logic, 23:4, pp. 405-441, 2017.
M. de Oliveira Oliveira and P. Pudlák: Representation of monotone Boolean functions by linear programs. ACM Transactions on Computation Theory (TOCT) Volume 11 Issue 4, September 2019 Article No. 22, pp. 1-32. (Preliminary versions in: Computational Complexity Conference 2017, Leibniz International Proceedings in Informatics, 79, pp. 1-14, 2017.)
P. Pudlák and N. Thapen: Random resolution refutations. Computational Complexity, Vol 28:2, pp. 185-239, 2019 (Preliminary version in: Proc. Computational Complexity Conference 2017, Leibniz International Proceedings in Informatics, 79, pp.1-10, 2017)
P. Hrubeš and P. Pudlák: Random formulas, monotone circuits, and interpolation. 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pp. 121-131, 2017
P. Pudlák: Reflection principles, propositional proof systems, and theories, 2020
P. Pudlák: The canonical pairs of bounded depth Fege systems. Annals of Pure and Applied Logic 172, 2021.
P. Pudlák: Complexity theory and genetics: The computational power of crossing over, Information and Computation 171, (2001), pp.201-223; preliminary version appeared in IEEE Proc. Structure in Complexity Theory 1994, pp.383-395. (Both papers are shorter versions; here is the full version pdf)
Pavel Pudlák, Petr Pudlák: Does dominance-recessiveness have a survival value?