A Variation on the Zero-One Law
- Andreas Blass ,
- Yuri Gurevich ,
- Vladik Kreinovich ,
- Luc Longpré
Information Processing Letters |
Given a decision problem P and a probability distribution over binary strings, do this: for each n, draw independently an instance x(n) of P of length n. What is the probability that there is a polynomial time algorithm that solves all instances x(n)? The answer is: zero or one.