PSPACE Algorithms and PSPACE-Complete

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-ik1l9ssToec+JF/[email protected]
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.