Construction of models of bounded arithmetic by restricted reduced powers
The paper is devoted to models of bounded arithmetic. The general aim is to construct extensions of models that preserve the set of lengths (and, consequently, polynomial-time computable properties) and satisfy some amount of bounded induction, yet are not elementary, so that they can be utilized, e.g., to prove independence results. Specifically, the author studies variants of \textit{restricted reduced powers}. He presents two constructions of such powers. Construction A is simple, but appears to be of limited applicability; nevertheless, the author shows how it can be used to reprove a form of Buss's witnessing theorem. Construction B is technically more complicated (both in the statement and in the proof), but it is more flexible than Construction A. The paper includes an interesting application of Contruction B to the open problem of separating the theory \(R^1_2\) from its strict variant: it is shown in the relativized setting that \(\mathrm{strict }R^1_2(\alpha)\neq R^1_2(\alpha)\), assuming that the existence of one-way permutations is hard for polynomial-size circuits (on any non-negligible subset of the domain). In fact, the author proves that under this assumption \(\mathrm{strict }R^1_2(\alpha)\) does not prove the bounded choice/collection/replacement schema \(\mathrm{BB }\Sigma^b_1(\alpha)\), which is well known to be provable in \(R^1_2(\alpha)\). Furthemore, if one can find such a one-way permutation definable by a term in the language of \(R^1_2\), we obtain even the unrelativized separation \(\mathrm{strict }R^1_2\neq R^1_2\).
- scientific article; zbMATH DE number 2208069
- scientific article; zbMATH DE number 999649
- Model theory of bounded arithmetic with applications to independence results
- On embedding models of arithmetic of cardinality \aleph1into reduced powers
- Theories of arithmetics in finite models
- Automorphisms of models of bounded arithmetic
- scientific article; zbMATH DE number 4101163
- scientific article; zbMATH DE number 1048040
- Structures interpretable in models of bounded arithmetic
- Models of arithmetic and upper bounds for arithmetic sets
- A new proof of Ajtai's completeness theorem for nonstandard finite structures
- Arithmetizing uniform NC
- Bounded arithmetic for NC, ALogTIME, L and NL
- Generalizations of the Compactness Theorem and Gödel’s Completeness Theorem for Nonstandard Finite Structures
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 1420845 (Why is no real title available?)
- scientific article; zbMATH DE number 227056 (Why is no real title available?)
- Non-standard models of Peano arithmetic
- Nondeterministic polynomial-time computations and models of arithmetic
- The strength of replacement in weak arithmetic
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- A Remark on Independence Results for Sharply Bounded Arithmetic
- On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- scientific article; zbMATH DE number 2208069 (Why is no real title available?)
- Preservation theorems and restricted consistency statements in bounded arithmetic
This page was built for publication: Construction of models of bounded arithmetic by restricted reduced powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q506954)
