An observation on time-storage trade off
SA Cook - Proceedings of the fifth annual ACM symposium on …, 1973 - dl.acm.org
Proceedings of the fifth annual ACM symposium on Theory of computing, 1973•dl.acm.org
Recently there have been several attempts to prove that every set of strings in@@@@(ie,
recognizable in deterministic polynomial time) can be recognized in deterministic storage
(log n) 2. The methods used in the attempts were based on that of [1], in which it is shown
that every context free language can be accepted in storage (log n) 2 Our thesis in the
present paper is that these attempts must fail. We define a specific set SP of strings which is
clearly in@@@@, but in a certain well-defined sense cannot be recognized in storage (log …
recognizable in deterministic polynomial time) can be recognized in deterministic storage
(log n) 2. The methods used in the attempts were based on that of [1], in which it is shown
that every context free language can be accepted in storage (log n) 2 Our thesis in the
present paper is that these attempts must fail. We define a specific set SP of strings which is
clearly in@@@@, but in a certain well-defined sense cannot be recognized in storage (log …
Recently there have been several attempts to prove that every set of strings in @@@@ (i.e., recognizable in deterministic polynomial time) can be recognized in deterministic storage (log n)2. The methods used in the attempts were based on that of [1], in which it is shown that every context free language can be accepted in storage (log n)2 Our thesis in the present paper is that these attempts must fail. We define a specific set SP of strings which is clearly in @@@@, but in a certain well-defined sense cannot be recognized in storage (log n)2 using the techniques in [1]. We conjecture that no Turing machine recognizes SP within storage (log n)2, and show that if this conjecture is false, then in fact every member of @@@@ can be recognized within storage (log n)2.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果