4 ms·
Actually, some undecidable problems are NP hard, like the halting problem. That is, a halting oracle gives a polynomial time algorithm for any NP problem.
by sobellian 8y ago
Actually, some undecidable problems are NP hard, like the halting problem. That is, a halting oracle gives a polynomial time algorithm for any NP problem.