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

  • $\begingroup$ I don't understand your question. Can you please state it more rigorously mathematically? $\endgroup$ – Kaveh Feb 17 '14 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 Feb 18 '14 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 Feb 18 '14 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 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.

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

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

Your Answer

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

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