David O. Zisselman

Over the course of 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 can't be answered -- it 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 $ZF$: by adding "knowledge" to a model of a specific problem $L$ in $NP\cap co-NP$, we can create a model of $ZF$ in which the problem $L$ is in $P$ in that model. In this paper, we'll define the exact terms and show: - a mechanism, that is similar -- but somewhat different -- to forcing, which adds a set to an existing $ZF$ model. - how to use this mechanism to add "knowledge" to a $ZF$ model. - how such a "knowledge enriched" model can solve a problem and make it polynomial time decidable. As a result -- we show that under some mild consistency assumptions and one unnatural assumption, the statement that a given definable language in $NP\cap co-NP$ is also in $P$, is consistent with $ZF$ axioms. 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. Moreover, the main result will depend on an "unnatural" peculation assumption (given in the paper) which hopefully will be resolved in further works.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment