Content deleted Content added
No edit summary |
PSPACE |
||
Line 9:
Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated.<ref>{{Cite journal|doi=10.1145/322234.322243|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=[[Journal of the ACM]]|volume=28|issue=1|pages=114–133|year=1981|doi-access=free}}</ref>
For example, it was proven in 1978<ref>{{Cite journal |last=Fortune |first=Steven |last2=Wyllie |first2=James |date=1978 |title=Parallelism in random access machines |url=https://doi.org/10.1145/800133.804339 |journal=Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 |___location=New York, New York, USA |publisher=ACM Press |pages=114–118 |doi=10.1145/800133.804339}}</ref> that for any <math display="inline">T(n) \ge \log n</math>, and with the restriction that the number of processors of the PRAM is no more than exponential in parallel running time, we have<math display="block"> \bigcup_{k=1}^{\infty} T(n)^k \text{-time PRAM} = \bigcup_{k=1}^{\infty} T(n)^k \text{-space} </math>In particular, <math display="inline">\bigcup_k \log^k n \text{ PRAM} = \bigcup_k \log^k n \text{ SPACE}</math>, and polynomial-time '''PRAM''' = '''PSPACE'''. Note that the exponential amount of processors is likely required. Specifically, suppose that only a polynomial number of processors are required for some [[PSPACE-complete|'''PSPACE'''-complete]] problem, then it would show that '''PSPACE''' = '''P''', a major unresolved hypothesis that is expected to be false.
Also, for non-deterministic versions,<math display="block"> \bigcup_{c>0} cT(n) \text {-time NONDET PRAM }=\bigcup_{c>0} 2^{cT(n)} \text {-time }
</math>In particular, nondeterministic <math display="inline">O(\log n)</math>-time PRAM = NP and nondeterministic polynomial time PRAM = nondeterministic exponential time.
| |||