Welcome to the resource topic for 2023/1832
Title:
A Note On the Universality of Black-box MKtP Solvers
Authors: Noam Mazor, Rafael Pass
Abstract:The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta complexity problems relate to one another, and to the task of function inversion.
In this note, we present resolutions to some of these questions with respect to the \emph{black-box} analog of these problems. In more detail, let MK^t_MP[s] denote the language consisting of strings x with K_{M}^t(x) < s(|x|), where K_M^t(x) denotes the t-bounded Kolmogorov complexity of x with M as the underlying (Universal) Turing machine, and let search-MK^t_MP[s] denote the search version of the same problem.
We show that if there for every Universal Turing machine U there exists a 2^{\alpha n}poly(n)-size U-oracle aided circuit deciding MK^t_UP [n-O(1)], then for every function s, and every not necessarily universal Turing machine M, there exists a 2^{\alpha s(n)}poly(n) size M-oracle aided circuit solving search-MK^t_MP[s(n)]; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating MK^t_MP with particular choices of (a non universal) TMs M (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion).
As a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding MK^t_UP[n-O(1)] for any universal TM U; that is, also in the worst-case regime, black-box function inversion is ``equivalent" to black-box deciding MKtUP.
ePrint: https://eprint.iacr.org/2023/1832
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .