
Re: P=NP Proof Published at CERN
Posted:
May 20, 2009 1:24 AM


On May 15, 4:07 pm, "VMCM1905" <VMCM1...@gmail.com> wrote: > "MartinMusatov" <marty.musa...@gmail.com> wrote in message > > news:dd08dfe2baa4452babebc30f8f62a9cd@v35g2000pro.googlegroups.com... > On May 13, 8:10 am, "VMCM1905" <VMCM1...@gmail.com> wrote: > > > "MartinMusatov" <marty.musa...@gmail.com> wrote in message > > >news:00064f99ab124c0e8685c0349a9180d7@s21g2000vbb.googlegroups.com... > > > VMCM1905 a écrit : > > > > "Mensanator" <mensana...@aol.com> wrote in message > > >news:a26c01fd835e469cb4f44e2d3d81a4c9@s31g2000vbp.googlegroups.com... > > > On May 11, 10:44?pm, "VMCM1905" <VMCM1...@gmail.com> wrote: > > > > "Martin MichaelMusatov" <marty.musa...@gmail.com> wrote in > > > > messagenews:29921474.87652.1242020365442.JavaMail.jakarta@nitrogen.mathforum.org... > > > > > > Who is "JSH"?MartinMusatov > > > > > Oh please don't tell me Harris has moved from being a crank who thinks > > > > he > > > > has a simple proof of FLT to a crank who thinks he can prove P vs NP? > > > > >I don't see how that follows, but yes, he thinks he's solved > > > >the Travelling Salesman Problem. > > > > It follows, but in a convoluted manner. > > > As to the OP's question, there are many sites that discuss JSH as a > > > crank. > > > > When did JSH give up on FLT, and how was he finally convinced? For the > > > record I have bo idea who JSH or what FLT is. ~~~~MMM~~~~NNN > > >www.google.com"how to use google" > > > "JSH FLT" > > "James Harris" Fermat's Last Theorem > > >http://www.crank.net/harris.html > > Thank you for explaining, please cite specific examples from which to > draw the comparison. MartinMusatov > > No need for me to do your research for you.
Dear VMCM1905 a écrit : aka "Mensanator" <mensana...@aol.com>,
As you suggested I have done my research. I hereby officially publicly challenge your intellectual authority and intelligence with the text below.
I assert your claim P does not equal NP is false. The basis of my assertion is the below text. If you still believe you are correct in your assumption, I challenge you to explain to the community why the below text does not qualify to prove [P==NP]:
Respectfully,
Martin Michael Musatov
[BELOW IS MARTIN MICHAEL MUSATOV'S P==NP PROOF TEXT] Original Message From: Martin Musatov <marty.musatov@gmail.com>
Date: Fri, 15 May 2009 16:30:54 To: <marty.musatov@gmail.com> Subject: ComputerAided Polynomial Time Processing
 In pequalsnp@xxxxxxxxxxxxxxx, "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=P AbstractThe 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 the of 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 the destination city without traversing a city twice. An algorithm is developed which employs Bubble Sort(BS) as component which is proved NP complete. The same Algorithm when Quick Sort(QS) is employed instead of BS turns out to be P type. They produce the same minimal cost, proving NP=P. The Halting problem remain resolved.Contents Non deterministic polynomial time NP algorithms can be either General case which are all algorithms that have algorithms but don't halt in legitimate time which will go on beyond legitimate time to halt or has to be `Drop Dead Halted' and Special case where the symbol sequences are gibberish in nature and are made to halt with drop dead halts.For the general case an NCity Travelling Sales Mans Problem (TSP) is chosen to prove ehe phenomenon NP=P. We are required to find out the minimal cost incurred by him when touring all these selected cities on a sales tour starting from a selected city to a destination city not stepping into one city twice in the tour. Here a 5city tour is demonstrated as a representative example of the Ncity tour with the costs marked in the graph (Figure 1, pp2). It is bidirectional graph and the costs are identical for forward and backward traverse. Representative costs based on distance between cities tend to produce converging results for the Algorithm in the cities chosen. For the sake of this problem it is sufficient 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 other cities. Mark the city header with * and write the minimal cost beside it. (Since the list is sorted the minimal costs will remain at the beginning of the list) . Underline also, 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 choose the next minimal cost. Add it to the previous cost. Place a * at the header and write 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, (since this is a forward looking algorithm).6. You do this for all transitions from the starting city and the minimal is cost is the least cost arrived.Table 1 on last page (pp 11) gives the rundown of this Algorithm.

Page 2 2

Page 3 3Bubble Sort In the example traverse of sixcity TSP algorithm use Bubble Sort
(BSFigure 2, pp 4) to sort the field in the ascending ( step1 of algorithm). In BS the bottom number is compared with the one above number. If it is smaller they are exchanged. The above number got is compared with the previous number on top of it and exchanged if the above number is smaller than the previous. This goes on till the least number reaches the top. In a similar fashion 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 n. In 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)n. From 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 log n).This shows that the ncity tour and it's subsidiary the 5city tour algorithm turns to be of exponential time complexity and hence NP complete when Bubble Sort is employed. This is like Exhaustive search.The minimal cost of the traverse is found from Table 1 to be 2100 from all traverses with Cochin(C) as starting city and Pune(P) as the destination.Quick Sort Now Quick Sort (QSFigure 3, pp 5) is used instead of Bubble Sort in the first step of the minimal traverse algorithm given above. QS is faster algorithm but it has its problem which is overcome when it is done like that of sorting a Telephone Directory for faster convergence. The numbers should be arranged in close ranges before the sort like that of a Telephone directory. QS consists of marking the top and bottom elements and choosing a Pivot element which is the mid point element of the array elements. 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 of the pivot. This is a standard practice when using Quick Sort to make it effective for faster convergence.). Now take the top part exchange the top and pivot if pivot is smaller than the 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 there is 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@xxxxxxxxxx Note that scriber77@xxxxxxxxx is also an email address I have had since 2005. (founder of the board:pequalsnp@xxxxxxxxxxxxxxx).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.
..
 [ABOVE IS MARTIN MICHAEL MUSATOV'S P==NP PROOF TEXT POSED AS A CHALLENGE TO VMCM1905 AKA "MENSANATOR"] 

