0
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't understand your question. Can you please state it more rigorously mathematically? $\endgroup$
    – Kaveh
    Commented Feb 17, 2014 at 12:41
  • $\begingroup$ 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)$. $\endgroup$
    – David G
    Commented Feb 18, 2014 at 12:15
  • $\begingroup$ 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$? $\endgroup$
    – Kaveh
    Commented Feb 18, 2014 at 12:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – David G
    Commented Feb 18, 2014 at 12:29

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer! I am a bit ashamed that I missed the open question P=L. $\endgroup$
    – David G
    Commented Feb 18, 2014 at 12:00
  • $\begingroup$ 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". $\endgroup$
    – David G
    Commented Feb 18, 2014 at 12:04
  • 1
    $\begingroup$ having said that, there are problems in P with (weak) super linear time lower bounds. $\endgroup$
    – Suresh Venkat
    Commented Feb 18, 2014 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.