|
|
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:dd08dfe2-baa4-452b-abeb-c30f8f62a9cd@v35g2000pro.googlegroups.com...
> On May 13, 8:10 am, "VMCM1905" <VMCM1...@gmail.com> wrote:
>
> > "MartinMusatov" <marty.musa...@gmail.com> wrote in message
>
> >news:00064f99-ab12-4c0e-8685-c0349a9180d7@s21g2000vbb.googlegroups.com...
>
> > VMCM1905 a écrit :
>
> > > "Mensanator" <mensana...@aol.com> wrote in message
> > >news:a26c01fd-835e-469c-b4f4-4e2d3d81a4c9@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: Computer-Aided 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 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 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 N-City
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 5-city tour
is demonstrated as a representative example of the N-city 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 six-city TSP algorithm use
Bubble Sort
(BS-Figure 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 N-city TSP,The number of
comparisons=n + (n-1)+?+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 n-city tour and it's
subsidiary
the 5-city 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 (QS-Figure 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(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@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 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.
..
--------------------------------------------------------------------------------
[ABOVE IS MARTIN MICHAEL MUSATOV'S P==NP PROOF TEXT POSED AS A
CHALLENGE TO VMCM1905 AKA "MENSANATOR"]
--------------------------------------------------------------------------------
|
|
