下記 田中 尚夫 数学基礎論的手法の計算量理論への応用 が 見つかったので ご紹介
”またgeneric setとP=NP問題との,§5とは異なる関連が最近竹内・安本によつて
得られた[TY 96].これは有界第2階算術のgenericモデルとの関連である.第2階構造は“記
述的計算量”の立場で,クラスNPを特徴づけることができる[Fa 74].”とあるね

やっぱ、第2階は えらい！　（＾＾
なお、”§1. 数学基礎論と数学の他分野との関連”も 面白かったな

(参考)
https://www.jstage.jst.go.jp/article/sugaku1947/48/4/48_4_372/_article/-char/en
J-STAGE home/SUGAKU/Volume 48 (1996) Issue 4/
https://www.jstage.jst.go.jp/article/sugaku1947/48/4/48_4_372/_pdf/-char/ja
数学基礎論的手法の計算量理論への応用
(付:数 学他分野との関連)
田中 尚夫 （数学 Volume 48 (1996) Issue 4）
(1996年4月25日提出) (たなか ひさお ・法政大学工学部)
序論
これらの他に,数学基礎論の研究中に開発された様々な概念・手法の他分野への応用とい
う重要な一一面がある.例えば, Shelahに始まる無限アーベル群論への応用,正規ムーア空間の距
離化問題のような集合論的位相空間論への応用, Nonstandard Analysis, etcがあり,
またRiemann.予想への数学基礎論的アプローチさえある.
中でも理論計算機科学,特に計算量理論,との関連は際立っていると言える.
計算機科学の理論的基礎はTuring machineにある.
従つて,理論計算機科学はrecursion theoryの上に成り立つていると言っても過言ではないと思う.本論説
はこのような数学基礎論と計算機科学,特に計算量理論,との関連に着目し,概念や手法がどのよ
うに使用されているかを紹介するのが主要目的である.しかし,読者の中には上に述べたような数
学基礎論と他の数学分野との関連により一層の興味をもつ人がかなりあるのではないかと考え,主
題とはやや離れるがこの話題に最初の一節を割くことにする。

§1. 数学基礎論と数学の他分野との関連.

§6.その他の関連.
またgeneric setとP=NP問題との,§5とは異なる関連が最近竹内・安本によつて
得られた[TY 96].これは有界第2階算術のgenericモデルとの関連である.第2階構造は“記
述的計算量”の立場で,クラスNPを特徴づけることができる[Fa 74].