Tuesday, February 18, 2014

why is np in pspace?

Pspace: 
PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

from http://en.wikipedia.org/wiki/PSPACE

Reason:
From: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/09PSPACE.pdf





No comments:

Post a Comment