scientific article
From MaRDI portal
Publication:3689182
zbMath0572.03034MaRDI QIDQ3689182
A. J. Wilkie, Jeffrey Bruce Paris
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
The complexity of the pigeonhole principle, Approximate counting and NP search problems, A generalized Grzegorczyk hierarchy and low complexity classes, Circuit principles and weak pigeonhole variants, \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\), Cutting planes, connectivity, and threshold logic, Typical forcings, NP search problems and an extension of a theorem of Riis, \(\text{Count}(q)\) does not imply \(\text{Count}(p)\), Transfinite induction within Peano arithmetic, An exponential separation between the parity principle and the pigeonhole principle, Some consequences of cryptographical conjectures for \(S_2^1\) and EF, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\), Computation models and function algebras, Some consequences of cryptographical conjectures for S 2 1 and EF, Towards NP-P via proof complexity and search, On the computational complexity of cut-reduction, A note on SAT algorithms and proof complexity, Build your own clarithmetic I: Setup and completeness, Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem, Resolution proofs of generalized pigeonhole principles, The canonical pairs of bounded depth Frege systems, A new proof of the weak pigeonhole principle, Combinatorial principles in elementary number theory, Partially definable forcing and bounded arithmetic, The treewidth of proofs, On the correspondence between arithmetic theories and propositional proof systems – a survey, Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\), A Characterisation of Definable NP Search Problems in Peano Arithmetic, Induction rules in bounded arithmetic, Bounded arithmetic, proof complexity and two papers of Parikh, A model-theoretic characterization of the weak pigeonhole principle, Nonerasing, counting, and majority over the linear time hierarchy, On the complexity of counting in the polynomial hierarchy
