[vorbis-dev] vorbis-utils features ;)

[Keith Wright]

> From: xiphmont at xiph.org (Monty)
> > In-reply-to: kwright at free-comp-shop.com
> > > 
> > > It's an NP-hard problem [at least] in the general case.  If it wasn't,
> > > compression would be easy.
> > 
> > "NP-hard" is a description of computational complexity.
> 
> Yes, and the term is commonly generalized to apply to [among other
> things] tasks that, at first glance to a human, seem trivial because
> of the n-billion-way parallel processing capability of the brain.
> 
> > After all you hope to do it in linear time or streaming
> > is impossible.
> 
> Depends on which variable dependencies being linear... it's linear on
> the total stream length, but roughly [theta] n lg(n) and [big-O] n^2
> on window size.

Exactly right.  Sorry if I went off into theory professor mode at
an inapropriate time.  In the future you can call your dog
"NP-hard" without me trying to correct you and explain what it means.

Perhaps a better description for the difficulty is "AI-complete".
This is more accurate despite, or rather because, the term
has no precise meaning at all.


-- 
     -- Keith Wright  <kwright at free-comp-shop.com>

Programmer in Chief, Free Computer Shop <http://www.free-comp-shop.com>
         ---  Food, Shelter, Source code.  ---

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'vorbis-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.