Randomness, pseudorandomness and models of arithmetic

MaRDI QIDQ5222083zbMATH OpenFDO

Authors Pavel Pudlák

Publication date 30 March 2020

Full work available at URL https://arxiv.org/abs/1210.4692

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Models of arithmetic and set theory (03C62) Model theory (number-theoretic aspects) (11U09)

Abstract: Pseudorandmness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To this end we construct a set of models $calM$, a common element $iota$ of these models and a probability distribution on $calM$, such that for every pseudorandom sequence $s$, the probability that $s(iota)=1$ holds true in a random model from $calM$ is equal to 1/2.

Recommendations

• scientific article; zbMATH DE number 1195809
• Randomness below complete theories of arithmetic
• Randomness, computation and mathematics
• RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
• Randomness and arithmetic
• scientific article; zbMATH DE number 1487695
• scientific article; zbMATH DE number 1531917
• scientific article; zbMATH DE number 7377983
• Randomness and computation

Cited in

(5)

• A remark on pseudo proof systems and hard instances of the satisfiability problem
• scientific article; zbMATH DE number 1195809 (Why is no real title available?)
• Randomization and eventual reordering: a number theoretic approach
• Randomized proofs in arithmetic
• Polynomial time ultrapowers and the consistency of circuit lower bounds

This page was built for publication: Randomness, pseudorandomness and models of arithmetic

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