# Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem?

What is largest complexity class oracle that a single tape Turing machine could need so that it will need $\omega(1)$ Space time resource (as against separate space and time) to solve $\mathsf{NP}$-complete problem?

• I don't understand your setup. Does the machine not need at least $\Omega(n)$ time just to read its input? – András Salamon Aug 9 '15 at 9:14
• That is what I thought but it seems that working memory is different. That is why we are able to prove unconditional ST bound of $\Omega(n^{1.80\dots})$. – Brout Aug 9 '15 at 9:19
• The best unconditional time-space lower bound is $n^{2-o(1)}$, for nondeterministic Turing machines, by Santhanam. The lower bound you give is for the RAM model, due to Williams. Note that an NDTM can guess and check using $n^{2+o(1)}$ time-space units. – András Salamon Aug 9 '15 at 9:28
• I think $n^{2-o(1)}$ is for multi tape. Where is $n^{2+o(1)}$ bound referenced? – Brout Aug 9 '15 at 9:40
• Can the machine not just copy the input CNF formula to the oracle tape, together with a guessed assignment, using $\Theta(n)$ time and constant space, as long as the oracle is powerful enough to decide whether an input formula is satisfied by the input assignment? This only requires a rather weak oracle, no more than PTIME. I think you need to be more precise about your model if you want an answer. – András Salamon Aug 19 '15 at 8:22