Subject: PSPACE Algorithms and PSPACE-Complete

From: Shlomi Fish <[email-masked]>
Date: Sat, 10 Feb 2007 13:31:33 +0200

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      [email-masked]
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.

---

From: Tzahi Fadida <[email-masked]>
Date: Sat, 10 Feb 2007 13:46:03 +0200

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:
> 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
> 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:
>

-- 
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