Check out some more weird stuff about Incremental-Polynomial complexity

and Polynomial, but in the input AND output.

This one we use in databases. i.e. even if the output is exponential, even

2^n. The algorithm is still polynomial in the input and output if it is not

something like 2^(2^n) run time.

I am 95% sure this is the article. check it out for more weirdness:

@article{JP88,

author = {David S. Johnson and M. Yannakakis and Christos H. Papadimitriou},

title = {On generating all maximal independent sets},

journal = {Inf. Process. Lett.},

volume = {27},

number = {3},

year = {1988},

issn = {0020-0190},

pages = {119--123},

doi = {

http://dx.doi.org/10.1016/0020-0190(88)90065-8},

publisher = {Elsevier North-Holland, Inc.},

address = {Amsterdam, The Netherlands, The Netherlands},

}

On Saturday 10 February 2007 13:31, Shlomi Fish wrote:

> I wrote about the algorithms' class NP and NP-Completeness here:

>

> http://tech.groups.yahoo.com/group/hackers-il/message/2654

>

> A few weeks ago I learned about PSPACE:

>

> http://en.wikipedia.org/wiki/PSPACE

>

> It took me some time to understand what it was all about. Apparently, while

> P is the algorithms that can be solved in polynomial time (and polynomial

> space), and NP is the class of algorithms whose verification can be done in

> polynomial time (and still be solved in polynomial space after an

> exponential or better time), then PSPACE is the class of algorithms that

> can be solved using polynomial space and potentially inifinite time. So

> PSPACE contains NP.

>

> PSPACE-Complete are algorithms in PSPACE which every other algorithm in

> PSPACE can be reduced to them. Sokoban (

> http://en.wikipedia.org/wiki/Sokoban ) was shown to be PSPACE-complete:

>

> http://www.cs.ualberta.ca/~joe/Preprints/Sokoban/

>

> Today when I visited wikipedia I also found about P-Complete:

>

> http://en.wikipedia.org/wiki/P-complete

>

> Another thing I wondered for some time, is whether there is a class "NNP"

> which is the class of algorithms whose verification algorithms are in NP.

>

> Regards,

>

> Shlomi Fish

>

> ---------------------------------------------------------------------

> Shlomi Fish shlomif@...

> Homepage: http://www.shlomifish.org/

>

> Chuck Norris wrote a complete Perl 6 implementation in a day but then

> destroyed all evidence with his bare hands, so no one will know his

> secrets.

--

Regards,

Tzahi.

--

Tzahi Fadida

Blog: http://tzahi.blogsite.org | Home Site: http://tzahi.webhop.info

WARNING TO SPAMMERS: see at

http://members.lycos.co.uk/my2nis/spamwarning.html