Final answer:
The problems Partition, Subset sum, and 0-1 knapsack are not known to be solvable in deterministic polynomial time and are classified as NP-complete, while Minimum spanning tree can be solved in polynomial time.
Step-by-step explanation:
The question involves classifying problems according to their computational complexity, specifically whether they are known to be solvable in deterministic polynomial time. In computational complexity theory, problems that are not known to be solvable in deterministic polynomial time are typically considered NP (nondeterministic polynomial time) problems.
T for Partition.
F for Minimum spanning tree.
T for Subset sum.
T for 0-1 knapsack.
Each of the statements is evaluated as follows:
a) Partition is a problem that is known to be NP-complete, which means it is not known to be solvable in deterministic polynomial time. True (T).
b) Minimum spanning tree is a problem that can be solved in polynomial time using algorithms like Kruskal's or Prim's algorithm. False (F).
c) Subset sum is another NP-complete problem, so it is not known to be solvable in deterministic polynomial time. True (T).
d) 0-1 knapsack is also NP-complete and not known to be solvable in deterministic polynomial time. True (T).
When approaching these types of problems, problem-solving strategies such as identifying knowns and unknowns and checking if the answer is reasonable are applied. In complex cases, making a list of unknowns can help in structuring the approach to finding a solution.