The problem is that topics like descriptive complexity theory are typically reserved for graduate level courses, and what the author has access to is basically a survey.
There are entire hierarchies that describe what is "NP-Harder" specifically the second level of the polynomial hierarchy, where NP == Σ_1^p
IMHO one of the most useful parts of the -complete concepts is as a meet-me where one can find possible reductions that may work in your use case, but even with just P and NP you can find useful mappings like:
P = FO(LFP)=FO(n^O(1))=SO(Horn)
NP = PCP(0,poly(n)) = PCP(log n, log n) = PCP(log n, 1) = Σ^1 = SO(∃)
The arithmetic and exponential hierarchies, which the author mentions are actually nearly just as big as a jump to HALT from the polynomial hierarchy.
The reason that PSPACE is invoked (class of decision problems solvable by a Turing machine in polynomial space).
Is because is because PSPACE contains PH, the Polynomial-Time Hierarchy[1] which is what the author seems to have been looking for. The PSPACE-complete problems[2] are also a great meet-me space for either looking for some special case reduction, or understanding that complexity from your preferred abstract model.
As space* is always more valuable then time, because you have to read, which takes time, it is common to have that transition. But then things get crazy too.
HALT and NP are very closely related in a practical method because of the Entscheidungsproblem, which is the decision problem issue.
But you have to think in the General case, not a restricted problem.
You can verify any NP problem in poly time, just as you can tell that a machine halts, but you cannot pre-guess that.
A possibly useful lens for this is the generalization of HALT, Rice's Theorem[3]
> Rice's theorem states that all non-trivial semantic properties of programs are undecidable.
> Given a program P which takes a natural number n and returns a natural number P(n), the following questions are undecidable: * Does P terminate on a given n? (This is the halting problem.) * Does P terminate on 0? * Does P terminate on all n (i.e., is P total)? * Does P terminate and return 0 on every input? * Does P terminate and return 0 on some input? * Does P terminate and return the same value for all inputs? * Is P equivalent to a given program Q?
If you quit thinking about NP as something that can be brute forced, as yes NP can be simulated on a TM, and think about a decider program running and deciding without running the actual program this will help connect the dots.
Understanding that this decision has to happen without access to the semantic properties (runtime behavior) but only has access to the syntax of a program will open lots of concepts for you.
If moving past the oversimplified "survey" level explanations is of interest there are many resources, but here is one play list that some trusted people I know claimed was useful[4]. One of the more common descriptive complexity books is "Descriptive Complexity" by Neil Immerman, and even complexityzoo references[1] can help.
To be clear, I can understand why these oversimplified introduction explanations can be frustrating, and the curriculum could and should be improved.
[1]https://complexityzoo.net/Complexity_Zoo:P#ph [2]https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_prob... [3]https://en.m.wikipedia.org/wiki/Rice%27s_theorem [4]https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJO...