4 ms·
Right conclusion, not the most direct argument. NP is a proper subset of EXPTIME; there are problems that must take exponential time to complete. Wikipedia says
by swolchok 16y ago
Right conclusion, not the most direct argument. NP is a proper subset of EXPTIME; there are problems that must take exponential time to complete. Wikipedia says that asking whether a Turing-machine halts in k steps is EXPTIME-complete (you have to execute k steps and the input is of size log k), but if you're willing to fudge a bit and consider function problems, listing all paths in a graph (or something even simpler, like "list all n-bit binary numbers")is going to take exponential time in the worst case.