Y

Written 07/04/24

Published 07/04/24

Y

A Finite Epistemological Analysis of the P vs. NP Hypothesis
and Assertion of the Negative: P ≠ NP

Justin Bailey

ABSTRACT

P vs. NP is a concept that most knowledgeable people would likely agree should have been solved already. This proof assumes the positive (P = NP) and constructs a recursive argument to demonstrate a contradiction in the nature of the given assumptions.

The latter half of the essay corresponds and compares the structure of this line of argumentation to that of Alan Turing and Bertrand Russell, in an effort to show that this problem has, in fact, been solved philosophically, if only in other words/contexts.

TABLE OF CONTENTS

-Proof Y
-The Necessity of Space and Time
-Modern Perspectives on Analogous Philosophical Paradoxes
-Conclusion

Proof Y

Assume assertion A: P = NP according to proof X. The following proof Y asserts the contrary B: P ≠ NP.

To verify X, one must perform task M0: translate the set of all NP problems into P problems as A asserts is possible.

M0 is decidedly outside of P, as this translation requires a surjective process onto P, as well as the verification that this surjection holds.

The surjective process involves a mapping of each NP problem to any given P problem (including itself and other NP problems under A). All P problems by definition may be translated to any other P problem, and A asserts this should hold for NP problems.

To verify that the surjection holds under X, one must perform task M1: translate the set of all NP->P translation problems into P problems as A asserts is possible.

M1 is decidedly outside of P as this translation requires a surjective process onto P, as well as the verification that this surjection holds.

Mn are decidedly outside of P, as each instance of translation of a set of novel NP problems into P requires a surjective process onto P, as well as the verification that every surjection holds.

Each instance of Mn requires a constructed model of Mn-1 so as to complete the Mn task of translating the set of Mn-1 tasks into P tasks.

Therefore:

If Mn were inside of P, the process of translating all given NP problems into P problems would be a trivial P problem. If Mn were outside of P, this would be a trivial axiomatic distinction. The knowledge of whether A holds is distinctly given by some manifestation of X.

X does not exist, therefore A is an NP language. In some constructible theoretical Universe where X does exist, A is a P language; whether this theoretical Universe has any real and accessible bearing on the known Universe constrained by the axioms of math and computation is an open problem that is likely unfalsifiable. One might hold this notion of meta-undecidability as a perspective C, if you will, in relation to A and B.

This meta distinction feels truly and egregiously trivial, but the matter of categorizing objects is a long-standing philosophical problem that generally results in the same conclusion: it’s subjective, or it’s a paradox.

To confidently assert that P = NP is to manifest a translation/mapping problem of one’s own creation (via X/Mn) that is unmanageable and impossible to actually translate and compute, therefore creating the very problem the assertion A intended to dispel, that of efficient computability of all verifiable solutions to all constructible languages.

Thus, the most reasonable conclusion to hold without further empirical evidence, out of the two given perspectives A and B, is decidedly that of assertion B:

P ≠ NP.

The Necessity of Space and Time

Complexity classes are constrained by resources labelled as “space” and “time” (# of parallel processes/# of computations), and the question refers to whether one complexity class labelled “P” is equivalent to another labelled “NP”, thus equating the constraints which bound these categories.

Suppose an alternative set of constraints regarding computability/complexity independent of space and time. In this hypothetical Universe, P is trivially equivalent to (or independent from) NP as all established equivalence classes under standard constraints are essentially flattened to a dimensionless stabilizer (a point) under the new constraints, with no distinguishing characteristic between any particular distinct sets of computations (except perhaps cardinality of idealized computations, another undecidable problem via CH).

A set of constraints must be represented with bits. A set of bits is a language which requires space and time. This hypothetical alternative Universe where P = NP is inherently paradoxical as this Universe requires constraints to be considered a proper Universe, yet it requires the absence of constraints so as to avoid engaging with resources such as “time” and “space”.

Suppose a set of constraints, but don’t actually suppose them or your model will collapse, due to Incompleteness (woke).

This is certainly not to argue that complex problems cannot be simplified. However, one must solve and verify the problem of solving all problems, in order to generalize the global notion of “simplifying complex problems”. Simplifying and translating complex problems is necessarily a localized task that requires goal-oriented decisions (i.e. a space of potential states as opposed to a dimensionless point) and time.

Modern Perspectives on Analogous Philosophical Paradoxes

Consider the halting problem posed by Alan Turing. The halting problem concerns categorizing algorithms into those that will halt and return some output in a finite amount of time, vs. those that fail to do so and instead continue to loop indefinitely without bound. This is strikingly analogous to the categorization of P vs. NP respectively, and with some context and rephrasing one may draw analogies from both concepts to Russell’s paradox (as has been previously done by others), that of categorizing sets into normal vs. abnormal, N vs. A.

It follows from the conclusions of both Turing’s halting problem and Russell’s paradox that P vs. NP is yet another philosophical categorization hypothetical for which the answer is essentially: it’s fine if you stop thinking about it.

Consider the set of all algorithms that halt. This includes normal algorithms which arrive at a conclusion in finite time, as well as any algorithm which is axiomatically bound by some constraint to recognize situations where the program is looping, and simply halt without returning any output directly relevant to the solution.

This effect is common for coding IDEs, softwares that recognize errors/bugs and report information about the error, rather than trying (and failing) to return a proper answer. These algorithms are in the set of algorithms that halt, regardless of their output.

The algorithms that are necessarily constrained to halt, will halt. This seems trivial but one requires defined constraints on the nature of the algorithm in order to construct this category.

Consider the algorithms that do not halt. There are many. Consider the process (algorithm) used to construct the Mn argument previously in this proof.

There are many algorithms that demonstrably halt. There are many algorithms that demonstrably do not halt. The trivial conclusion is that there is no global solution, as follows from Turing.

Consider the set of all sets that do not contain themselves. [1,2,3] is such a set, denoted as a “normal” set belonging to category N.

Now consider the set of all sets that contain themselves. These are “abnormal” sets belonging to category A.

Obviously and trivially, a set that refers to itself must either bound its self-reference via some external constraint (i.e. IDE, observer), or be destined to reference itself indefinitely, as there is no given constraint to its referential “inertia”.

Considering the category N is trivial and reasonable to understand. Considering category A is a natural Pandora’s box waiting to be released. The conclusion is that there is no global solution to Russell’s paradox, and one must enforce proper constraints when dealing with self referential concepts.

It naturally follows from the greatest minds in modern philosophy and computation that NP is a unique class of problems that exists outside the domain of problems solvable in polynomial time.

Conclusion

If X exists, X asserts A and A asserts P = NP. X does not exist.
If Y exists, Y asserts B and B asserts P ≠ NP. Y exists.

If some Z exists and asserts C, C asserts ~A and ~B. Z does not exist.

----------------------------------------------------------

Y

WORKS CITED

“Diagonal Lemma.” Wikipedia, Wikimedia Foundation, 29 Apr. 2024, en.wikipedia.org/wiki/Diagonal_lemma.

“Lawvere’s Fixed-Point Theorem.” Wikipedia, Wikimedia Foundation, 14 Feb. 2024, en.wikipedia.org/wiki/Lawvere%27s_xed-point_theorem.