scientific article; zbMATH DE number 1114029
The author considers a number of axiomatic systems of arithmetic and their bearings on the \(\text{P}=(?)\) NP problem. The first system considered is \(\text{ISREF}(A)\), introspective semantics with reflection of the given system \(A\). The new system is formulated in terms of non-growth functions, like subtraction and root (in contrast to addition and multiplication). And its axioms give the apparatus for arithmetization and include two types of reflections. One of them states: if \(x>\text{Size}(y)\), where \(y\) is a proof of \(\Phi\), then \(\Phi^{x-1}\). Here, \(\Phi^{x- 1}\) is obtained from \(\Phi\) by adding the bound \(x-1\) to unbounded quantifiers. (Since only non-growth functions are used, giving bounds to quantifiers is very sensible.) It is shown that the operation: \(A\mapsto\text{ISREF}(A)\) preserves consistency, and yet the system becomes inconsistent upon changing the bound to \(x\) from \(x-1\). Another system discussed is \(\text{ISREF}^R(A)\) whose reflection depends on a given function \(R(\;)\) [and is too complicated to quote]. This operation is related to \(\text{P}=\text{NP}\) in two ways. If it is consistency preserving with \(R(y)\gg\text{PolyLog}(y)\), then \(\text{P}\neq \text{NP}\); and if \(\text{ISREF}^R(\text{PAX})\) is consistent, then PA can not decide \(\text{P}=\text{NP}\) in the form of satisfiability. Here, PA is Peano arithmetic and PAX is \(\text{PA }+\) (a little more). The author introduces and discusses a few more systems of a similar nature. For the entire collection see [Zbl 0881.00033].
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375800)
