My proof for P=NP draft three

Please realize that this is a draft proof.

The existence of a unary decision problem that is NP Complete – A Proof Sketch

By: Nunghead

 

Abstract:

We will establish that there exists a decision problem encoded in unary^[1] that is NP-Complete as the main result of this paper.

 

Definition 1.0(Strongly-NP Complete)^[2]

A strongly NP-Complete problem is a problem that even when encoded in unary is still NP-Complete.

 

Definition 1.1 (Unary Decision Problems)^[3]

The class of decision problems for which every ‘yes’ instance has the form 0ⁿ (i.e. inputs are encoded in unary). 

Remark 1.0(On Strongly NP Completeness)^[4]

We shall restrict ourselves to Strongly NP Complete decision problems as their complexity doesn’t vary with the changing encoding scheme i.e. from binary to unary, and to avoid artificially converting the problem from an NP-Complete one to a polynomial one.

 

Lemma 1.0

BIN-PACKING ∈ NP

 

Lemma 1.1

BIN-PACKING is Strongly NP Complete. Refer to footnote^[5] for Proof.

 

Theorem 1.0^[6]

If there exists a unary encoded decision problem that is NP-Complete, then P=NP. Refer to footnote^[7] for Proof.

 

Remark 1.1

Any unary encoded NP-Complete decision problem will satisfy our requirements so long as it is Strongly NP Complete. 

 

Remark 1.3

We have shown that there exists a unary encoded decision problem that is NP Complete therefore, P=NP, QED. ⬛

 

 

^[1] https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T

^[2] Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; a Guide to the Theory of Np-Completeness. W. H. Freeman & Co., New York, NY, USA.

^[3]  https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T

^[4]  Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; a Guide to the Theory of Np-Completeness. W. H. Freeman & Co., New York, NY, USA.

^[5]  Garey, M. R.; Johnson, D. S. (July 1978). “‘Strong’ NP-Completeness Results: Motivation, Examples, and Implications

^[6] https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T

^[7] Relationship between density and deterministic complexity of NP-complete languages, Piotr Berman