TY - JOUR

T1 - Prediction-preserving reducibility

AU - Pitt, Leonard

AU - Warmuth, Manfred K.

N1 - Funding Information:
*Supported in part by NSF Grant IRI-8809570 and by the Department of Computer Science, University of Illinois at Urbana-Champaign. t Supported in part by ONR Grant NOOO14-86-K-0454. Part of this work was done while visiting the Aiken Computation Laboratory, Harvard University, Cambridge, MA 02138, with partial support from ONR Grant NOOO14-85-K-0554.

PY - 1990/12

Y1 - 1990/12

N2 - We investigate a model of polynomial-time concept prediction which is a relaxation of the distribution-independent model of concept learning due to Valiant. Prediction-preserving reductions are defined and are shown to be effective tools for comparing the relative difficulty of solving various prediction problems. A number of prediction-preserving reductions are given. For example, if deterministic finite automata are polynomially predictable, then so are all Boolean formulas. We develop a complexity theory for prediction problems that parallels standard complexity theory. It is shown that certain problems of concept prediction are "prediction-complete" for a complexity class-a polynomial time algorithm for the prediction problem would imply that all languages in the complexity class are polynomially predictable. For example, polynomial-time prediction of deterministic finite automata implies the polynomial predictability of all languages in the class LOG (deterministic logspace). Similar natural prediction-complete problems are given for the standard complexity classes NC1, NLOG, LOGCFL, and P. Showing that a prediction problem is prediction-complete for any of these classes provides varying degrees of evidence that no efficient prediction algorithm exists for the problem. Based on very weak cryptographic assumptions, we establish hardness results for prediction of Boolean circuits and other prediction problems that are prediction-complete for P. The recent related resuts of Kearns and Valiant are discussed, which show that Boolean formulas and DFAs are not polynomially predictable based on the assumed intractability of computing specific cryptographic functions.

AB - We investigate a model of polynomial-time concept prediction which is a relaxation of the distribution-independent model of concept learning due to Valiant. Prediction-preserving reductions are defined and are shown to be effective tools for comparing the relative difficulty of solving various prediction problems. A number of prediction-preserving reductions are given. For example, if deterministic finite automata are polynomially predictable, then so are all Boolean formulas. We develop a complexity theory for prediction problems that parallels standard complexity theory. It is shown that certain problems of concept prediction are "prediction-complete" for a complexity class-a polynomial time algorithm for the prediction problem would imply that all languages in the complexity class are polynomially predictable. For example, polynomial-time prediction of deterministic finite automata implies the polynomial predictability of all languages in the class LOG (deterministic logspace). Similar natural prediction-complete problems are given for the standard complexity classes NC1, NLOG, LOGCFL, and P. Showing that a prediction problem is prediction-complete for any of these classes provides varying degrees of evidence that no efficient prediction algorithm exists for the problem. Based on very weak cryptographic assumptions, we establish hardness results for prediction of Boolean circuits and other prediction problems that are prediction-complete for P. The recent related resuts of Kearns and Valiant are discussed, which show that Boolean formulas and DFAs are not polynomially predictable based on the assumed intractability of computing specific cryptographic functions.

UR - http://www.scopus.com/inward/record.url?scp=0025623922&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025623922&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(90)90028-J

DO - 10.1016/0022-0000(90)90028-J

M3 - Article

AN - SCOPUS:0025623922

SN - 0022-0000

VL - 41

SP - 430

EP - 467

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -