Storage requirements for deterministic polynomialtime recognizable languages

摘要

An intriguing question is whether (log n)2 space is enough to recognize the class of languages recognizable in deterministic polynomial time. This question has earlier been narrowed down to the storage required to recognize a particular language called SP. SP is clearly in and it has been shown that if SP has tape complexity (log n)k, then every member of has tape complexity (log n)k. This paper presents further evidence in support of the conjecture that SP cannot be recognized using storage (log n)k for any k. We have no techniques at present for proving such a statement for Turing machines in general; we prove the result for a suitably restricted device.