## Re: [hackers-il] PSPACE Algorithms and PSPACE-Complete

Expand Messages
• 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
Message 1 of 2 , Feb 10, 2007
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.
--