Re: P vs NP and the analog machine

From: Paul J. (it_paul_jay_at_hotmail.com)
Date: 02/24/04 

Date: 23 Feb 2004 17:05:26 -0800

"The Lord of Chaos \(Suresh Devanathan\)" <surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message news:<c1d7hb$1hab3s$1@ID-182852.news.uni-berlin.de>...
> err
> x - n\mu = +/- \sqrt(2n) \sigma sqrt(N) sqrt( log N -1)
> x = n \mu +/- n sqrt(2) \sigma sqrt( log N -1)
>
> x/(n \mu) -> 1 +/- \frac{sqrt(2) \sigma sqrt( log N - 1)}{\mu}
>
>
> I will leave the math here.
>
>
>
> "The Lord of Chaos (Suresh Devanathan)"
> <surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
> news:c1c0f5$1g7eb2$1@ID-182852.news.uni-berlin.de...
> > One more thing
> >
> > although the % deviation = (standard deviation)/(average) goes to 0, the
> > deviation between the path with the least cost and the average cost
> doesnt.
> >
> > It can be seen from the following analysis. The notation is sloppy
> >
> > Let P(a) be probability of getting a value anything under a, given that a
> is
> > normally distributed.
> >
> > P(a) = 1/N!
> >
> > P ( (x - n \mu)/( \sqrt {2 n} \sigma) ) = 1/N!
> >
> > For asymptocially small values P(a) would be about exp(-a^2)/ a
> >
> > exp(-a^2)/ a = 1/N!
> >
> > -a^2 = -log(N!)
> > a^2 = N (log N - 1)
> > a = sqrt(N) sqrt( log N - 1)
> >
> > x - n\mu = \sqrt(2n) sqrt(N) sqrt( log N -1)
> > x = n \mu + n sqrt(2) sqrt( log N -1)
> >
> > x/(n \mu) -> 1 + \frac{sqrt(2) sqrt( log N - 1)}{\mu}
> >
> > It does us no good to find just the average one.
> >
> >
> > "The Lord of Chaos (Suresh Devanathan)"
> > <surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in
> message
> > news:c1bujo$1gmtka$1@ID-182852.news.uni-berlin.de...
> > > This is one thing i can prove.
> > >
> > > Take an element a_ij. Let x = a_ij Assume that x has the pdf p(x)
> > >
> > > Now, the total cost along certain tour can written as
> > >
> > > cost = \sum a_mn
> > >
> > > Now, each a_mn also has the distribution p(x), by definition of p(x) .
> > > From the distribution, we can calculate the \mu and \sigma
> > >
> > > For a tour of length n,
> > > The distribution of costs would have the mean (n) \mu and the standard
> > > deviation \sqrt(n) \sigma
> > >
> > > % deviation from the mean is \frac{\sqrt(n) \sigma}{ n \mu} =
> > > \frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
> > >
> > > As n->infy, % deviation goes to 0. In a way, all paths "relatively"
> have
> > > about the same n \mu
> > >
> > > Of course, the proof makes implicit assumption that p(x) is not changing
> > > with n.
> > >
> > > Either, i have gone completely crazy, or have discovered something
> > > completely interesting. It looks so deviously simple.
> > >
> > > -suresh
> > >

> As n->infy, % deviation goes to 0. In a way, all paths "relatively"
> have
> about the same n \mu

This works for large N. However, let me back up a few steps. You are
assuming N! for all possible routes between some i and j (or k). This
assumption may be
wrong. To compute the possible paths of any length binomially we
should use
N!/((N-2)!) since we require just 2 vertices for each path. Going
further still, and assuming random distribution of path choice
probabilities, we could multiply our binomial by p^n * (p-1)^n-2 where
p should be 1/N.

I think your math, above, for 'normalization' was accurate, but let me
rephrase it for clarity (if not redundancy).
     normalized = (random variable - finite mean) / standard deviation

where standard deviation can be calculated by:
    sd = sqrt[ (1/n)*((n0^2)+(n1^2)+(n2^2...) - (average
expectation)^2 ]

In general, we could apply transitive closure (~composition) to find
the longest path lengths by assuming a fully converged (or total mesh)
and removing increasing path lengths by squaring over all the
relations (R^n). Where n=sqrt(nodes) should be a weak upper bound on
the total of squarings needed. In this way, the step which loses the
most paths is found to be contain the average path length.

Relevant Pages

  • Re: [IBM-MAIN] Software Pricing
    ... The cost of acquisition is forgotten ... It's just math, not rocket science. ... For IBM-MAIN subscribe / signoff / archive access instructions, ... send email to listserv@xxxxxxxxxxx with the message: GET IBM-MAIN INFO ...
    (bit.listserv.ibm-main)
  • Re: WTB: BBB in Lower WI. Willing to pay for shipping. Can arrange.
    ... math must be done taking out the costs and considering only the profit ... Only Georgiana and Gene probably know the full extent of the loss. ... divided by the number of machines, you can work the actual cost of the ... The math here is a little skewed :-) If they cost him 8K to make and he ...
    (rec.games.pinball)
  • Re: copying DVDs
    ... an entire unprotected DVD to the hard drive. ... Joe, the math is simple: ... What's your additional cost for Toast? ... it costs you Y more than me to burn that way. ...
    (rec.music.gdead)
  • Re: Acoustic vs. Digital: The Great Debate
    ... each 20 seconds long (to make the math easier). ... >> I suppose that's only nine times the memory that's in the computer I'm ... I have in my hand a 1 GB SecureDigital card about the ... >size of a postage stamp that cost me just under $100. ...
    (rec.music.makers.piano)
  • Re: More on RC4/n
    ... > required for this attack? ... For small n, deviation and mean are ... So the cost may explode beyond ... RC4/5 because lowlying fruit just isn't there. ...
    (sci.crypt)
Loading