ABSTRACT
Some natural problems do not seem to be complete for any of the complexity classes we have seen so far. For example, consider the problem of taking as input a graphG and a number k, and deciding whether k is exactly the length of the shortest traveling salesperson’s tour. This is clearly related to the Traveling Salesperson Problem (TSP) discussed in Chapter 23, but in contrast to TSP, it seems not to belong to NP, and also seems not to belong to co-NP.
