|
|
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" 3-SAT... a counterexample took I
> > think a week or so, but eventually it was found.
> >
> > Next was the proof that solved equations over GF-2; in here, the
> > NP-completeness 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 Polynomialtime-NP) Algorithm
> produce
> Polynomial time (deterministic polynomial time-P)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 N-City
> 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 5-city tour
> isdemonstrated as a representative example of the N-city 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 six-city TSP algorithm use Bubble Sort
> (BS-Figure 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 N-city TSP,The number of
> comparisons=n + (n-1)+?+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 n-city tour and it's
> subsidiary
> the 5-city 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 (QS-Figure 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(n-1) , 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 2-tuple.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, H-Halt 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.)1-B7 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 non-destructive 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.
|
|
