神論文のNP ≠ EXPの証明より
> (4)の定義は “S(x, α) is Yes iff Q(1, α) is Yes based on an algorithm σ∈A(1, s, x).”
> (中略）
> 明らかに、(4)はEXPに属する。
それはその通りです。

> さらに、A(1, s)の定義により、(4)はNPには属さない。
こちらは証明が必要ですね。
(4)の実行に、σの実行が必須とは限りません。
もっと効率の良いアルゴリズムで、(4)の出力を得られるものがあるかもしれませんから。

それにしても、こんなのを証明なしに認めてよいのだったら、何でも証明できちゃいますよね。