Randomness, pseudorandomness and models of arithmetic

zbMATH Open1432.03067arXiv1210.4692MaRDI QIDQ5222083FDOQ5222083

Pavel Pudlák

Publication date: 30 March 2020

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.

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)

Cited In (5)

• Title not available (Why is that?)
• Randomization and eventual reordering: a number theoretic approach
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• A remark on pseudo proof systems and hard instances of the satisfiability problem
• Randomized proofs in arithmetic

Recommendations

• Randomness and Computation 👍 👎
• RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS 👍 👎
• Randomness, Computation and Mathematics 👍 👎
• Randomness below complete theories of arithmetic 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)