论文标题
数字扩展
Numbers Extensions
论文作者
论文摘要
在过去的50年中，在计算性领域的许多问题令人惊讶地没有得到答复。一个示例是$ p $ vs $ np \ cap co-np $的问题。它可以用宽松的术语来表达，例如“如果一个人有能力验证证明和解决问题的证明，那么这个人知道解决该问题的解决方案吗？”。 当谈论人时，当然可以看到问题取决于特定人对此问题的知识。我们的主要目标是将该观察结果扩展到设置理论$ ZFC $的正式模型：鉴于型号$ m $和特定问题$ l $ in $ np \ cap co-np $，我们可以证明，如果我们拥有$ l $的“知识”，则问题$ l $在$ p $中。 在本文中，我们将定义知识的概念，并阐述为什么它与知识的直观概念一致。接下来，我们将构建一个模型，其中我们对许多功能具有知识。从该模型的存在来看，我们将在任何具有世俗的红衣主教的模型中推断出我们对广泛功能的知识。 结果，我们表明，如果我们假设存在世俗的红衣主教，那么“在$ np \ cap co-np $中也以$ p $为$ np \ cap co-np $的特定可定义语言也是可证明的。假设我们是世俗的基础主教，我们通过简单地使用这些定理可以显示一个可以在多同源时间中的因素数字。 本文不会解决$ p $ vs $ np \ cap co-np $问题，但其主要结果使我们更近一步地决定了这个问题。
Over the course of the last 50 years, many questions in the field of computability were left surprisingly unanswered. One example is the question of $P$ vs $NP\cap co-NP$. It could be phrased in loose terms as "If a person has the ability to verify a proof and a disproof to a problem, does this person know a solution to that problem?". When talking about people, one can of course see that the question depends on the knowledge the specific person has on this problem. Our main goal will be to extend this observation to formal models of set theory $ZFC$: given a model $M$ and a specific problem $L$ in $NP\cap co-NP$, we can show that the problem $L$ is in $P$ if we have "knowledge" of $L$. In this paper, we'll define the concept of knowledge and elaborate why it agrees with the intuitive concept of knowledge. Next we will construct a model in which we have knowledge on many functions. From the existence of that model, we will deduce that in any model with a worldly cardinal we have knowledge on a broad class of functions. As a result, we show that if we assume a worldly cardinal exists, then the statement "a given definable language which is provably in $NP\cap co-NP$ is also in $P$" is provable. Assuming a worldly cardinal, we show by a simple use of these theorems that one can factor numbers in poly-logarithmic time. This article won't solve the $P$ vs $NP\cap co-NP$ question, but its main result brings us one step closer to deciding that question.
