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?

  • 1
    $\begingroup$ I don't understand your setup. Does the machine not need at least $\Omega(n)$ time just to read its input? $\endgroup$ – András Salamon Aug 9 '15 at 9:14
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Brout Aug 9 '15 at 9:19
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon Aug 9 '15 at 9:28
  • 1
    $\begingroup$ I think $n^{2-o(1)}$ is for multi tape. Where is $n^{2+o(1)}$ bound referenced? $\endgroup$ – Brout Aug 9 '15 at 9:40
  • $\begingroup$ 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. $\endgroup$ – András Salamon Aug 19 '15 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.