We study how the complexity of modular circuits computing AND depends on the depth of the circuits and the prime factorization of the modulus they use. In particular our construction of subexponential circuits of depth 2 for AND helps us to classify (modulo Exponential Time Hypothesis) modular circuits with respect to the complexity of their satisfiability. We also study a precise correlation between this complexity and the sizes of modular circuits realizing AND. On the other hand showing that AND can be computed by a polynomial size probabilistic modular circuit of depth 2 (with O(log n) random bits) providing a probabilistic computational model that can not be derandomized. We apply our methods to determine (modulo ETH) the complexity of solving equations over groups of symmetries of regular polygons with an odd number of sides. These groups form a paradigm for some of the remaining cases in characterizing finite groups with respect to the complexity of their equation solving.
翻译：我们研究模块电路的复杂程度,并取决于电路的深度和它们所使用的模子的质因子化。特别是我们建造了深度2的亚爆炸性电路,帮助我们对模块电路的复杂性进行分类(模拟指数化时间假设),我们还研究这一复杂程度与模块电路的大小之间的确切关联。另一方面,我们显示,并且可以通过深度2的多数值概率组合性组合波段(与O(log n)随机比特一起)进行计算,以提供一个不可解析的概率计算模型。我们运用我们的方法确定(模型ETH)如何解决具有奇数面的常规多边形对称组合的方程式组合的复杂性。这些组合构成一些剩余案例的范例,这些案例在确定有限组的方程式的解析复杂性方面,对一些剩余案例进行了定性。
相关内容
微信扫码咨询专知VIP会员