There is a typo in the text: “We say that S is an ??? with probability p.” I guess this is supposed to be “irreducible pattern”?
Btw, it seems that the definition makes sense for arbitrary promise problems, you don’t have to consider provability in particular.
There is a typo in the text: “We say that S is an ??? with probability p.” I guess this is supposed to be “irreducible pattern”?
Btw, it seems that the definition makes sense for arbitrary promise problems, you don’t have to consider provability in particular.