
December 16th, 2013, 12:55 AM
#16
Re: A better algorithm
Originally Posted by superbonzo
an avarage "with respect to everything" is either nonsense or it can be reduced to the choice of a ( possibly degenerate and/or a family of ) probability space.
It was just a way of describing "any possible input" because that's how I define "average input".
My point was that using the OP's input (even in the form of a probability distribution) as you suggested won't give the averagecase complexity of the algorithm. For that all possible inputs should be considered, not just one specific. It's a conceptual insight independent of any mathematical formalism such as probability theory.
I stop here because I know you're a probabilities fanatic who cannot fathom anything that doesn't come with a distribution. A discussion would go on forever or break down completely when you introduce that compass again.
Last edited by razzle; December 16th, 2013 at 02:34 AM.

December 16th, 2013, 03:39 AM
#17
Re: A better algorithm
Originally Posted by razzle
It was just a way of describing "any possible input" because that's how I define "average input".
why calling it "avarage", why not give it another name then ?
for the sake of curiosity, how is such a complexity class defined and what's the benefit of adopting such a point of view ?
Originally Posted by razzle
you're a probabilities fanatic who cannot fathom anything that doesn't come with a distribution.
yes I am, but not because I'm in love with probabilities ( or compasses ), indeed I think there are far superior alternatives both technically and foundationally to characterize "randomness" and statistics in general.
But, I've seen too many people with science degrees producing wrong or ambiguous results ( sometimes even slipping through peer review ) about propability and statistics, and the language of propability theory ( the modern, measure theoretic formulation ) seems the most accepted among practitioners.

December 16th, 2013, 04:09 AM
#18
Re: A better algorithm
Originally Posted by superbonzo
and what's the benefit of adopting such a point of view ?
That's what I meant. You confuse probability theory with reality and fail to understand it's just one formalism among many.
To me how an algorithm responds to any input rather than one specific input is a succinct and to the point description of the averagecase. And rember that before this thread you had it wrong because you couldn't look beyond the narrow probabilistic notion of an average as the "center of distribution" or "first moment" or however you like to think about it.
It's for the same reason you could never accept that the "escape the waterfront" problem we discussed a while ago could be solved perfectly fine without any probabilistic reasoning whatsoever. The notion of complete uncertainity as opposed to a defined distribution struck you as impossible, and probably still does. With a track record like that it's hard to consider you a relevant spokesperson for practitioners, much less a solid judge of the scientific abilities of others.
Last edited by razzle; December 16th, 2013 at 05:14 AM.

December 16th, 2013, 05:55 AM
#19
Re: A better algorithm
flames and weak arguments .. this is how you react to any form of debate; I genuinely asked you to explain your idea of "avarage" and why it should supersede its more common statistical meaning, but your aversion to any form of perceived authority sadly won again.
Last edited by superbonzo; December 16th, 2013 at 06:06 AM.

December 27th, 2013, 07:28 PM
#20
Re: A better algorithm
Originally Posted by superbonzo
flames and weak arguments .. this is how you react to any form of debate; I genuinely asked you to explain your idea of "avarage" and why it should supersede its more common statistical meaning, but your aversion to any form of perceived authority sadly won again.
Come on superbonzo.
I just don't buy your single minded idea that probability theory is reality. It isn't. It's just a mathematical tool. And it's not even always called for.
It became so obviously clear in the "escape the waterfront" discussion we had. It can be solved perfectly fine without any probablity theory at all. When you explain why it cannot and that probability theory is necessary I'll listen to you. And please leave that compass out of the explanation will you.
And even in this thread your strict adherance to probability theory has lead you wrong.
YOU CLAIMED THE SPECIFIC INPUT OF THE OP WOULD REVEAL THE AVERAGE COMPLEXITY OF THE ALGORITHM.
This is wrong regardless of the definition of average. You are seriously wrong here superbonzo. Simple as that.
Furthermore, what you call "modern" probability theory it just the same old probability theory only that it has overcome some of it's shortcomings. Please notify me when it has overcome all of its shortcomings will you!
Last edited by razzle; December 27th, 2013 at 08:41 PM.

December 28th, 2013, 09:56 AM
#21
Re: A better algorithm
just for cusiosity sake, where did I even vaguely suggested that "probability theory is reality" ( whatever does this mean ) ? where did I wrote that the "specific input reveals the avarage complexity" ( whatever does this mean ) ? or that "'modern' probability theory [is not/it is/?] the same old probability theory" ( whatever does this mean ) ? and above all, why all this non sense is relevant to this discussion ?
and no, using capital letters will not make your arguments less weak. Frankly, I asked you twice to explain what your enlightened definition of "avarage" complexity is and how and why it could or should be made independent of any kind pf probabilitstic analysis, and the only answer I received has been a rhetorical misstatement of my own words ... if this is how you realize yourself then fine, no problem man, and happy new year !
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
