MATHEMATICAL LOGIC AND ITS APPLICATION TO COMPUTATIONAL COMPLEXITY

数学逻辑及其在计算复杂性中的应用

• 批准号: 12640115
• 负责人: YASUMOTO Masahiro
• 金额: $ 2.11万
• 依托单位: UNIVERSITY OF NAGOYA
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12640115/
• 关键词: bounded arithmetic; computational complexity; nonstandard models; ブール値モデル; 多項式時間計算量

Let $N$ be a nonstandard model of $S_2$. A subset $\a$ of $N$ is called an oracle if $ (N,\a) $ satisfies $S_2 (\a) $. In this reseach we are concerned with bounded oracles $\a$ of $N$ satisfying $P^\a=NP^\a$. We proved that the existence of such oracles implies many interesting results about separations of axioms in bounded arithmetic.Let $n\in N$ and $M=PTC (n, \a) $ I.e.$M$ be the polynomial time closure of $\ {n\} $ with the oracle $\a$. Then it is known that $M$ is a model of $T_2^0$. Assume that there exists a bounded oracle $\a$ such that $N$ satisfies $P^\a=NP^\a$. Then $M$ satisfies Axioms $S_2$ and we proved that $M$ has no endextension satisfying $R_2^1$. This implies that $U_2^1$ is not a conservative extension of $S_2 (\a) $. In paticular, if there exists a model $N$ of $S_2$ such that $P=NP$ holds in $N$, then there is a first order sentence which is provable in $U^1_2$ but not in $S_2$. It is believed that $P\not=NP$ but there may exist a nonstandard model $N$ of $S_2$ satisfying $P=NP$.

设$N$是$S_2$的非标准模型。如果$（N，\a）$满足$S_2（\a）$，则$N$的子集$\a$称为oracle。在这个研究中，我们关注的是满足$P^\a=NP^\a$的有界预言机$\a$。我们证明了这类预言的存在性蕴含了关于有界算术中公理分离的许多有趣结果，设$n\in N$和$M=PTC（n，\a）$ I.e.$ M$是$\ {n\} $的多项式时间闭包，其中oracle $\a$。那么就知道$M$是$T_2^0$的模型。假设存在有界预言机$\a$使得$N$满足$P^\a=NP^\a$。则$M$满足公理S_2 $，我们证明了$M$没有满足R_2^1 $的扩张。这意味着$U_2^1$不是$S_2（\a）$的保守扩张。特别地，如果存在一个$S_2$的模型$N$使得$P=NP$在$N$中成立，则存在一个一阶句子在$U^1_2$中可证，但在$S_2$中不可证。我们认为P不=NP，但可能存在一个满足P=NP的S_2的非标准模型N。

项目成果

S.Aida, R.Schuler, T.Tsukiji and O.Watanabe: "The difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributational Problems"Theory of Computing Systems 35. 449-463 (2002)

S.Aida、R.Schuler、T.Tsukiji 和 O.Watanabe：“分布式问题上多项式时间多一与真值表约简性之间的差异”计算系统理论 35. 449-463 (2002)

T.Tsukiji: "On the difference between polynomial-time many-one and truth-table reducibility on distributional problems"Electronic Collq. on Computational Complexity. 81. 1-14 (2000)

T.Tsukiji：“关于分布问题上多项式时间多一与真值表可约性之间的差异”Electronic Collq。

Y.Matsubara: "Stationary preserving ideals over Lκλ"to appear in J.of Mathematical Sosiety of Japan.

Y. Matsubara：“Stationary Keeping Ideals over Lκλ”发表在 J.of Mathematics Society of Japan 上。

T. Tsukiji: "A limit law for outputs in random recursive circuits"Algorithmica. 31. 403-412 (2001)

T. Tsukiji：“随机递归电路中输出的极限法则”算法。

Y.Matsubara: "Stationary preserving ideal over Lκλ"Journal of the Mathematical Society of Japan. (to appear).

Y. Matsubara：“Lκλ 上的稳态保持理想”，日本数学会杂志（待发表）。