3 ms·
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
by through_17 8y ago
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 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/ https://eccc.weizmann.ac.il//report/2011/031/ used computer search to show time-space tradeoffs for solving satisfiability.
- commandlinefan 8y agoThe 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 8y agoI 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.