我们表明,对于具有保守Maltsev多态性的每个有限结构B,B的约束满意度问题可以通过对称线性Z2-Datalog程序来解决,特别是在复杂度类奇偶校验-L中。 证明有两个步骤:我们首先为某个亚类呈现结果,其多态代数在遗传上是可不可还原的。 然后我们表明,我们类中的每一个其他结构都可以由子类中的一个结构原始地积极构建。 第二步需要不同的技术,并将呈现在配套文章中。
我们考虑了一个追逐逃避游戏,它描述了在无方向图的节点上熄灭燃烧火灾的过程。 我们表示ffn(G)所需的最小消防员人数,并为ffn(G)=1和ffn(G)=2的图形以及完整的二叉树的几乎锐利的界限提供表征。 我们表明,决定给定 G 和 m 的 ffn(G) ≤ m 是否为 NP-hard。 此外,我们表明最短的策略可以具有超多项式长度,从而打开问题是否在NP中。 基于一些合理的猜想,我们也证明这个决策问题对于具有边界树荫的图形来说既不是NP-hard,也不是恒定m。
我们表明,对于具有保守Maltsev多态性的每个有限结构B,B的约束满意度问题可以通过对称线性Z2-Datalog程序来解决,特别是在复杂度类奇偶校验-L中。 证明有两个步骤:我们首先为某个亚类呈现结果,其多态代数在遗传上是可不可还原的。 然后我们表明,我们类中的每一个其他结构都可以由子类中的一个结构原始地积极构建。 第二步需要不同的技术,并将呈现在配套文章中。
我们表明,线性编程和线性二价方程组合的提升和项目层次结构并没有解决近似的图形着色。 证明是基于组合张量理论。
布尔的满意度(SAT)问题表示为数学公式。 本文为这些SAT问题提供了矩阵表示。 它显示了如何使用这个矩阵表示来获得全套有效的满足变量赋值。 它证明这是给定问题的答案集,并且相对于矩阵的大小呈指数级。 它提出了一个简单的算法,它利用每个子句的反向来为矩阵找到一个交叉点。 这给出了一个令人满意的变量赋值。
我们提出了一个紧凑的量子电路,用于考虑一大类整数,包括一些经典硬度预计相当于RSA(但不包括RSA整数本身)。 最值得注意的是,我们用log Q = Θ(n^a)在空间和深度亚线性的 n(特别是 Õ( log Q))中用 Õ(n) 量子门,在空间和深度亚线性中为 n(特别是 Õ(log Q)) 的 n 位整数;对于这些整数,没有已知的经典算法利用相对较小的 Q 大小来比通用因子算法以相对快的速度运行。 据我们所知,这是第一个为经典硬因子问题实现亚线性量子比特计数的多项式时间电路。 因此,我们认为,考虑这些数字有可能成为目前已知的最具体的可经典可验证的量子性证明。 我们的电路建立在Li,Peng,Du和Sutter发现的无平方分解的量子算法(2012年自然科学报告)上,该算法依赖于计算量子叠加中的Jacobi符号。 我们贡献的技术核心是一种新的空间效率量子算法,用于计算A mod B的Jacobi符号,在B是经典且比A大得多的政权中。 我们用于计算Jacobi符号的电路概括为相关问题,例如计算最大的通用除数和模块化反面,因此可能是独立的兴趣。
通过 MAXSAT 问题,我们得到了一组 m 变量的 V 和 n 个子句的集合 C over V。 我们将寻求一个真理的任务,以最大限度地提高满意条款的数量。 这个问题是NP-complete,即使是其限制版本,2-MAXSAT问题,每个子句最多包含2个字面量。 在本文中,我们讨论了一个高效的算法来解决这个问题。 它最糟糕的时间复杂度受O(n^2m^4)的限制。 这表明2-MAXSAT问题可以在多项式时间解决。 因此,本文实际上提供了P = NP的证明。
我们研究撞击集发生器的算术复杂性,这是用于多项式身份测试问题的去随机化对象。 我们提供新的明确结构的命中集生成器,其输出在VNC^0中可计算,即可以通过恒定大小的算术公式计算。 无条件,我们构建一个 VNC^0 可计算发电机,它撞击恒定深度和多项式大小的算术电路。 我们还给出了条件结构,在强而合理的硬度假设下,分别击中算术公式和多项式尺寸的算术分支程序。 VNC^0-computable generator 作为我们结构的必然结果,我们为Grochow和Pitassi的几何理想证明系统的子系统提供了下限。 这种发电机的构造隐含在Kayal先前在下界的工作中,以湮灭多项式的程度。 我们的主要贡献是结构,其正确性依赖于电路复杂性下界而不是下界。
我们考虑了一个追逐逃避游戏,它描述了在无方向图的节点上熄灭燃烧火灾的过程。 我们表示ffn(G)所需的最小消防员人数,并为ffn(G)=1和ffn(G)=2的图形以及完整的二叉树的几乎锐利的界限提供表征。 我们表明,决定给定 G 和 m 的 ffn(G) ≤ m 是否为 NP-hard。 此外,我们表明最短的策略可以具有超多项式长度,从而打开问题是否在NP中。 基于一些合理的猜想,我们也证明这个决策问题对于具有边界树荫的图形来说既不是NP-hard,也不是恒定m。
对称性在布尔函数 f:{0,1}^n →{0,1}1} 中的作用在复杂性理论中得到了广泛的研究。 例如,对称函数,即S_n作用下不变的函数,是研究布尔函数中重要的一类函数。 函数 f:{0,1}^n →{0,1} 称为过渡性(或弱对称),如果存在 S_n 的转向组 G,因此 f 在 G 的作用下是不变的 - 即使 f 的输入位根据一些排列 σ∈ G 被移动后,函数值也保持不变。 在过去的几十年里,了解过渡功能的各种复杂性测量一直是一个丰富的研究领域。 在这项工作中,我们根据几个组合措施研究过渡功能。 我们研究各种措施对用于过渡功能的最大分离。 这种对一般布尔功能的研究已经进行了多年。 广为人知的一般布尔函数的结果由Aaronson等人(STOC,2021)很好地编译。 一对组合措施之间的分离是通过构建显示分离的有趣函数来显示的。 但许多著名的分离结果是通过函数的构建(如来自Ambinis等人的“指针函数”)。 (JACM,2017)和“作弊表函数”Aaronson等人。 ( STAC ,2016年)不是过渡性的。 因此,我们在过渡函数的对对之间没有这种分离。 在本文中,我们展示了如何修改其中一些函数来构建过渡函数,这些函数在成对的组合度量之间表现出类似的分离。
在局部差分隐私下计算子图或图谱的问题是一个重要的挑战,引起了研究人员的高度重视。 然而,现有的大部分工作都集中在三角形或k星等小图形上。 在本文中,我们提出了一个非交互式的本地差分私有算法,能够计算任何大小的k的图形。 当 n 是输入图中的节点数时,我们显示我们算法的预期 l_2 误差为 O(n^k - 1)。 此外,我们证明存在一类大小为 k 的输入图和图,任何非交互式计数算法都会产生预期的 l_2 误差 Ω(n^k - 1),从而证明了我们结果的最优性。 此外,我们确定对于某些输入图和图,任何局部微分私有算法都必须具有预期的 l_2 误差 Ω(n^k - 1.5)。 我们的实验结果表明,我们的算法比经典的随机响应方法更准确。
在这项工作中,我们研究具有多样性意识的聚类问题,其中数据点与多个属性相关联,导致交叉组。 聚类解决方案需要确保每个组中选定的聚类中心的数量应位于每个组的下限和上限阈值定义的范围内,同时最小化聚类目标,可以是k-median,k-means或k-suplier。 我们研究拟议问题的计算复杂性,提供对其NP硬度,多项式时间不近似和固定参数难耐症的见解。 我们分别介绍了近似值算法,其近似值比为 1+ 2/e + ε≈ 1.736、1+8/e + ε≈ 3.943 和 5 分别用于 diversity-aware k-median、 diversity-aware k-means 和 diversity-aware k-suplier。 假设Gap-ETH,对于多样性感知k-median和多样性感知k-means的问题,近似比率是紧密的。 我们的结果意味着与不相邻组( fair k-median, fair k-means 和 fair k-suplier) 的相应变体具有相同的近似因子,具有下限要求。
Aaronson,Bouland,Fitzsimons和Lee介绍了复杂性类PDQP(原始标记naCQP),BQP的改变增强了BQP,能够获得非崩溃测量的能力,量子态样本而不会崩溃它们。 虽然PDQP包含SZK,但它仍然需要Ω(N^1/4)查询来解决非结构化搜索。 我们制定了PDQP的替代等效定义,我们用它来证明正加权对手低边界方法,在查询和非崩溃测量之间建立多个更严格的边界和权衡。 我们利用该技术来分析研究良好的多数和元素独特性问题的查询复杂性。 此外,我们证明一个紧密 Θ(N^1/3) 的搜索绑定。 此外,我们使用下限来探索查询限制下的PDQP,发现当与非自适应查询相结合时,我们会在几种情况下限制加速。
在这里,我们重新审视了获取Forrelation[Aaronson等人,2015]值的量子算法,以评估布尔函数的一些着名的加密显著光谱,即Walsh光谱,交叉相关性光谱和自关联谱。 我们介绍现有的2倍的Forrelation配方与基于弯曲的二元性承诺问题作为理想的实例化。 接下来我们通过两种方法专注于3倍版本。 首先,我们明智地将一些函数设置在3倍的Forrelation中,以便给定神谕访问,可以从f的Walsh Spectrum进行采样。 使用它,我们获得的结果比我们从Deutsch-Jozsa算法获得的结果要高,反过来,它在弹性检查中也有影响。 此外,我们使用类似的想法来获得一种技术,在任何一点上估计交叉相关性(从而自动关联)值,改进了现有的算法。 最后,我们用线性函数的叠加来调整量子算法,以获得交叉相关性采样技术。 据我们所知,这是第一个具有恒定查询复杂性的交叉相关性采样算法。 这也提供了一个策略,检查两个函数是否不相关的度m。 我们使用 Dicke 状态进一步修改此功能,以便时间复杂度降低,特别是对于 m 的常量值。
在一篇参数化复杂度理论的基本论文中,马克思[ToC '10]构建了最大3度的k-vertex图H,使得n^o(k/log k)用于检测彩色H子图的时间算法将驳斥指数-时间假说(ETH)。 这一结果被广泛用于获得ETH下参数化问题的几乎紧密的条件下限。 我们为这一结果提供了新的、完全独立的证明,进一步简化了 Karthik 等人最近的工作。 [SOSA 2024]。 在我们的证明中,我们引入了一个独立感兴趣的新图形参数,即联动容量γ(H),并显示检测时间 n^o(γ(H)) 中的五颜六色的H子图会反驳ETH。 然后,我们使用归功于Beneš的通信网络的简单构建,以获得最大度3和联动容量Ω(k / log k)的k-vertex图形,避免了涉及扩展图的参数,这是以前的论文中要求的。 我们还表明,树幅t的每个图H都有链接能力Ω(t / log t),从而以简化的证明恢复了马克思[ToC '10]所显示的更强的结果。 此外,我们通过分析其联动能力,在某些类型的模式的彩色子图检测的复杂性上获得新的紧密下限:我们证明,Ω(k^β)的多项式平均度Ω(k^β)的k-vertex图形具有连接能力Θ(k),这意味着找到此类模式H的紧密下限。 作为这些结果的应用,我们还获得了严格的下限,用于计算具有固定属性Φ的小诱导子图,从[Roth et al., FOCS 2020]提高边界。
有序的二进制决策图(OBDD)是一个定向的丙烯图,代表布尔函数。 OBDDs也被称为复杂性理论领域遗忘的读一次分支程序的特殊情况。 由于OBDD作为数据结构具有许多不错的特性,因此在理论和实践领域(如VLSI设计,正式验证,机器学习和组合问题)已经进行了数十年的广泛研究。 可以说,使用OBDDs最关键的问题是,当它们表示相同的函数时,它们的大小可能会成倍地变化,这取决于它们的变量排序(即变量要读取的顺序)。 事实上,很难找到一个最优的变量排序,从而最小化给定函数的 OBDD。 因此,许多研究都寻求启发式来寻找最佳变量排序。 从实践和理论的角度来看,寻求与琐碎的蛮力算法相比,以较低的(指数)时间复杂性输出最佳解决方案的算法也很重要。 Friedman和Supowit提供了一个具有时间/空间复杂性O^∗(3^n)的聪明的确定性算法,其中n是函数的变量数,这比琐碎的蛮力绑定O^∗(n!2^n)要好得多。 本文表明,量子计算机可以通过证明量子算法的存在,该量子算法与O^∗(2.77286^n)时间和空间中的相应变量排序一起产生最小OBDD,并且误差呈指数小。 此外,该算法可以适应构建其他最小决策图,例如零压制的BDD,它提供了稀疏集的紧凑表示,并且通常用于离散优化和枚举领域。
在量子计算机上成倍小的空间中模拟大型经典系统引起了人们的关注。 先前的工作表明,量子算法在模拟具有长距离相互作用的经典动力学方面提供了对任何经典算法的指数加速。 然而,许多现实世界的经典系统,如偏微分方程产生的系统,只表现出局部相互作用。 问题仍然是量子算法在这种情况下是否仍然可以提供指数加速。 在这项工作中,我们彻底表征了量子算法的计算复杂性,用于模拟这种几何局部系统。 首先,我们去量化量子算法,用于模拟此类系统的短时间(多项式)动力学。 这意味着模拟这种动力学的问题不会产生任何指数级的量子优势。 其次,我们证明短时间动力学的量子算法与多项式概率经典计算具有相同的计算复杂性。 第三,我们表明,长期(指数时间)动力学的量子算法的计算复杂性是由指数-时间和多项式空间量子计算捕获的。 这表明在将计算限制在多项式空间时具有超多项式时间优势,或者以其他方式提供指数空间优势。 这项工作为偏微分方程所支配的经典动力学的复杂性提供了新的见解,为在实际问题中实现量子优势提供了途径。
布尔的可满足性问题(SAT)是一个众所周知的单调推理的例子,由于快速解决者而产生了强烈的实际兴趣,并辅之以严格的细粒度复杂性结果。 然而,对于非符号推理,例如,演绎推理,在经典复杂性理论之外,相对鲜为人知。 在本文中,我们迈出了弥合单调和非单调推理之间差距的第一步,分析了看似被忽视但自然的参数n:知识库中的变量数量下棘手的绑架问题的复杂性。 我们获得了几个积极的结果以及NP和 Σ^P_2- 共NP-完整的片段,这意味着第一个例子,即 Σ^P_2 彻底搜索一个完整的问题(据我们所知)。 我们用下界来补充这一点,并且许多片段排除了(强)指数时间假设下的改进。
多代理路径查找 (MAPF) 问题要求在图上找到一组路径,这样当同步跟踪这些路径时,代理永远不会遇到冲突。 在最广泛的MAPF配方中,所谓的经典MAPF,代理大小被忽视,并且考虑了两种类型的冲突:占据相同的顶点或同时使用相同的边缘。 同时,在许多实际应用中,例如机器人技术,考虑到代理商的尺寸,对于确保MAPF解决方案能够安全执行至关重要。 引入大型代理会产生一种额外的冲突,当一个代理跟随一个边缘,其身体与另一个实际上不使用相同边缘的代理的身体重叠时(例如,仍然停留在图形的某些不同顶点)。 到目前为止,尚不清楚在规划时考虑此类冲突时,问题会有多困难。 具体来说,众所周知,在无方向图上的Classical MAPF问题可以在多项式时间解决,但是没有提供完整的多项式时间算法来解决具有大型代理的MAPF。 在本文中,我们首次确定后一个问题是NP-hard,因此,如果 P!=NP 没有多项式算法可以,不幸的是,可以提出。 我们的证明是基于在现场技术中普遍存在的,即将开创性的3SAT问题(已知是NP完全问题)减少到手头问题。 特别是,对于任意的3SAT公式,我们在程序上构建了一个带有特定起点和目标顶点的专用图,并表明给定的3SAT公式是可满足的iff,相应的路径查找实例有一个解决方案。
最近的作品通过检查具有分层结构的功能或数据来探索深度学习的成功。 为了研究具有分层结构的功能的学习复杂性,我们研究了具有独立输入的树层次结构函数的噪声稳定性。 我们表明,如果层次结构中的每个函数都离线性远,噪声稳定性在层次结构的深度就呈指数级小。 我们的成果有学习的即时应用。 在使用Dachman-Soled,Feldman,Tan,Wan和Wimmer(2014)的结果的布尔设置中,我们的结果为基于分层函数的学习类提供了统计查询超多项式下限。 同样,使用Diakonikolas,Kane,Pittas和Zarifis(2021)的结果,我们的结果为高斯测量下的SQ学习提供了超多项式下界。 使用Abbe,Bengio,Cornacchiam,Kleinberg,Lotfi,Raghu和Zhang(2022)的结果,我们的结果意味着在完全连接的神经网络上学习梯度下降的分层函数的样本复杂性下限。
需求可拆分的资源分配问题通常使用不同的解决方案方法来解决,而不是其不可分割的等价物。 虽然可拆分问题实例可以更容易地实现两者(例如,它们可能只是对应于离散问题的线性松弛),但存在许多问题,包括路由问题,而路由问题则相反。 也就是说,解决未分裂问题的技术已经成熟,但可拆分的对应物则不是。 对于这些问题,最近显示潜力的一个策略是使用先验拆分规则,其中每个客户的需求提前拆分成更小的部分,这使得人们能够简单地将拆分问题作为不可拆分版本的实例来解决。 需要考虑的一个重要因素是这种分裂后产生的碎片数量。 大量的碎片将允许更多的分裂模式实现,但将导致更大的问题实例。 在本文中,我们引入了一个分割规则,将碎片数量最小化,但受到所有需求拆分模式仍然可行的约束。 车辆路由问题的基准实例和时间窗口扩展的计算实验表明,我们提议的拆分规则的解决方案质量可以匹配现有方法的性能。
在本文中，我们证明了在证明系统 Res(lin_𝔽_q) 中，对于不可满足的向量子集和实例 a_1 x_1 + … + a_n x_n = b 的驳斥大小的下界，其中 char(𝔽_q)≥ 5。我们将具有列 (a_1, …, a_n) 的矩阵 A 的属性选择为定义良好纠错码 C_A := {x· A | x ∈𝔽_q^k}⊂𝔽_q^n 的生成矩阵，并证明了以下下界：1) 对于 Res(lin_𝔽_q) 的有向无环图 (dag) 片段。我们引入了子集和实例的 (s,r)-鲁棒性概念，这特别意味着 A 定义了一个最小距离 s≥ r 的纠错码。对于 (s,r)-鲁棒实例，我们证明了在 Res(lin_𝔽_q) 的有向无环图片段中，驳斥大小的下界为 2^Ω(r)。我们表明随机实例是 (n / 3, Ω((n/(q + 1)ln q))^1/3))-鲁棒的，并且可以使用代数几何码构造达到这些下界的特定示例。2) 对于树状 Res(lin_𝔽_q) 驳斥，我们证明了对于任何子集和实例，其大小下界为 2^Ω(((q+1)ln q)^-1/3d^1/5)，其中 d 是 C_A 的最小距离。