Loading...
Please wait, while we are loading the content...
Similar Documents
Incomplete sets in P for logspace-reduction
| Content Provider | arXiv |
|---|---|
| Author | Czerwinski, Reiner |
| Date of Submission | 2022-01-19 |
| Abstract | In this article, we investigate the behaviour of TMs with time limit and tape space limit. This problem is in P when the time limit is unary coded. If both limits go to infinity, it is undecidable which limit is exceeded first. Thus logspace-incomplete sets in P can be constructed. This implies L $\not=$ P. |
| Related Links | https://arxiv.org/pdf/2201.08501.pdf |
| arXiv | 2201.08501 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Complexity Complexity Measures and Classes Tradeoffs between Complexity Measures Computer Science Complexity classes (hierarchies, relations among complexity classes, etc.) Complexity of computation |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |