# Problems of similar complexity for different measures

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? ...

• I don't understand your question. Can you please state it more rigorously mathematically? – Kaveh Feb 17 '14 at 12:41
• 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 Feb 18 '14 at 12:15
• 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 Feb 18 '14 at 12:20
• 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 Feb 18 '14 at 12:29

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.
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...