Re: PSPACE Algorithms and PSPACE-Complete

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

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


 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/hackers-il/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/hackers-il/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:[email protected] 
    mailto:[email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/