Complexity of calculating, complexity of things
To follow up on this post: we had a complexity axiom that told us something about topology, apparently. I would like to elaborate on this and explain what it's "really" (in my opinion) doing. The topological statement is also, inherently, a complexity question. It's just that, instead of being couched in the usual langauge of minimum complexity of a Turing machine calculating something, it's a statement about the minimum complexity writing down a description of some knot. This is more natural than you might think!
Morally, it's very analogous to the "theorem" that the Hajos number of a graph can be exponentially big (under the complexity "axiom" that coNP != NP). The Hajos number is one way of measuring how hard to build a graph from simpler graphs. You start with complete graphs K_n. Of the steps you're allowed to use, none of them can ever decrease the chromatic number of the graph. It's also been shown you can always build a graph in this way where the chromatic number never changes. That is, the Hajos number sort of asks: how many steps do you need to build this graph, in a way where each step leaves the chromatic number unchanged?
So, if you have a graph that is "simple" by measure of the Hajos number (at most polynomially long), then it means that there's a short proof (a polynomial length sequence of steps to construct it) that it has a certain chromatic number k. This means there is no coloring of k, which is coNP-hard. So you would have a NP way to check coNP questions.
Generally you could imagine other versions of this... like, #3COL is the counting problem that asks how many 3-colorings there are of a graph. This is #P-hard, so if P^{#P} != NP, then this shouldn't be in NP. If I gave you a set of allowed "moves" to do on a graph that always change #3COL in simple ways (e.g. "I'm going to add a degree-one edge, which doubles the number" or "This graph has two distinct components, so I can reduce to counting on each component separately and then multiply"). Then I define the complexity of a graph com(G) as the number of steps it takes to reduce it to the empty graph. P^{#P} != NP would imply that com(G) must grow superpolynomially in the size of G.
I could generalize that somewhat. Instead of reducing to just trivial graphs, I could say, I want to reduce to graphs of small treewidth. This is 'enough' because on graphs of small treewidth, #3COL is easy to compute. Maybe the steps I'm allowed to use won't reduce treewidth, but I'm just sort of asking: can I take a graph and somehow canonicalize it to a graph of small twin-width that has the same number of colorings?
So if I start a graph G and can reach a graph H by applying these moves, then I say that G and H are "equivalent" within this space of moves. The distance(G,H) is how many moves you need to do this. I would be able to solve #3COL quickly on G if I can reduce it to H with only polynomially many moves, and then H has small treewidth. So then the theorem would be,
if there is a constant k such that (for all G, there is an equivalent H, with polynomial distance(G,H), and treewidth(H) <= k), then P^{#P} = NP.
so by flipping that around,
P^{#P} != NP --> for any k, there is some G, for which all equivalent H, either have treewidth(H) > k, or a superpolynomial distance(G,H).
This paper from Freedman is looking at a particularly nice, maybe natural example of this. Here instead of #3COL of a graph, the hard thing to calculate is the Jones polynomial of a knot. The allowed "steps" to change the knot are the standard Reidemeister moves together with Dehn surgery. Instead of talking about graphs of small treewidth, the measure of "complicated" knots is the girth of their plane diagram. The theorem there is
P^{#P} != NP --> for any b and b', there is some D, for which all equivalent D', either have girth(D') > b*log(size(D)) + b', or a superpolynomial distance(G,H).
