论文标题
部分可观测时空混沌系统的无模型预测
Downward Self-Reducibility in TFNP
论文作者
论文摘要
储层计算是预测湍流的有力工具，其简单的架构具有处理大型系统的计算效率。然而，其实现通常需要完整的状态向量测量和系统非线性知识。我们使用非线性投影函数将系统测量扩展到高维空间，然后将其输入到储层中以获得预测。我们展示了这种储层计算网络在时空混沌系统上的应用，该系统模拟了湍流的若干特征。我们表明，使用径向基函数作为非线性投影器，即使只有部分观测并且不知道控制方程，也能稳健地捕捉复杂的系统非线性。最后，我们表明，当测量稀疏、不完整且带有噪声，甚至控制方程变得不准确时，我们的网络仍然可以产生相当准确的预测，从而为实际湍流系统的无模型预测铺平了道路。
A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in \textsc{PSPACE}. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution -- that is, the downward self-reducible problems in \textsc{TFNP}. We show that most natural $\PLS$-complete problems are downward self-reducible and any downward self-reducible problem in \textsc{TFNP} is contained in \textsc{PLS}. Furthermore, if the downward self-reducible problem is in \textsc{TFUP} (i.e. it has a unique solution), then it is actually contained in \textsc{UEOPL}, a subclass of \textsc{CLS}. This implies that if integer factoring is \emph{downward self-reducible} then it is in fact in \textsc{UEOPL}, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.
