For each of the following statements, determine whether it is true or false.
Minimumspanningtree ∈ NP
It is possible that NP ⊆ P
If you find a polynomial time algorithm which is always finds the optimal solution for some problem in NP then you have proven P = NP.
Some problems in P require exponential time to solve.
CLIQUE ≤p INDEPENDENTSET
QSAT ∈ PSPACE
The PLANNINGPROBLEM is known to be in PSPACE ∩ P
There does not exist a r-approximation algorithm for LOADBALANCING (on 2 machines) for any values of r<3.
There is a 2-approximation algorithm for METRICTSP.
