If P = NP, do these NP-complete problems reduce to these specific easier versions?

Question

I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al.

Chapter 8 has the table below and I am wondering:

1. if $P = NP$ does each of the problems on the left reduce to the easy problem (in $P$)in its immediate right?

2. The book mentions that

the problems on the left are all difficult for the same reason! At their core, they are all the same problem, just in different disguises! They are all equivalent:

does this imply that the problems on the right are also the same problem but in different guises? Can they be solved the same way like solving SAT for NP-complete problems? If so, what's the equivalent of SAT for problems in $P$ ? I understand that SAT reduces to all problems in $NP$ but is there a problem in $P$ that sort of holds the same position as SAT in $NP$?

3. Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if $P=NP$? This was asked in a true-false question and couldn't get it right. The options were: true, false, true if $P=NP$, true $P \neq NP$. In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

Answer 1

1. if P=NP does each of the problems on the left reduce to the easy problem (in P) in its immediate right?

If P=NP then every problem on the left is in P, and trivially polynomially equivalent to every problem on the right. There is no special formal correspondence between the pairs of problems in each row of the table. The authors probably chose informally similar problems for the left and right columns to make the point that a seemingly small change to an efficiently solvable problem can make it NP-complete, and vice versa.

2. The book mentions that "the problems on the left are all difficult for the same reason! At their core, they are all the same problem [...]" does this imply that the problems on the right are also the same problem but in different guises?

I would say no. NP-complete problems are all polynomially equivalent, meaning that given an oracle that computes the answer to one in polynomial time, you can answer any other in polynomial time. Because there is no polynomial-time algorithm known for any of them without the oracle, the amount of time you save by using the oracle dominates the total time for large enough problem sizes, so you can argue that the oracle is doing the heavy lifting. This applies to any pair of NP-complete problems, so they all contain models of important parts of each other in a nontrivial way – somewhat like different computational models can simulate each other

Problems in P are trivially polynomially equivalent: given an oracle for one, you can solve any other one in the usual way and ignore the oracle. But you can't argue from this equivalence that the oracle played any role. P contains many problems like "is the input nonempty?" that are of no use in solving any other problem and clearly don't "contain" interesting problems like MST.

If it turns out that P=NP then it becomes much harder, perhaps impossible, to formalize the relationship between the problems that were formerly considered NP-complete; the apparent similarity between them might just be an illusion.

3. Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if P=NP?

In the trivial sense, yes. If P≠NP, then it doesn't (if it did, that would give you a polynomial-time algorithm for Hamiltonian path).

In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

It might be reducible to some other spanning-tree algorithm, but that algorithm would have to be flexible enough that you could encode the Hamiltonian-path constraint somehow in the input.