An observation on time-storage trade off
An observation on time-storage trade off
复制标题
对时间存储权衡的观察
DOI：
--
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
S. Cook
中科院分区：
文献类型：
--
作者：
S. Cook
最近，有几项尝试证明，在确定性存储（log n）2中可以识别@@@@@（I.E.，确定性多项式时间）中的每组字符串。尝试中使用的方法基于[1]的方法，在这种方法中，可以在存储（log n）2中接受每个上下文的语言2我们在本文中的论文是这些尝试必须失败。我们定义了一组特定的字符串，显然是在@@@@中，但是在某些明确的意义上，无法使用[1]中的技术在存储（log n）2中识别。我们猜想没有图灵机识别存储（log n）2中的SP，并表明如果此猜想是错误的，则实际上可以在存储（log n）2中识别@@@@的每个成员。
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.