×

Randomness, stochasticity, and approximations. (English) Zbl 0956.68064

Summary: Polynomial time unsafe approximations for intractable sets were introduced by A. R. Meyer and M. S. Paterson [With what frequency are apparently intractable problems difficult? Technical Report TM-126, Laboratory for Computer Science. MIT (1979)] and Y. Yesha [SIAM J. Comput. 12, 411-425 (1983; Zbl 0545.03023)], respectively. The question of which sets have optimal unsafe approximations has been investigated extensively. Recently, Y. Wang [SIAM J. Comput. 28, No. 2, 394-408 (1998; Zbl 0915.68046) and Randomness and complexity (1996; Zbl 0858.03041)] showed that polynomial time random sets are neither optimally unsafe approximable nor \(\Delta\)-levelable. In this paper we show that: (1) There exists a polynomial time stochastic set in the exponential time complexity class which has an optimal unsafe approximation. (2) There exists a polynomial time stochastic set in the exponential time complexity class which is \(\Delta\)-levelable. The above two results answer a question asked by K. Ambos-Spies and J. Lutz [The Workshop on Randomness and Information, Dagstuhl, July 15-19 (1996)]: What kind of natural complexity property can be characterized by \(p\)-randomness but not by \(p\)-stochasticity? Our above results also extend Ville’s [J. Ville, Etude critique de la notion de collectif (1939; Zbl 0021.14601)] historical result. The proof of our first result shows that, for Ville’s stochastic sequence, we can find an optimal prediction function \(f\) such that we will never lose our own money betting according to \(f\) (except the money we have earned), that is to say, if at the beginning we have only $1 and we always bet $1 that the next selected bit is 1, then we always have enough money to bet on the next bit. Our second result shows that there is a stochastic sequence for which there is a betting strategy \(f\) such that we will never lose our own money betting according to \(f\) (except the money we have earned), but there is no such optimal betting strategy. That is to say, for any such betting strategy, we can find another betting strategy which could be used to make money more quickly.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI