Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Tzahi Fadida
    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
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.