An Improved Proof of the Rabin-Harmanis-Stearns Conjecture
We offer an improved presentation of Aanderaa's constructive proof of the Rabin-Hartmanis-Stearns conjecture: For all k≥2, there exists a language Lk such that Lk can be recoginzed by a k-worktape real time Turing machine but cannot be recognized by any (k-1)-worktape real time Turing machine....
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148951 |