复杂度理论技术问询：为何部分NP-hard问题不属于NP

Great question—this is a super common confusion when you’re first wrapping your head around complexity theory. Let’s break down your three questions one by one:

1. Why do some NP-hard problems not belong to NP? #

First, let’s recap the key definitions to clear up the mix-up:

• NP: A problem is in NP if, for any "yes" instance, there exists a polynomial-length certificate (a guess at a solution) that can be verified in polynomial time by a deterministic Turing machine.
• NP-hard: A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.

The critical detail here is: NP-hardness doesn’t require the problem itself to meet NP’s verification rule. It only requires that all NP problems can be mapped to it. So if a problem is so hard that even checking a potential solution can’t be done in polynomial time (or it’s outright undecidable), it can still qualify as NP-hard as long as all NP problems reduce to it.

2. What does this situation mean? #

If an NP-hard problem isn’t in NP, it tells us this problem is strictly harder than all problems in NP.

For NP problems, even if we can’t find solutions quickly, we can at least verify if a given candidate solution is correct fast. But non-NP NP-hard problems don’t even have that luxury—either verifying a solution takes exponential time (or worse), or the problem is undecidable (no algorithm can solve it for all inputs, ever). These problems live in higher complexity classes like EXPTIME, PSPACE, or even the realm of unsolvable problems.

3. Can you give examples? #

Absolutely—here are two classic, easy-to-grasp ones:

• The Halting Problem: This is a famous undecidable problem (no algorithm can solve it for all possible inputs). It’s NP-hard because any NP problem can be reduced to it: take an NP problem instance and a candidate solution, build a Turing machine that verifies the solution. If the solution is valid, the machine halts; if not, it loops forever. Deciding whether this machine halts is exactly the Halting Problem, and it’s equivalent to answering whether the NP problem has a solution. Since the Halting Problem is undecidable, it can’t be in NP (all NP problems are decidable).
• Generalized Chess (n×n board): For a standard 8×8 chessboard, we can brute-force all possibilities, but for an arbitrary n×n board, the problem of determining if the first player has a winning strategy is EXPTIME-complete. It’s NP-hard because all NP problems reduce to it, but it’s not in NP—verifying a winning strategy would require checking every possible response from the opponent, which takes exponential time (way longer than polynomial).

内容的提问来源于stack exchange，提问作者Qwerto