3 ms·
Yes, "NP-complete" is not correct on the author's part and neither is "NP-hard." "NP-hard" is the author's intent since the problem is solvable using a SAT solv
by pclmulqdq 2y ago
Yes, "NP-complete" is not correct on the author's part and neither is "NP-hard." "NP-hard" is the author's intent since the problem is solvable using a SAT solver but presumably has no polynomial algorithm (so it is harder than P but not as hard as NP), but NP-hardness actually requires the other direction to be true: for a problem to be NP-hard, an oracle for the problem needs to be able to solve everything in NP. NP-complete is a stricter condition that requires NP-hardness but also requires that the problem be in NP.
The author was missing the words "in NP" if they are talking about complexity.