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.