Randomness, pseudorandomness and models of arithmetic

zbMATH Open1432.03067arXiv1210.4692MaRDI QIDQ5222083FDOQ5222083

Authors: 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

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

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

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)