What is polynomial-time random language? I have tried to found the definition by searching artilce, but failed. Any one give reference?

  • $\begingroup$ A random language, conditioned on it being in P? Which article are you referring to? $\endgroup$
    – Clement C.
    Aug 22, 2017 at 19:43
  • $\begingroup$ @ClementC. I am not sure, I have not found any definition of it, it is relating to some theorems. It is relating to my question posted several year ago,.mathoverflow.net/questions/157880/… $\endgroup$ Aug 22, 2017 at 19:45
  • $\begingroup$ "Which article are you referring to?" Which "theorems," from where? $\endgroup$
    – Clement C.
    Aug 22, 2017 at 19:46
  • $\begingroup$ and I am embarrassed to ask the solver again about the question $\endgroup$ Aug 22, 2017 at 19:48
  • $\begingroup$ @ClementC. I have made a mistake. sorry, corrected. $\endgroup$ Aug 22, 2017 at 19:51

1 Answer 1


Here is a lecture notes to explain p-time random, in one word, an infinite sequence $Z\in \{0,1\}^N$is resource-bounded/computable random if there is no computable/resource-bounded martingale that succeeds on $Z$.

So p-time randomness is an infinite sequence $Z\in \{0,1\}^N$ is p-time random if there is no p-time computable martingale that succeeds on $Z$.

I think I can say settled now.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .