archives

Feasible Reductions to Kolmogorov--Loveland Stochastic Sequences


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Lutz, Jack H. (1996) Feasible Reductions to Kolmogorov--Loveland Stochastic Sequences. Technical Report TR96-10, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Feasible Reductions to Kolmogorov--Loveland Stochastic Sequences
Jack H. Lutz                       David L. Schweizer
Department of Computer Science          Department of Mathematics
Iowa State University                College of the Holy Cross
Ames, Iowa  50014                   Worcester, MA   01610
For every binary sequence A, there is an infinite binary sequence S
such that A is polynomial-time tt-reducible to S and S is stochastic
in the sense of Kolmogorov and Loveland.

Subjects:All uncategorized technical reports
ID code:00000130
Deposited by:Staff Account on 30 September 1996



Contact site administrator at: ssg@cs.iastate.edu