New Studies in Weak Arithmetics

0422148 - MÚ 2014 RIV US eng M - Část monografie knihy
Pudlák, Pavel
Randomness, pseudorandomness and models of arithmetic.
New Studies in Weak Arithmetics. 1. Stanford: Center for the Study of Language and Information, 2013 - (Cégielski, P.; Cornaros, C.; Dimitracopoulos, C.), s. 199-216. CSLI Lecture Notes, vol. 211. ISBN 978-1-57586-723-6
Grant CEP: GA AV ČR IAA100190902
Institucionální podpora: RVO:67985840
Klíčová slova: pseudorandomness * number theory
Kód oboru RIV: BA - Obecná matematika

Pseudorandomness 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 and we construct a set of models M, a common element i of these models and a probability distribution on M, such that for every pseudorandom sequence s, the probability that s(i)=1 holds true in a random model from M is equal to 1/2.
Trvalý link: http://hdl.handle.net/11104/0228428