MATHEMATICAL LOGIC AND ITS APPLICATION TO COMPUTATIONAL COMPLEXITY

点击翻译按钮获取中文摘要

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