Tuesday, February 15, 2011

P vs NP

P vs NP
Andtre Willers
15 Feb 2011

"If it were done when 'tis done , then 'twere well
It were done quickly ."
Shakespeare

Synopsis :
A Quick Proof that P = NP
An Algorithm can always be found that reduces the Aleph number by one , with an error factor .

Discussion :
This is just a blog , not a formal proof .

Pre-requisite axiom :
Axiom of Delineation .
Items can be defined , ie delineated .

Then statements about anything can be True (+1) or False(-1) (Aristotelianism , computer logic)

The Universe of True and False statements (U(A) can then be expressed in combinations as
U(A) = { (+1) + (-1) } ^ n
Where n can be large finite or any Kantorian Infinity .
(Amusing to note that this means the expansion of zero , Cf Quantum Foam)

Just counting the statements , where (+1) counts as one and (-1) also counts as one , gives the number of statements , gives the
Number of statements in U(A) = 2^n . This fits in with Kantorian Aleph classes .

Definition of Algorithm :
An Algorithm has a smaller Aleph number than that of n , by definition .
This can be expressed as
Algorithm = { (+1) + W * (-1) } ^ n …. Where 0 <= W < 1

Can an Algorithm always exist ?
Yes . We show it as follows :
We express U(A) in logical notation as :
U(A) = { (+1) + W*(-1) - (1-W) } ^ n … a congruent tautology .

Expansion
Using Binomial expansion to give all possible combinations gives
U(A) = { (+1) + W*(-1)} * F + (-1)^n * (1-W)^n
Where F is the other terms of the expansion

This means that
U(A) = Algorithm * F + (-1)^n * (1-W)^n

Interpretation :
A delineated universe can always be expressed in terms of an Algorithm of one less Aleph number , with an uncertainty of { +- (1-W)^n } .

Popular methods in this Universe is to set W=1/2 . Ie Quantum physics of spin .

Travelling Salesman problem :
See http://andreswhy.blogspot.com "Travelling salesman Problem and Quantum Gravity" Nov 2010 .
Here W=1/2 by using Arrival and Departure points in a city as quantum pairs that have to filled first after a finite sorting of n(n-1)/2 distances .
Sorting can be used as n (the number of cities) is finite .

For the same reason , the cumulative error can be made as small as we like , smaller than the smallest distance between cities . Hence , an exact solution is possible .

Applications :

1, I am releasing this since it has important applications in real-world problems like protein folding . Remember , old age sucks .

2. Some quick adjustments will have to be made to many cryptographic systems that depend on the difficulty of factoring large (but finite) numbers .

As for the Clay prizes , they would not even deign to consider this .

Oh , well .

There is always the Wright Prize .
Eppur it flies .

Andre

Xxxx

No comments: