We determine which major $\TFNP$ classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of $\TFNP$ from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard $\TFNP$ subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: $\PPAD$, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of $\EoPL = \PPAD \cap \PLS$. In contrast, we show that $\UEoPL$ can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between $\EoPL$ and $\UEoPL$. This resolves the black-box hardness landscape of all major $\TFNP$ classes in Romantica. Finally, we initiate the study of separations between $\TFNP$ subclasses in Romantica: $\PWPP$ and $\PPA$ do not reduce to $\PLS$ under \emph{public-coin} reductions.
Emanuele Rimoldi, Riccardo Neumarker, Tomaso Poggio, Daniel Mitropolsky
原文摘要
Can a model learn by trying to fool another model? We show that it can. Inspired by the Turing Test and its recent generalization to arbitrary distinguishers, we introduce a domain-based teacher-Turing-Test, in which a stronger teacher model serves as both the target of imitation and the distinguisher, and a weaker student model is trained to make the teacher attribute responses to itself. We use this self-attribution (or fooling) probability as a reinforcement learning reward, without ever providing the student ground-truth answers, nor requiring the teacher to generate responses. We test our approach independently in four domains with verifiable answers: CommonsenseQA (reasoning), GSM8K (mathematics), KodCode (programming), and Spider (SQL), training a Qwen2.5-1.5B student/imitator model using DeepSeek V4 Flash as teacher/distinguisher. Beyond improving at passing the Turing Test, the student improves on independent, held-out evaluations in all domains and runs. To probe why being mistaken for the teacher can improve capability, our analyses reveal that self-attribution is associated with correctness -- substantially more than formatting changes -- and that it rewards partial correctness. Our results demonstrate a new, simple teacher-student training paradigm with a private and/or high-cost teacher. They also suggest that indistinguishability need not merely measure behavior -- it can also be a mechanism for learning.