NP とランダムの関係を知りたかったら、ランダムオラクル仮説と
PCP(probabilistically checkable proof) 関係を調べてみたら?