VARIATION ON THE ZERO-ONE LAW

Authors
BLASS A GUREVICH Y KREINOVICH V LONGPRE L
Citation
A. Blass et al., VARIATION ON THE ZERO-ONE LAW, Information processing letters, 67(1), 1998, pp. 29-30
Citations number
1
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
67
Issue
1
Year of publication
1998
Pages
29 - 30
Database
ISI
SICI code
0020-0190(1998)67:1<29:>2.0.ZU;2-R
Abstract
Given a decision problem P and a probability distribution over binary strings, for each it, draw independently an instance x(n) of P of leng th n. What is the probability that there is a polynomial time algorith m that solves all instances x(n) of P? The answer is: zero or one. (C) 1998 Elsevier Science B.V. All rights reserved.