
Re: P=NP Proof Published at CERN
Posted:
May 13, 2009 7:37 PM


Martin Musatov wrote: > On May 10, 3:10 pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote: > > Martin Michael Musatov wrote: > > > Listen to the nonsense you speak. Do you recognize the only > > > individuals able to respond carry the name Mariano and Victor with a > > > "666" in the email address for the U.K.? That is not a coicidence. > > > > Yes... most of the people in this newsgroup know better than to respond > > to yet another claim of proof of a major unsolved problem by someone > > with no credentials whatsoever. > > > > This is, what, the fourth one I've seen in the past year? > > > > JSH first attempted it by finding a polynomial algorithm to the > > Traveling Salesman Problem last August... granted it neither worked nor > > solved the problem, although that last part was eventually ironed out. > > That's actually three attempts, all of which have known counterexamples. > > > > Then there was the person who "solved" 3SAT... a counterexample took I > > think a week or so, but eventually it was found. > > > > Next was the proof that solved equations over GF2; in here, the > > NPcompleteness of the problem being solved was in question. > > > > And then here's yours... to quote someone else: > > > > > It is surprising that P=NP is still an open problem; after all, we get a > > > new proof every month! > > > >  > > Beware of bugs in the above code; I have only proved it correct, not > > tried it.  Donald E. Knuth > > May I ask since you seem to be more agreeable and professional than > the crudeness prior, what you make of this information? > > The below is an email I received: (please note I own > scriber77@yahoo.com and registered the group pequalsnp@yahoogroups.com > but decided deliberately to use marty.musatov@gmail.com for reasons of > proving P==NP. > >  In pequalsnp@yahoogroups.com, "scriber77" <marty.musatov@...> > wrote: > > > > This is the html version of the file http://www.npp.co.in/ClayProblem.pdf. > > Google automatically generates html versions of documents as we crawl the web. > > Page 1 > > 1A go at the Clay Millennium problem NP=PAbstractThe problem posed is whether > Non Computational time (Non deterministic PolynomialtimeNP) Algorithm > produce > Polynomial time (deterministic polynomial timeP)algorithm results, > that is > whether they are equal. That is NP=P. A six City traverse of theof a > traveling > Sales man is considered . There exists a starting city and an ending > city.The > problem is to converge into a minimal cost tour from the starting city > to > thedestination city without traversing a city twice. An algorithm is > developed > which employsBubble Sort(BS) as component which is proved NP complete. > The same > Algorithm whenQuick Sort(QS) is employed instead of BS turns out to be > P type. > They produce the sameminimal cost, proving NP=P. The Halting problem > remain > resolved.ContentsNon deterministic polynomial time NP algorithms can > be either > General casewhich are all algorithms that have algorithms but don't > halt in > legitimate time which willgo on beyond legitimate time to halt or has > to be > `Drop Dead Halted' and Special casewhere the symbol sequences are > gibberish in > nature and are made to halt with drop deadhalts.For the general case > an NCity > Travelling Sales Mans Problem (TSP) is chosen to provethe phenomenon > NP=P. We > are required to find out the minimal cost incurred by himwhen touring > all these > selected cities on a sales tour starting from a selected city to > adestination > city not stepping into one city twice in the tour. Here a 5city tour > isdemonstrated as a representative example of the Ncity tour with the > costs > marked in thegraph (Figure 1, pp2). It is bidirectional graph and the > costs are > identical for forward andbackward traverse. Representative costs based > on > distance between cities tend to produceconverging results for the > Algorithm in > the cities chosen. For the sake of this problem it issufficient to > take costs > same for both directions. Those who want to check out different > weights are > urged to do so but it is clear that it will produce appropriate result > without > change in the resulting proof. Table 1 gives the outgoing and incoming > costs for > different cities. The cities chosen are the Indian cities of Cochin (C > )Madras(M)Bangalore(B)Hydrabad(H)Pune(P). The Algorithm for > generating the > minimal cost tour is as follows.1. Arrange the costs from each city in > fields. > Sort it in the Ascending order.2. At starting city find the minimal > cost out of > all the costs from that city, to othercities. Mark the city header > with * and > write the minimal cost beside it. (Since thelist is sorted the minimal > costs > will remain at the beginning of the list) . Underlinealso, the > selected cost.3. > At the next city where the previous city lead to find the minimal cost > to the > next whichever city. If this city is already traversed and is the > destination > city choosethe next minimal cost. Add it to the previous cost. Place a > * at the > header andwrite the total cost till then against it. Underline the > selected > cost.4. Repeat 3 till the destination city is reached.5. The number > appearing > before the final city is the minimal cost required, (sincethis is a > forward > looking algorithm).6. You do this for all transitions from the > starting city and > the minimal is cost is theleast cost arrived.Table 1 on last page (pp > 11) gives > the rundown of this Algorithm. > > >  > > Page 2 > > 2 > > >  > > Page 3 > > 3Bubble SortIn the example traverse of sixcity TSP algorithm use Bubble Sort > (BSFigure 2, pp 4) tosort the field in the ascending ( step1 of > algorithm). In > BS the bottom number is comparedwith the one above number. If it is > smaller they > are exchanged. The above number got iscompared with the previous > number on top > of it and exchanged if the above number issmaller than the previous. > This goes > on till the least number reaches the top. In a similarfashion second > least > number is also found out. This goes on till all the field is > sorted.Algorithm > Complexity analysis is done by ascertaining, in the number of > comparisons in the value of components nIn a general case of > BS used in > the first step of the Algorithm provided, for Ncity TSP,The number of > comparisons=n + (n1)+?+1 x nnn= n x n2? n( 1+2+?..+n)nFrom this we > see > that the algorithm grows faster than a n2and is of complexity o(n2) > nnnen log > n111244399and so on.The table above shows that nn= en log n, where log > n is the > upper bound and o(n logn).This shows that the ncity tour and it's > subsidiary > the 5city tour algorithm turns to be ofexponential time complexity > and hence NP > complete when Bubble Sort is employed. Thisis like Exhaustive > search.The minimal > cost of the traverse is found from Table 1 to be 2100 from all > traverses > withCochin(C) as starting city and Pune(P) as the destination.Quick > SortNow > Quick Sort (QSFigure 3, pp 5) is used instead of Bubble Sort in the > first step > of theminimal traverse algorithm given above. QS is faster algorithm > but it has > its problemwhich is overcome when it is done like that of sorting a > TelephoneDirectory for faster convergence. The numbers should be > arranged in > close ranges beforethe sort like that of a Telephone directory. QS > consists of > marking the top and bottomelements and choosing a Pivot element which > is the mid > point element of the arrayelements. Thus the elements are divided into > two parts > top part and bottom part (Caveat: The elements to the top of the pivot > should be > smaller than the elements to the bottom ofthe pivot. This is a > standard practice > when using Quick Sort to make it effective for fasterconvergence.). > Now take the > top part exchange the top and pivot if pivot is smaller thanthe top. > Again > divide the top part into two parts by finding the midpoint of the top > part.Of > this top part exchange the top and midpoint if midpoint is smaller > than the top. > If thereis no more elements then come to the bottom part of this and > exchange > the midpoint element and the pivot if pivot is smaller than the > midpoint > element. If there are more > > >  > > Page 4 > > 4 > > >  > > Page 5 > > 5 > > >  > > Page 6 > > 6elements then before exchanging the bottom part the new top part got is > divided againinto two parts and the top and bottom of it is sorted as > above > before sorting the bottompart of the first division. Thus after > sorting the top > part of initial division in a similar waythe bottom part of the > initial division > is also sorted. To put it simply the sorting is carriedout by dividing > and > exchanging which is nested deep as the number of elements increase.As > for Bubble > Sort the algorithm complexity for Quick Sort is found to be,n  > n = > nnsince there are n comparisons in each field and there are n such > fields. See > table 1 forreference. See table below.nn log n1021.333.2and so on.This > shows > that Quick sort has complexity O(n)  O (n log n). The > algorithm grow > fasterthan (n log n) this being the lower bound being the information > mass. > Table above showsthat (n log n) gives the actual comparisons in Quick > Sort. For > example for list of 1 city, 0comparison, for 2 cities 1 comparison, > for 3 > cities 3 comparisons and so forth given by (nlog n).Algorithm with O(n > log n) > complexity is P type algorithm since n log n is a polynomial..The > resulting > minimal cost using the minimal cost algorithm which turns out to be P > typeO(n > log n), when Quick Sort is used instead of Bubble Sort with starting > city > asCochin(C) and destination Pune(P), turns out again to be 2100 from > all the > possibletraverses .It can be proved that,Let K be the Largest bit > pattern NP or > P possible.kNumber of such patterns =  ! > =2Taking n bit > cluster out of all this possible clusters,Probability is taken for > each stream > of bit NP or P to give it a unique identity.k*Probability of 1such n > bit cluster > =1 / (  ! )=2Bounds start at 2 since that is > the least > number required to form a combination., moreovermore than 1 bit is > always > required.Probability of 1 bit out of the n bits in the cluster > is,Taking Joint > Probabilities,kk(0.5+ 1/n  0.5 x 1/n)(1/(  !)  (0.5+ > 1/n  0.5 > x 1/n)( 1/(  !) =2=2 > > >  > > Page 7 > > 70.5(n1) , for Large n this converges.nThe proof starts with description of a > theoretical Computer.Let  be a language. Then L  >  be a > language in x  L halts for the Computer, then x >  {{x}} >  L halts in Polynomial time.Let y  > halts in > Polynomial time or P only if y {{x}} or has counterparts which > are {{x}} in which case it is Non deterministic Polynomial > time or NP OR > it has delimiteror language K which may or may not be  L.Let > PS , *And NPK, > * is delimiter for S's and  delimiter for K's, > S and K > are sets of symbol sequences.Usually an Automaton is defined as a 5 > tuple, but > here for simplicity I choose a 2tuple.MNP E(h) >  , > NP H(h)Where, NP E(h) = Exception Halts or > Dead Drop > HaltsNP H(h) = Normal Halts which may be dead drop halted.NP > NP >  (NP/P)  P(NP/P)  P(P) > = > P(P)NP NP   P(NP/P)  > P(P), all being HaltsTaking Bayesian ProbabilitiesP > (PNP) = > P(NP/P)P(P) = P(X) space iff P( NP/P) P(P)P(NP) > P(NP/P) = > P(P/NP)P(NP)P(P)If 1/β is the probability of occurrence of NP and > P thenthe > above two equations becomes 1/β provingP(PNP) = P(NP/P)(P/ > NP) = > (NP/P)Also, both NP and P occurs at a probability > 1/(2п.√(1+x2))Additionally functional equality can be > proved between > NP and P,Problem(P), Bubble sort(B), Quick sort(Q), sorted table(T), > result(R)and Search(S)Now,BSQSP => T => R and P => T => RHere, S(B(P) ) > = S(Q(P)) > = Rie; Q(P) = B(P) where,B(P) is NP and Q(P)=P which are proved to be > functionally equivalent through theirproducing the same sort > results.ie; (P/NP) > = (NP/P) .This is true since the speed of the Computer should not be > taken as a > constraint totheir equality. This not only proves that all NP's belong > to P but > also that we can findP solutions that can be determined on the > Computer. This > proves the results of theBayesian equation.It can be uniquely > identified by log > n in P(X) which later on is the empiricalprocess to > verify the > proof. n is the numerical value of the P stress.H is Halt > > >  > > Page 8 > > 8X = log n and B(X)=Binary(X)Then, H=NP/P=B(X)P H PreflexiveP H NP/P = NP/P H > Psymmetric(P H X)  (X H NP/P)  P H NP/ > Ptransitivewhere, P and > NP/P  B binary numbers and XI or R or N or B binary > numberswhich > can be uniquely identified by the numerical value log n as explained > earlier.Here, their existence is not required in the same class of > numbers > considering theunique nature of the phenomenon and problem. Also in > the TSP > problem solved NPand P produce the same result 2100 and so this can be > taken as > the representative casefor all NP, P problems, where NP/P and P halts > for > smaller n.Where all NP/P = NPIt is noticed that the relation between P > (NP/P) and > P(P) is an equivalence relation, HHalt being the Relation. We also > see that > P(NP/P) is one to one and onto P(P)making it an Equivalence > Class.So > that MP(H) instead of > MNP > E(h) , NP H(h) as assumed > earlier.Note:Let >  be a Language and *in it NP.Let w be a Language in > y*and xw  then, from > above,y >  wkwhere k   > y < >  max w2The double > brazes > convention is forfeited here to comply with the description of > theproblem given > on www.claymath.org.Let # be a relational operatorAs per the above > results,y # x > where # may or may not be a part of This shows all possible > combinations > of 0's and 1's are  PNP = PRefer to Figure 4 for visualization > of the > phenomenon.It can be empirically verified as follows. If n is the > numerical > value of the bit pattern then,Log n gives the individual > identification of the > bit pattern out of all the  bit patternswhere n  > . This > is also the growth rate from a single bit from numerical 0. So whenP > (NP) is > associated with P(P) it is identified as Log n.Also,P(P){P}P(NP){P}P > (NP/P){P}The > proof given above shows that{P(NP/P)}  {P(P)}With Exception > Halts or > Dead drop Halts taken into consideration{P(NP)}  {P(P)} >  NP=PNP > = PIn the example of TSP we proved NP result =2100 and P results = > 2100 so > thatNP = P, like when x =a and y=a then x = y.Also, both NP and Pare > Polynomials. > > >  > > Page 9 > > 9Also both NP and PThere cannot be a contradiction in this because always a > Brute force method isavailable to solve NP's which are P itself as per > the proof > by Baysein but the speed of the Computers may be a limiting factor, > until new > Computers based on new materialfor speed is manufactured in > future.ConclusionContention shows us that Algorithm which turns into > either P > type or NP type accordingto the choice of the sort algorithm employed > produces > the same resulting costs 2100,proving the general case of NP =P. The > special > case is always dead drop halted. Sinceboth the general and special > case of NP > halts, and the Turing Machine comes to halt by > > >  > > Page 10 > > 10doing so all NP's has to be subset of P type algorithms. All NP type > Algorithms thusformed are thus part of the P type or is partnered > through a > Relational operator # whichmay or may not be part of P.The problem > description > directs us only to prove that y x2 > *.The > Bayesian proves that all NP occurring at P is a subset of all P itself > provingthe above requirement(Italics in the proof). P=NP numerically > (probability > and result),functionallyan relationally. Clay Millennium problem > remain > resolvedNP = Pin all the casesTuring's Halting problem stipulates > either a > Turing machine that halts or run indefinitelywithout halting for a > given set of > symbols. Here we proved that all symbols stops theTuring > Machine.Turing's > Halting Problem remains resolved.To find P type of Algorithms for all > NP type > Algorithms not yet found out can be worththe while. Exception Halts > are of no > consequence. > > >  > > Page 11 > > 11C*533H *2100B *864M > *1552PCB533HP548BM331MB331PH548CM681HB562BC533MC681PB835CH1095HM688BH562MH688PM1\ > 166CP1221HC1095BP835MP1166PC1221Table 1 > > >  > > Page 12 > > 12Acknowledgment: Late Dr. K.R. Ramakrishna and my Colleagues there, EE Dept., > IISC,Bangalore for giving me opportunity to work with computers, > Claude Shannon > for hisInformation Theory works. Prof. Thathachar V.L of > IISc,Bangalore and his > Ph.D students for leading me into Algorithm complexityanalysis when I > attended > their departmental seminar on the same subject in 1982. GregoryChaitin > for his > article `The limits of reason' in Scientific American, Indian Edition > ofMarch > 2006, which ultimately made me aware of Clay Maths problems and all > mycolleagues, friends and Professors who supported me in my endeavor > in > understandingphilosophies of my multiple professions. S.E Goodman and > S.T > Hedetniemi for theirbook `Introduction to the design and analysis of > Algorithm' > published by McGraw Hill,for introducing me to the fundamentals and > possibilities and impossibilities. Last but notthe lease the Google > search sight > linux.Wku for a quick review of Sorts after a leave ofprobably 20 odd > years when > Mr. Chaitin's article led me back into it again one more time. > > >  > > Page 13 > > 13Mathew Cherian B.E, M.B.A(Western Michigan.)1B7 Penta Queen, B1 > BlockPadivattom, Cochin 682024, Kerala, India. Email: imag94@... > > >  > > Page 14 > > 14 > > > Great Job. The above message is from the inbox of Martin Musatov. It > was > delivered to marty.musatov@gmail.com. Note that scriber77@yahoo.com is > also an > email address I have had since 2005. (founder of the > board:pequalsnp@yahoogroups.com).Martin Musatov: As to languages and formulations, the language of questions must be finite arithmetic, where the proper question is; "What is the true fundamental mathematical problem with capitalism? Or any other form of heiarchical organization, of any other possible nondestructive social contracts?"P=NP i.e., Proof=NonPossibles, add em up, and choose what's left___the possibles...It's just a simple combinatoric process, existing from the earliest of written and recorded languages...All conversions of unknowns are achieved by isomorphically changing/updating psychologies/semantics to arithmetic logics through their global pragmatic uses. Martin Musatov. P.S. Special Thanks to my friend and mentor Lloyd G.

