Stimulated by the work of Hartmanis and Berman , we study the question of the existence of a tally language L in NP such that L is in P if and only if P = NP. The method used is applicable to questions regarding the comparison of a wide range of pairs of classes of formal languages specified by machines whose computational resources are bounded in time or space.
|Original language||English (US)|
|Number of pages||8|
|Journal||Mathematical Systems Theory|
|State||Published - Dec 1 1977|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computational Theory and Mathematics