NP reducibility proof steps

Question

Can someone help me to verify my understanding of reducible NP problems? Look at this tree:

The root shows the most complex NP complete problem. So, given that circuit-sat is NP complete, by this theorem, it can be reduced to any one of the NP problems that are its leaves. So, Circuitsat is NP complete by this theorem (but idk why it says that L can be reduced to L' if L' is NP complete and would be more complex than L). If you were trying to show that vertex cover could be reduced to NP complete, you would show that there is some function (that employs an algorithm) that runs in polynomial time that transforms all the inputs of the more complex problem into inputs for the less complex problem. So this demonstrates that an NP problem is reducible to another NP problem. (idk why, but this shows that all problems in the tree I gave are NP complete). Additionally, I want to add that for reductions where X is polynomial time reducible to Y, that X is always the more complex problem. I talked to a TA who said the ordering doesn't matter; was he just incorrect or is there a nuance to what he said?

Answer 1

I think you've got things mixed up. Usually, we show circuit-SAT is NP complete directly, by reducing an arbitrary NP problem to it (this is the Cook-Levin theorem). Then, what this tree presumably illustrates is that Circuit-SAT can be reduced to SAT, so by the theorem (and the fact that SAT is NP), SAT is also NP-complete. And then we can reduce SAT to 3CNF-SAT, showing the latter is NP-complete, and so on, showing all the problems in the tree are NP-complete.

But this is just one convenient way of doing it. Any NP-complete problem has the property that all NP problems reduce to it (by definition), so since they're all NP (also by definition), they all reduce to one another. So, in theory, we could have proved Subset Sum is NP complete directly, then reduced it to all the others along some tree. Perhaps this is what your TA meant by "the order doesn't matter". Note in particular, this means that, at least at this coarse-grained level of polynomial time mapping reductions, there is no "most complex" NP-complete problem... they are all inter-reducible. There may be other senses in which we can assign them relative complexity, though.