MATHEMATICAL LOGIC AND ITS APPLICATION TO COMPUTATIONAL COMPLEXITY

设$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。

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$.