Date: Fri, 26 Jul 2024 | Total: 3
This paper looks at the intersection of algorithmic information theory and physics, namely quantum mechanics, thermodynamics, and black holes. We discuss theorems which characterize the barrier between the quantum world and the classical realm. The notion of a "semi-classical subspace" is introduced. The No Synchronization Law is detailed, which says separate and isolated physical systems evolving over time cannot have thermodynamic algorithmic entropies that are in synch. We look at future work involving the Kolmogorov complexity of black holes.
We survey the complexity class $\exists \mathbb{R}$, which captures the complexity of deciding the existential theory of the reals. The class $\exists \mathbb{R}$ has roots in two different traditions, one based on the Blum-Shub-Smale model of real computation, and the other following work by Mn\"{e}v and Shor on the universality of realization spaces of oriented matroids. Over the years the number of problems for which $\exists \mathbb{R}$ rather than NP has turned out to be the proper way of measuring their complexity has grown, particularly in the fields of computational geometry, graph drawing, game theory, and some areas in logic and algebra. $\exists \mathbb{R}$ has also started appearing in the context of machine learning, Markov decision processes, and probabilistic reasoning. We have aimed at collecting a comprehensive compendium of problems complete and hard for $\exists \mathbb{R}$, as well as a long list of open problems. The compendium is presented in the third part of our survey; a tour through the compendium and the areas it touches on makes up the second part. The first part introduces the reader to the existential theory of the reals as a complexity class, discussing its history, motivation and prospects as well as some technical aspects.
We study the refutation complexity of graph isomorphism in the tree-like resolution calculus. Tor\'an and W\"orz (TOCL 2023) showed that there is a resolution refutation of narrow width $k$ for two graphs if and only if they can be distinguished in ($k+1$)-variable first-order logic (FO$^{k+1}$) and hence by a count-free variant of the $k$-dimensional Weisfeiler-Leman algorithm. While DAG-like narrow width $k$ resolution refutations have size at most $n^k$, tree-like refutations may be much larger. We show that there are graphs of order n, whose isomorphism can be refuted in narrow width $k$ but only in tree-like size $2^{\Omega(n^{k/2})}$. This is a supercritical trade-off where bounding one parameter (the narrow width) causes the other parameter (the size) to grow above its worst case. The size lower bound is super-exponential in the formula size and improves a related supercritical width versus tree-like size trade-off by Razborov (JACM 2016). To prove our result, we develop a new variant of the $k$-pebble EF-game for FO$^k$ to reason about tree-like refutation size in a similar way as the Prover-Delayer games in proof complexity. We analyze this game on a modified variant of the compressed CFI graphs introduced by Grohe, Lichter, Neuen, and Schweitzer (FOCS 2023). Using a recent improved robust compressed CFI construction of Janett, Nordstr\"om, and Pang (unpublished manuscript), we obtain a similar bound for width $k$ (instead of the stronger but less common narrow width) and make the result more robust.