A curious identity I rediscovered!

Sin(x)^2 + Cos(x)^2 = 1 for all rational numbers x. I discovered this while punching random characters on my calculator.

A natural generalization is to generalise this identity to the Gaussian Integers. It would be interesting to see whether there only finitely many solutions to the equation when constrained to the Gaussian Integers and i /= 0 or the Imaginary Numbers. It would also be interesting to consider whether there are infinitely many solutions if 1 was replaced with 0. Here sin(x) is expressed in radians.

A elementary proof of this identity for rational number cases can be found in the link below.

https://en.wikipedia.org/wiki/Pythagorean_trigonometric_identity

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 0n (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

A slide presentation to explain the basics of Complexity Theory.

The slide presentation I will link below is to explain P and NP to a general audience. It is written at a somewhat beginner level. If you need to understand more about this , feel free to comment.

Here are the slides for my talk on the topic.

Suggestions for further reading would by Fortnow, The Golden Ticket and the wikipedia articles on the respective topics.

Thank you,

Nunghead

Some other interesting series

The first such series we shall consider is the series generated by the formula 1/8(2x+1)^2 +7 This series generates a very similar series to the triangular number i.e the difference between consecutive terms is equal to 1m. Some terms are 1, 2 , 4 , 7, and so on… Indeed, if we subtract one we get the triangular numbers. Due to this coincidence, we can create another such formula for computing triangular numbers namely {1/8(2x+1)^2+7}-1.

Another such series is a series of numbers such that the difference of two consecutive odd number terms is equal to 2m. The formula for this is 1/4(2x+1)^2 +3. Some terms are 1, 3, 7, 13, 21, 31, and so on…

The last such series we will is a series of numbers such that the difference of any two consecutive number terms is equal to 7m. The formula for this is (2x+1)^2 +7)/8 + (2x+1)^2 +3)/4 + (2x+1)^2+1)/2.

Some terms of this are 3, 10, and 24.

All the formulas and series were discovered by me. Please attribute them to me if you are using these formulas.

Thank you,

Nunghead

An interesting series of numbers.

I discovered a interesting series of numbers, do tell me if you see the pattern in them.

1, 5, 13, 25,41,61,85, 113, …

The pattern is that the difference of any two terms is equal to a multiple of four.

Now, another challenge for you is to find the formula that generates the nth such number.

The formula is 1/2 {(2x+1)^2 + 1}

All these discoveries were made by me.

Thank you,

Nunghead

My proof of P vs NP variant two

DISCLAIMER:(Read This NOW Before you read my Proof!){I cannot emphasize this!}
Please do recognize that this is very tentative work. I would like you to read it with caution but not skepticism. This is also presented in an unadulterated fashion as this is my second draft and so constitutes my second variant If you do not have anything nice to say in the comments, don’t say it. Thank you for your time.

The existence of a unary decision problem that is NP Complete
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 0n (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 to avoid artificially converting the problem from an NP-Complete one to a polynomial one. Suppose to further elaborate , if we had used the Weakly-NP Complete decision problem SUBSET SUM instead of using any Strongly-NP Complete decision problems we would have unnaturally converted our problem from displaying exponential time complexity[5] for large input values leading to its binary encoded variant being probably not in P[6] but the unary encoded variant is in P.

Lemma 1.0:
BIN-PACKING is NP Complete

Proof of Lemma 1.0()[7]
We will not present the proof outlined in Garey and Johnson’s paper for the sake of brevity instead the interested reader can find a copy online.

Remark 1.1:
Bin Packing is strongly NP Complete a stronger fact than its mere NP-Completeness already proven in the paper by Garey and Johnson.

Theorem 1.0[8]
If there exists a unary encoded decision problem that is NP-Complete then P=NP

Proof of Theorem 1.0[9]
Again for the sake of brevity we will again not present the proof of this.

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

Remark 1.3
Recall that now we have shown that there exists a unary encoded decision problem that is NP Complete therefore, P=NP ,QED.
⬛

References:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T
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.
Relationship between density and deterministic complexity of NP-complete languages ,Piotr Berman
Garey, M. R.; Johnson, D. S. (July 1978). “‘Strong’ NP-Completeness Results: Motivation, Examples, and Implications

[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] The technical term for denoting that certain algorithms run in exponential time for large values is the term pseudo- polynomial time algorithm.
[6] Here assuming that P /= NP.
[7] Garey, M. R.; Johnson, D. S. (July 1978). “‘Strong’ NP-Completeness Results: Motivation, Examples, and Implications

[8] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, Journal of Computer and System Sciences 25:130-143, 1982.
[9] Relationship between density and deterministic complexity of NP-complete languages ,Piotr Berman

My proof for P vs NP Draft One, Variant One

DISCLAIMER:(Read This NOW Before you read my Proof!){I cannot emphasize this!}
Please do recognize that this is very tentative work. I would like you to read it with caution but not skepticism. This is also presented in an unadulterated fashion as this is my first draft and so constitutes my first variant If you do not have anything nice to say in the comments, don’t say it. Thank you for your time.

A solution for the P versus NP Problem
By: Nunghead

Abstract:

In this proof, I will outline a solution to the P versus NP Question. The main result of this proof is that Berman’s Theorem is proven in the positive implying P=NP as a corollary by the explicit construction of a unary language with the property that it is NP Complete

Axiom 1.0 (Garey and Johnson):
Any NP Complete problem’s corresponding binary language is also NP Complete.

Lemma 1.1 (Wikipedia):
Every binary language has a more compact unary version.

Proof of Lemma 1.1:
Since the universe of strings over any finite alphabet is a countable set, every language can be mapped to a unique set A of natural numbers; thus, every language has a unary version {1k | k in A}.

Theorem 1.0 (Berman)
If there exist a unary language that is NP Complete then P=NP

Remark 1.0:
We shall restrict ourselves to Strongly NP Complete languages as their complexity doesn’t vary with the changing encoding scheme i.e from binary to unary. Suppose, if we had used the Weakly-NP Complete language SUBSET SUM instead of using any Strongly-NP Complete language we would have unnaturally converted our problem from displaying exponential time in the worst case for large input values leading to its unary variant being in P but binary variant is not in P.

Proof of Theorem 1.0[1]
Final Proof:
Due to the fact that every Strongly NP Complete problem’s language is also Strongly NP Complete, we may pick any Strongly NP Complete language for the task ahead. We will pick Bin-Packing as the Strongly-NP Complete language to be specific. Now by applying Lemma 1.1 we know that Bin-Packing has a corresponding unary language .So now we can conclude there exists a corresponding unary language for Bin-Packing that is NP Complete, thereby proving P=NP via Berman’s Theorem i.e Theorem 1.0. Q.E.D

References:
Book, R.V., Wrathall, C., Selman, A.L. et al. Math. Systems Theory (1977) 11: 1. https://doi.org/10.1007/BF01768464
Relationship between density and deterministic complexity of NP-complete languages ,Piotr Berman
https://en.wikipedia.org/wiki/Unary_language,
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T
http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
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.

[1] The proof is presented in Berman’s paper Relationship between density and deterministic complexity of NP-complete languages , theorems 1 and 2.

Design a site like this with WordPress.com
Get started