[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhspace_time_hierachy.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Space Time Hierachy" source: https://www.jemoka.com/posts/kbhspace_time_hierachy/ --- I finally get to sound like I’m doing physics. \begin{equation} L \subseteq P \subseteq \text{PSPACE} \subseteq \text{EXP} \end{equation} by space hierarchy theorem and time hierarchy theorem, we have also that: \begin{equation} \text{P} \subset \text{EXP} \end{equation} and \begin{equation} L \subset\text{PSPACE} \end{equation} so we know that one of the subset things on top is a strict subset. There’s also a bridge \(P \subseteq \text{NP} \subseteq \text{PSPACE}\). \(L =^{?} P\) We believe that \(L \subset P\), but we can’t show this. \(L =^{?} \text{NP}\) We believe that \(L \subset \text{NP}\), but we can’t show this