Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$ has any separation of classes or consequences?

My main question is can use this to show that $P \neq NP$ or some thing useful about $P \neq NP$ .

  • 1
    $\begingroup$ Why do we need the $\forall$ quantifier here? If $NP$ is not a subset of $TISP(poly(n),n)$ then your statement should also be true for all $k>1$? $\endgroup$ Commented Sep 3, 2018 at 7:35
  • $\begingroup$ yes, they are equals. I thought they are different. $\endgroup$ Commented Sep 3, 2018 at 7:52
  • $\begingroup$ I think they are equals to $NP \not \subset TISP(poly(n),n^{o(1)})$ too. $\endgroup$ Commented Sep 3, 2018 at 7:58

1 Answer 1


This would imply that L⊊NP since L⊆TISP(poly(n),n^k) k∈N

  • 3
    $\begingroup$ It also can show $SC \neq NP$ in similar way. $\endgroup$ Commented Sep 2, 2018 at 19:50

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.