>>11270879that's not what NP is idiot
NP is nondeterministic polynomial time, which essentially says "polynomial with an oracle." an easier characterization is that a search problem (i.e, one which searches for a solution to a given input problem) is NP if you can verify whether or not some possible output is actually a solution in polynomial time. so if you give me a traveling salesman graph and a budget, i can give you a traversal of your graph, and you are able to check whether or not my traversal is within the budget you set and whether it's a traversal at all (very easy in polynomial time)
there are plenty of non-polynomial problems that are also probably not NP, though there's a whole complexity hierarchy which hasn't been resolved yet. for example, satisfiability of quantifier boolean languages is probably not NP. if i give you a set of variable assignments for a quantifier boolean expression, it isn't easy to tell whether or not it's true.
