论文标题
部分可观测时空混沌系统的无模型预测
Monotone Classes Beyond VNP
论文作者
论文摘要
在这项工作中，我们研究了VPSPACE的各种等效定义的自然单调类似物：一个经过良好研究的类（Poizat 2008，Koiran和Perifel 2009，Malod 2011，Mahajan和Rao 2013），被认为比VNP更大。我们观察到，这些单调类似物与非单调的类似物不同，并提出单调VPSPACE（MVPSPACE）定义为Poizat定义的单调类似物。有了这个定义，MVPSPACE证明比MVNP要指数强，并且还满足了其他类似物可能无法使用的几种理想的闭合属性。 我们的最初目标是了解透明多项式的单调复杂性，这一概念最近由Hrubeš和Yehudayoff（2021）引入。在这种情况下，我们表明，对于所有已知的VPSPACE的所有已知定义的单调类似物来说，大稀疏性的透明多项式很难，除非是由于Poizat引起的。
In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran and Perifel 2009, Malod 2011, Mahajan and Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone VPSPACE (mVPSPACE) to be defined as the monotone analogue of Poizat's definition. With this definition, mVPSPACE turns out to be exponentially stronger than mVNP and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš and Yehudayoff (2021). In that context, we show that transparent polynomials of large sparsity are hard for the monotone analogues of all the known definitions of VPSPACE, except for the one due to Poizat.
