構文的に同等の意味クラスは何ですか?

この質問は、構文クラスと意味クラスの利点に関連しています。
前述のように、$ mathsf {PSPACE} = mathsf {IP} $は、意味クラス$ mathsf {IP}
$として解釈でき、構文定義を取得します。 クラスを “統語的にする”ための他の非自明な例は何ですか?

ベストアンサー

FWIWでは、[1]で定義された表面的に意味論的なクラスAPPが[2]において構文的であることが示された。

[1] Valentine Kabanets、Charles Rackoff、Stephen A. Cook、効率的
  近似実数値関数
、ECCCレポート TR00-034 、2000。

[2] Emil Jeřábek, Approximate counting in bounded
arithmetic
, Journal of Symbolic Logic 72 (2007), no. 3, pp.
959–993. doi, preprint

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です