[through_17]

Work on determining the relationships between complexity classes is mostly theoretical. I've outlined some of the frontier of this work regarding BPP in another comment. There are two broad classes of exceptions that I know of:

* Where this work intersects cryptography: in order for cryptosystems to be secure, we generally have to assume the difficulty of certain specific problems: a complexity assumption! Recent work (see here: https://eprint.iacr.org/2015/907) links these assumptions to how easy it is to notice they are false. Intuitively, the easier it is to notice that an assumption is false, the better it is for crypto. A false assumption can be detected and crypto based on this assumption abandoned.

* Where computer search is used to assist proofs: A line of work terminating in https://eccc.weizmann.ac.il//report/2011/031/ used computer search to show time-space tradeoffs for solving satisfiability.

[commandlinefan]

The linked article had an interesting way to phrase the traveling salesman problem. I've always heard it formulated as "given a set of cities and their distances, what is the shortest path that takes the salesman through each city", which wouldn't be NP by the definition given: if you were given the answer, you couldn't check it in polynomial time (unless you could solve the problem in polynomial time).

[dorgo]

I had a problem with this too. But actually the problem can be stated as an NP problem: Compute a round-trip shorter than k. If you have an algorithm to solve the NP version then you can use it to find the shortest round-trip by repeadly applying it to different k-parameters.