patternMinor
Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$
Viewed 0 times
subseteqeachpspaceexamplesforproblemsclass
Problem
Given that $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$ and that it is commonly believed that all these inclusions are strict can you provide examples of problems that are believed to be in each class and not in the preceding ones?
To try to narrow the scope of the question, could you provide paradigmatic examples of problems that are believed to be in each class and why they are so?
To try to narrow the scope of the question, could you provide paradigmatic examples of problems that are believed to be in each class and why they are so?
Solution
You can take complete problems for each class. Think of a complete problem as one which represents the "hardness" of this class, then under the assumption that all of the inclusions are strict, such a problem can not reside in the weaker classes.
If $\mathsf{L\neq NL}$, any $\mathsf{NL}$ complete problem (under logspace reductions) cannot lie in $L$ . An example for such a problem is deciding whether there exists a path between two given vertices in a directed graph.
If $\mathsf{P\neq NL}$, no $P$ complete problem (under logspace reductions) can lie in $\mathsf{NL}$ . One example for such a problem is $CVAL$, given a circuit and input, does the circuit outputs $1$ on the given input. You can find other examples of $P$ complete problems here.
If $\mathsf{P\neq NP}$, then NP-complete problems (under polynomial time reductions) cannot lie in $\mathsf{P}$. You can find hundreds of examples here, traveling salesman, hamiltonian path, SAT, just pick your favorite.
You probably got the point by now, but i'll say it anyway. If $\mathsf{NP\neq PSPACE}$ then PSPACE complete problems (under polynomial time reductions) cannot lie in $\mathsf{NP}$. Famous complete problems here are TQBF (checking if a CNF formula with quantifiers is true), and games (do I have a winning strategy in a game from a given position, of course you need to be careful and precisely define the language). You can find more examples on Wiki.
These were the easy examples, there are problems who are not complete for their class, but still believed to be hard. For example, FACTORING (deciding whether an integer has a factor smaller than some given number), is believed to be NP-intermediate (not NP complete but still not in P). See this question from cstheory about NL-intermediate problems. PSPACE is very far away from NP, and examples are easier here. If the polynomial hierarchy does not collapse, then any complete problem for $\Sigma_i$ with $i\ge 2$ is in PSPACE but not in NP.
If $\mathsf{L\neq NL}$, any $\mathsf{NL}$ complete problem (under logspace reductions) cannot lie in $L$ . An example for such a problem is deciding whether there exists a path between two given vertices in a directed graph.
If $\mathsf{P\neq NL}$, no $P$ complete problem (under logspace reductions) can lie in $\mathsf{NL}$ . One example for such a problem is $CVAL$, given a circuit and input, does the circuit outputs $1$ on the given input. You can find other examples of $P$ complete problems here.
If $\mathsf{P\neq NP}$, then NP-complete problems (under polynomial time reductions) cannot lie in $\mathsf{P}$. You can find hundreds of examples here, traveling salesman, hamiltonian path, SAT, just pick your favorite.
You probably got the point by now, but i'll say it anyway. If $\mathsf{NP\neq PSPACE}$ then PSPACE complete problems (under polynomial time reductions) cannot lie in $\mathsf{NP}$. Famous complete problems here are TQBF (checking if a CNF formula with quantifiers is true), and games (do I have a winning strategy in a game from a given position, of course you need to be careful and precisely define the language). You can find more examples on Wiki.
These were the easy examples, there are problems who are not complete for their class, but still believed to be hard. For example, FACTORING (deciding whether an integer has a factor smaller than some given number), is believed to be NP-intermediate (not NP complete but still not in P). See this question from cstheory about NL-intermediate problems. PSPACE is very far away from NP, and examples are easier here. If the polynomial hierarchy does not collapse, then any complete problem for $\Sigma_i$ with $i\ge 2$ is in PSPACE but not in NP.
Context
StackExchange Computer Science Q#80225, answer score: 4
Revisions (0)
No revisions yet.