Separation of PSPACE and EXP
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917608603779072 |
|---|---|
| author | Czerwinski, Reiner |
| author_facet | Czerwinski, Reiner |
| contents | This article shows that PSPACE not equal EXP. A simple but novel proof technique has been used to separate these two classes. Whether an arbitrary Turing machine accepts an input when the running time is limited has been computed in this paper. Then, the limit goes to infinity. Thus, methods of the recursion theory can be applied to problems of computational complexity theory without violating the relativization barrier. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_14316 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Separation of PSPACE and EXP Czerwinski, Reiner Computational Complexity 68Q15, 03D15 F.1.3; F.2.3 This article shows that PSPACE not equal EXP. A simple but novel proof technique has been used to separate these two classes. Whether an arbitrary Turing machine accepts an input when the running time is limited has been computed in this paper. Then, the limit goes to infinity. Thus, methods of the recursion theory can be applied to problems of computational complexity theory without violating the relativization barrier. |
| title | Separation of PSPACE and EXP |
| topic | Computational Complexity 68Q15, 03D15 F.1.3; F.2.3 |
| url | https://arxiv.org/abs/2104.14316 |