<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2015-08-09T09:14:20.733Z
I don't understand your setup. Does the machine not need at least $\Omega(n)$ time just to read its input?
András Salamon
CC BY-SA 3.0
2015-08-09T09:19:59.017Z
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})$.
Turbo
CC BY-SA 3.0
2015-08-09T09:28:43.457Z
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
CC BY-SA 3.0
2015-08-09T09:40:14.653Z
I think $n^{2-o(1)}$ is for multi tape. Where is $n^{2+o(1)}$ bound referenced?
Turbo
CC BY-SA 3.0
2015-08-19T08:22:07.153Z
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
<cc.complexity-theory><turing-machines><np-complete><pspace><space-time-tradeoff>
Space time lower bound with $\mathsf{PSPACE}$ oracle
Turbo
# Space time lower bound with $\mathsf{PSPACE}$ oracle

(Asked by: username_0 on 2015-08-08)

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?

**Tags:** cc.complexity-theory, turing-machines, np-complete, pspace, space-time-tradeoff
> **Comments:**
> **username_1**: I don't understand your setup. Does the machine not need at least $\Omega(n)$ time just to read its input?  
> **username_0**: 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})$.  
> **username_1**: 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.  
> **username_0**: I think $n^{2-o(1)}$ is for multi tape. Where is $n^{2+o(1)}$ bound referenced?  
> **username_1**: 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.  

---

## 0 answers

