Pages that link to "Item:Q1177041"
From MaRDI portal
The following pages link to Bounded arithmetic and the polynomial hierarchy (Q1177041):
Displaying 46 items.
- Circuit lower bounds in bounded arithmetics (Q466447) (← links)
- Lifting lower bounds for tree-like proofs (Q475337) (← links)
- Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) (Q535152) (← links)
- A simple proof of Parsons' theorem (Q558443) (← links)
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem (Q647334) (← links)
- Preservation theorems for bounded formulas (Q866887) (← links)
- Binary models generated by their tally part (Q1337500) (← links)
- Separations of theories in weak bounded arithmetic (Q1344280) (← links)
- On induction-free provability (Q1353982) (← links)
- On parallel hierarchies and \(R_k^i\) (Q1377627) (← links)
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF (Q1383164) (← links)
- A second-order system for polytime reasoning based on Grädel's theorem. (Q1412837) (← links)
- Relating the bounded arithmetic and polynomial time hierarchies (Q1899144) (← links)
- What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)? (Q1899145) (← links)
- Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
- Polynomial time ultrapowers and the consistency of circuit lower bounds (Q2288334) (← links)
- Induction rules in bounded arithmetic (Q2309507) (← links)
- Circuit principles and weak pigeonhole variants (Q2383589) (← links)
- Separations of first and second order theories in bounded arithmetic (Q2388431) (← links)
- Bounded theories for polyspace computability (Q2450770) (← links)
- A generalization of the second incompleteness theorem and some exceptions to it (Q2500470) (← links)
- Models of replacement schemes (Q2573725) (← links)
- Typical forcings, NP search problems and an extension of a theorem of Riis (Q2659102) (← links)
- Tautologies from Pseudo-Random Generators (Q2736584) (← links)
- FRAGMENTS OF APPROXIMATE COUNTING (Q2921008) (← links)
- END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS (Q2976370) (← links)
- Unprovability of circuit upper bounds in Cook's theory PV (Q2980966) (← links)
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD <font>NP</font> ∩ <font>coNP</font> FUNCTION (Q3094358) (← links)
- (Q3140642) (← links)
- Approximate counting by hashing in bounded arithmetic (Q3399180) (← links)
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic (Q3540180) (← links)
- POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC (Q3583040) (← links)
- Examining Fragments of the Quantified Propositional Calculus (Q3617380) (← links)
- On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
- Provably total functions of intuitionistic bounded arithmetic (Q4032632) (← links)
- Witnessing functions in bounded arithmetic and search problems (Q4227882) (← links)
- INCOMPLETENESS IN THE FINITE DOMAIN (Q4640304) (← links)
- 1998–99 Annual Meeting of the Association for Symbolic Logic (Q4940738) (← links)
- On the finite axiomatizability of (Q5109206) (← links)
- (Q5119389) (← links)
- Approximate counting in bounded arithmetic (Q5422312) (← links)
- Consequences of the provability of <i>NP</i> ⊆ <i>P</i>/<i>poly</i> (Q5444705) (← links)
- Fragments of bounded arithmetic and the lengths of proofs (Q5502825) (← links)
- Notes on polynomially bounded arithmetic (Q5687325) (← links)
- A model of \(\widehat{R}^2_3\) inside a subexponential time resource (Q5937822) (← links)
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS (Q6204144) (← links)
