<p>The answer to the first question is that we don't know, because we don't know whether $\mathbf P=\mathbf L$, so it could be that all $\mathbf P$ problems use only logarithmic space.</p>

<p>For the second one, most reasonable problems need at least linear time to read the input, even for non-deterministic machines, so it does not make a lot of sense to say "polynomial non-deterministic lower bound", or you need to make your question more precise.</p>

<p>Finally, the last question is like the first one: it could be that $\mathbf{NL}=\mathbf{NP}$, in which case such a problem wouldn't exist, we don't know...</p>

CC BY-SA 3.0
2014-02-18T12:00:15.993Z
Thanks for the answer! I am a bit ashamed that I missed the open question P=L.
David G
CC BY-SA 3.0
2014-02-18T12:04:39.650Z
I also changed the second question a bit to avoid linear time lower bounds. But I guess that the answer to all my questions is "we do not know".
David G
CC BY-SA 3.0
2014-02-18T16:37:06.123Z
having said that, there are problems in P with (weak) super linear *time* lower bounds.
Suresh Venkat
CC BY-SA 3.0
2014-02-17T17:38:28.087Z
2014-02-17T17:38:28.087Z
Denis
<p>It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a poly-space lower bound (say for multi tape TM), i.e. is there a space-hard problem in $\mathbf{P}$?</p>

<p>Similarly, is there a problem in $\mathbf{P}$ with a good non-deterministic time lower bound? Is there a problem in $\mathbf{NP}$ with poly-space lower bound? ...</p>

CC BY-SA 3.0
2014-02-17T12:41:28.330Z
I don't understand your question. Can you please state it more  rigorously  mathematically?
Kaveh
CC BY-SA 3.0
2014-02-18T12:15:55.610Z
Denis gave a good answer for the first and third question and I rephrased the second question for the clarity. For the second question, a good lower bound would be e.g. $\Omega(n^2)$.
David G
CC BY-SA 3.0
2014-02-18T12:20:24.257Z
Sorry, but I am still not sure what you are asking. You are using terms that I don't think are standard. What do you mean by "poly-space lower bound"? Are you asking if there is a problem in $P-DSpace(n^k)$ for some $k\geq 1$? What do you mean by "space-hard"? Do you mean PSpace-hard? And in the nondeterministic case, are you asking for a problem in $P-NTime(n^k)$ for some $k\geq 1$?
Kaveh
CC BY-SA 3.0
2014-02-18T12:29:36.550Z
If a problem is outside $\mathbf{DSpace}(n^k)$, for some $k≥1$, then it has a "poly-space lower bound", just as you said. I called the problems outside $\mathbf{DSpace}(n^k)$, for some $k\geq 1$, space-hard.
David G
<cc.complexity-theory><complexity-classes>
Problems of similar complexity for different measures
David G
# Problems of similar complexity for different measures

(Asked by: username_0 on 2014-02-17)

It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a poly-space lower bound (say for multi tape TM), i.e. is there a space-hard problem in $\mathbf{P}$?

Similarly, is there a problem in $\mathbf{P}$ with a good non-deterministic time lower bound? Is there a problem in $\mathbf{NP}$ with poly-space lower bound? ...

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: I don't understand your question. Can you please state it more  rigorously  mathematically?  
> **username_0**: username_2 gave a good answer for the first and third question and I rephrased the second question for the clarity. For the second question, a good lower bound would be e.g. $\Omega(n^2)$.  
> **username_1**: Sorry, but I am still not sure what you are asking. You are using terms that I don't think are standard. What do you mean by "poly-space lower bound"? Are you asking if there is a problem in $P-DSpace(n^k)$ for some $k\geq 1$? What do you mean by "space-hard"? Do you mean PSpace-hard? And in the nondeterministic case, are you asking for a problem in $P-NTime(n^k)$ for some $k\geq 1$?  
> **username_0**: If a problem is outside $\mathbf{DSpace}(n^k)$, for some $k≥1$, then it has a "poly-space lower bound", just as you said. I called the problems outside $\mathbf{DSpace}(n^k)$, for some $k\geq 1$, space-hard.  

---

## 1 answers

### Answer by username_2 on 2014-02-17. Score: 5 | Accepted answer

The answer to the first question is that we don't know, because we don't know whether $\mathbf P=\mathbf L$, so it could be that all $\mathbf P$ problems use only logarithmic space.

For the second one, most reasonable problems need at least linear time to read the input, even for non-deterministic machines, so it does not make a lot of sense to say "polynomial non-deterministic lower bound", or you need to make your question more precise.

Finally, the last question is like the first one: it could be that $\mathbf{NL}=\mathbf{NP}$, in which case such a problem wouldn't exist, we don't know...

> **Comments:**
> **username_0**: Thanks for the answer! I am a bit ashamed that I missed the open question P=L.  
> **username_0**: I also changed the second question a bit to avoid linear time lower bounds. But I guess that the answer to all my questions is "we do not know".  
> **username_3**: having said that, there are problems in P with (weak) super linear *time* lower bounds.  

---

