logoalt Hacker News

Bankqtoday at 3:54 AM2 repliesview on HN

The approach reminds me of NP-Completeness (Computational harness vs mathematical-proving hardness). Am I over-simplifying?


Replies

logician127today at 5:32 AM

You’re right on the money. It’s intimately tied to computability theory, complexity theory’s more abstract sibling (I.e. the Halting problem and further Turing degrees). Both rely on the core techniques of diagonalization and reductions. The meat of it can differ a lot because estimating time bounds and determining logical equivalence rapidly become different problem spaces, so it’s not like results in one are really applicable to the other. But a researcher in one will usually be well versed in the other.

throwaway81523today at 8:48 AM

I would say that's on the wrong track and that "hard" is the wrong term for what reverse math (RM) tells you about problems. RM studies what axioms you need to prove a given theorem, but it's more like showing that "to pound in a nail of size X you need a hammer of size Y and a smaller hammer just can't do it", than saying pounding in the nail is difficult or complicated. Once you have the big enough hammer, pounding the nail can be very simple.