Polynomial time ultrapowers and the consistency of circuit lower bounds

DOI10.1007/S00153-019-00681-YMaRDI QIDQ2288334zbMATH OpenOpenAlexWikidataFDO

Authors J. Bydžovský, Moritz Müller

Publication date 17 January 2020

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/177012

zbMATH Keywords

bounded arithmeticcircuit lower boundsrestricted ultrapowers

Mathematics Subject Classification ID

Ultraproducts and related constructions (03C20) Models of arithmetic and set theory (03C62) Applications of model theory (03C98) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 806749
• Unprovability of circuit upper bounds in Cook's theory PV
• Limit, logic, and computation
• Circuit lower bounds in bounded arithmetics
• Feasibly constructive proofs of succinct weak circuit lower bounds

Cites work

• A remark on pseudo proof systems and hard instances of the satisfiability problem
• Approximate counting in bounded arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Consequences of the provability of NP ⊆ P/poly
• Construction of models of bounded arithmetic by restricted reduced powers
• Every two elementarily equivalent models have isomorphic ultrapowers
• Hilbert's Tenth Problem is Unsolvable
• scientific article; zbMATH DE number 5845490 (Why is no real title available?)
• scientific article; zbMATH DE number 3115891 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 1070621 (Why is no real title available?)
• scientific article; zbMATH DE number 1136103 (Why is no real title available?)
• scientific article; zbMATH DE number 806753 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 3204609 (Why is no real title available?)
• scientific article; zbMATH DE number 3204611 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Limit Ultrapowers
• Logical foundations of mathematics and computational complexity. A gentle introduction
• Models of arithmetic and recursive functions
• Natural proofs
• Non-standard models of Peano arithmetic
• Notes on polynomially bounded arithmetic
• On uniformity and circuit lower bounds
• Randomness, pseudorandomness and models of arithmetic
• Reduced direct products
• Saturated models of universal theories
• Sub-arithmetical ultrapowers: A survey
• The ultraproduct construction
• Ultraproducts in the theory of models
• Unprovability of circuit upper bounds in Cook's theory PV
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen

Cited in

(11)

• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• Unprovability of circuit upper bounds in Cook's theory PV
• On the power of deterministic reductions to C=P
• scientific article; zbMATH DE number 1222575 (Why is no real title available?)
• On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 806749 (Why is no real title available?)
• Unprovability of strong complexity lower bounds in bounded arithmetic
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• On the consistency of circuit lower bounds for non-deterministic time
• On the unprovability of circuit size bounds in intuitionistic \(\mathsf{S}^1_2\)

This page was built for publication: Polynomial time ultrapowers and the consistency of circuit lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288334)