
Re: P=NP Proof Published at CERN
Posted:
May 11, 2009 4:57 AM


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

