计算复杂性研究快报
用 AI 跟踪日新月异的计算复杂性领域进展
提高标准:古典和量子最短路径算法的渐近比较
单源最短路径(SSSP)问题是计算机科学的基石,具有广泛的应用,Dijkstra的算法长期以来一直是经典的基线。 虽然已经提出了各种量子算法,但它们的性能通常与这种几十年来的方法相吻合。 最近,Doutan等人引入了一种新的经典算法,其复杂性为O(m·(log n)^2/3,因此重塑了这种景观。 这一发展需要重新评估SSSP的量子优势叙事。 在本文中,我们根据这一新的经典前沿对现代量子和经典SSSP算法进行了系统的理论比较。 通过分析它们的理论成本函数,我们说明了它们的相对缩放如何比较图密度和路径长度不同的场景。 我们的分析提出了一个微妙的图景:复杂的量子算法,如Wesolowski和Piddock的量子算法,可以表现出更有利的渐近缩放,但只能在以短解决方案路径为特征的系统中。 相反,对于涉及长路径的问题,最先进的经典算法似乎保持缩放优势。 我们的工作为未来量子算法开发提供了最新的视角,并强调追求量子优势是一个动态的竞赛,其中经典的目标柱正在不断变化。
无线通信中多播光束成形的NP-完整性
在这项工作中,重新考虑无线通信中多播波束成形的经典问题。 现有的一项工作表明,多铸束形成问题是NP-hard。 在这个项目中,我们显示真实通道矩阵和波束器的相应决策问题是NP-complete。 最后,我们进行模拟,以揭示使用SAT/SMT求解器在各种设置中解决NP-complete波束成形问题的计算复杂性。
解决P的内在障碍=NP(2-SAT为平面,3-SAT为高维空)
我们提出了高效计算的拓扑障碍,通过比较2 SAT和3 SAT解决方案空间的几何形状来揭示。 将一组令人满意的赋值视为布尔超立方体中的立方体,我们证明每2个SAT实例都有可收缩的解决方案空间,拓扑扁平,所有较高的Betti数字bk等于0等于k大于或等于1,而随机和显式3个SAT家族都可以表现出指数级秒贝蒂数,对应于指数级许多独立的空隙。 这些空隙在标准的SAT削减下保存,如果不解决NP硬的子问题,它们就无法坍塌,使它们抵抗三大复杂性理论障碍,相对化,自然证明和代数。 我们在受限查询模型中建立指数时间下限,并在温和的信息理论或编码假设下将其扩展到更广泛的算法范式。 这种拓扑对比扁平,连接的景观在2 SAT与3 SAT中的缠结,高维空旷景观,提供了结构证据,表明P不等于NP,确定b2为计算硬度的范式无关的不变量。
相关分类
最新研究
最小稳定切割和树宽
图表的稳定或局部最优的切割是一种切割,其重量不能通过改变单个顶点的一侧而增加。 在本文中,我们研究了最小稳定切割,即找到最小重量的稳定切割的问题。 由于这个问题是NP-hard,我们在低树幅,低度或两者兼而有之的图形上研究其复杂性。 我们首先表明,这个问题在严格限制的树木上仍然很弱,所以仅靠树幅无法使它变得容易。 我们用伪多项式DP算法来匹配这种硬度,及时(Δ· W)^O(tw)n^O(1),其中tw是树宽,Δ最大度和W最大重量。 另一方面,边界Δ也是不够的,因为对于边界度的未加权图形来说,问题是NP-hard。 因此,我们通过 tw 和 Δ 参数化最小稳定切割,并获得在时间 2^O(Δ tw)(n+log W)^O(1) 中运行的 FPT 算法。 我们对加权问题的主要结果是提供一个还原,表明上述两种算法本质上都是最优的,即使我们用路径width替换树荫:如果存在在(nW)^o(pw)或2^o(Δ pw)(n+log W)^O(1)中运行的算法,那么ETH就是假的。 补充这一点,我们表明,然而,我们可以获得由树宽参数化的FPT近似方案,如果我们考虑几乎稳定的解决方案,即没有单个顶点可以单方面增加其事件切割边缘的重量超过1+ε倍。 受这些主要负面结果的激励,我们认为未加权的最小稳定切割。 在这里,我们的结果已经意味着一个更快的精确算法在时间 Δ^O(tw)n^O(1) 中运行。 我们表明,这也可能是本质上最优的:在n^o(pw)中运行的算法将与ETH相矛盾。
基于图形的NP问题确定性多项式算法
P = NP 问题询问是否可以在多项式时间 (NP) 中验证其解决方案的每个问题是否也可以以多项式时间 (P) 解决。 在本文中,我们提出了一个P = NP的证明,证明每个NP问题都可以在多项式时间确定性地解决。 我们引入了一种新的计算模型,可以模拟图灵机,并表明在这个框架内可以有效地模拟NP问题。 通过引入可行性图的概念,我们确保模拟可以在多项式时间进行,为解决P = NP问题提供了直接的路径。 我们的结果对密码学、优化和人工智能等领域具有重要意义,其中NP-complete问题起着核心作用。
再生Ulam-von Neumann算法:一个创新的马尔可夫链蒙特卡洛矩阵反转方法
本文介绍了经典Ulam-von Neumann Markov链Monte Carlo算法的再生变体,用于矩阵逆的近似值。 本文中介绍的算法称为再生Ulam-von Neumann算法,利用由非单数矩阵定义的经典,非截断的Neumann系列的再生结构,并通过再生量的无偏定估算器比率产生矩阵的估算器。 拟议算法的准确性取决于控制模拟马尔可夫转换总数单个参数,从而避免了在马尔可夫链复制总数与其长度之间平衡的挑战,就像经典的乌拉姆-冯诺依曼算法一样。 为了在计算再生变量时有效地利用马尔可夫链过渡样本,拟议的算法通过精心设计的更新方案自动量化每个马尔可夫过渡到所有再生量的贡献,该更新方案分别使用三个包含当前权重、总权重和再生周期计数的独立矩阵。 提供了对算法性能的概率分析,包括估计器的方差。 最后,数值实验验证了拟议方案的有效性。
通过线性排序的超图3色近似1合3 SAT是NP-hard
鉴于1-in-3 SAT的可满足实例,很难为它找到一个令人满意的分配,但有可能有效地找到一个解决方案,其基础是弱(不一定是布尔)谓词,而不是“1-in-3”。 有一个民间传说猜想,预测哪些选择较弱的谓词会导致可处理性,而任务仍然是艰难的。 一个特定的谓词,对应于线性排序3均匀超图的3色问题,在最近的几篇论文中被提及,作为证明这一猜想的进一步进展的障碍。 我们证明这个谓词的问题是NP-hard,正如猜想所预测的那样。 我们使用Promise CSP框架,其中通过代数方法进行复杂性分析,通过研究多态性的结构,多态性是当前问题的多态不变性。 多态性分析一般是一项高度非平凡的任务,最近发现了拓扑组合学,为这提供了一个有用的工具。 它使用的方式有两种:一种是基于Borsuk-Ulam定理的变化,另一个旨在对某些重新配置(homototy)进行多态性进行分类。 我们的证据,虽然在性质上是组合的,但表明我们的问题是拓扑学的两个用途背后的特征出现的第一个例子。 因此,它很可能有助于指导旨在分类Promise CSP的拓扑方法的进一步发展。 我们结果的一个简单后果是另一个特定的Promise CSP的硬度,Filaakovský等人最近通过采用多态性的深度拓扑分析来证明这一点。
关于Pathwidth的第一顺序逻辑再次重温
库尔特尔著名的定理指出,所有MSO可表达的属性都可以在边界树幅图的线性时间决定。 不幸的是,这个定理所隐含的隐藏常数是一个指数之塔,其高度随着公式中的每个量词交替而增加。 更毁灭性的是,在标准假设下,即使我们考虑在树上决定FO-可表达属性的更受限制的问题,这一点也无法改善。 在本文中,我们重新审视了这个研究良好的主题,并确定了一个自然的特殊案例,其中Courcelle定理的依赖性实际上可以得到改善。 具体来说,我们表明,如果输入图具有边界路径(而不是树宽),则所有 FO 表达属性都可以在输入公式上的基本依赖性来决定。 这是一个罕见的树宽和路径具有不同复杂性行为的例子。 我们的结果也与MSO逻辑在边界路径宽度的图形上形成鲜明对比,其中已知依赖性必须是非基本的,在标准假设下。 我们的工作建立在Gajarský和Hliněný的相应元定理之上,并概括为更受限制的有界树深度的图形类别。
TIME[t] ⊆ SPACE[O(√(t)] 通过树高度压缩
我们证明了一个用于确定性多带图图机器的平方根空间模拟,显示了TIME[[t] ⊆SPACE[O(√(t)]。 关键步骤是高度压缩定理,该定理均匀地(在日志空间中)重塑了规范的左深简洁计算树,用于块尊重运行到二进制树中,其沿着任何DFS路径的评估堆栈深度为O(log T)为T = ⌈ t/b ⌉,同时保留O(b)在叶子上的工作,O(1)在内部节点和边缘。接口。 证明使用中点(平衡)递归,一个通过O(log T)同时绑定活动接口的每路径电位,以及通过平衡的二进制组合器对多路的内侧封顶替换。 算法上,一个在恒定大小的字段上具有恒定度映射的代数回放引擎,以及无指针的DFS和无索引流,确保每个级别令牌的恒定大小,并消除宽计数器,产生块大小的加法权衡S(b)=O(b + log(t/b)) b≥ b_0与b_0 = Θ(log t),在b_0 = Θ(log t)空间;b_0阈值排除了退化的块,其中寻址划痕将主导窗口足迹。 结构是均匀的,相对化的,并且对标准模型选择很稳健。 后果包括用于size-s bound-fan-in电路的分支程序上限2^O(√(s),通过标准层次结构参数收紧SPACE[n]-complete问题的二次时间下界,以及O(√(t))-空间认证解释器;在显式局部假设下,框架扩展到几何d维模型。
约束重构与运动规划的复杂性分析
在约束环境中协调多个智能体的运动是机器人学、运动规划和调度领域的一个基本挑战。一个激励性的例子涉及n个机械臂，每个机械臂表示为一个线段。目标是将每个机械臂旋转到其垂直方向，一次一个（顺时针或逆时针），避免碰撞且不旋转任何机械臂超过一次。这个场景是更一般的k-Compatible Ordering问题的一个例子，其中n个智能体，每个能够执行k个状态改变动作，必须在编码为k对有向图集合𝒢的约束下转换到特定的目标状态。我们证明k-Compatible Ordering是𝖭𝖯-complete的，即使当𝒢是平面的、退化的或无环的。在积极方面，我们为诸如k = 1或𝒢具有有界树宽的情况提供了多项式时间算法。我们还引入了支持每个智能体多个状态改变动作的广义变体，扩展了我们框架的适用性。这些结果适用于约束环境中广泛的调度、重构和运动规划应用。
解决P的内在障碍=NP(2-SAT为平面,3-SAT为高维空)
我们提出了高效计算的拓扑障碍,通过比较2 SAT和3 SAT解决方案空间的几何形状来揭示。 将一组令人满意的赋值视为布尔超立方体中的立方体,我们证明每2个SAT实例都有可收缩的解决方案空间,拓扑扁平,所有较高的Betti数字bk等于0等于k大于或等于1,而随机和显式3个SAT家族都可以表现出指数级秒贝蒂数,对应于指数级许多独立的空隙。 这些空隙在标准的SAT削减下保存,如果不解决NP硬的子问题,它们就无法坍塌,使它们抵抗三大复杂性理论障碍,相对化,自然证明和代数。 我们在受限查询模型中建立指数时间下限,并在温和的信息理论或编码假设下将其扩展到更广泛的算法范式。 这种拓扑对比扁平,连接的景观在2 SAT与3 SAT中的缠结,高维空旷景观,提供了结构证据,表明P不等于NP,确定b2为计算硬度的范式无关的不变量。
多指标算法复杂性:超越渐近分析
传统的算法分析将所有基本操作都视为同样昂贵的操作,这掩盖了现代处理器上不同类型的计算之间的时间、能耗和成本的显著差异。 我们提出了一个加权操作复杂性模型,该模型为跨多个维度的不同指令类型分配了现实的成本值:计算工作、能源使用、碳足迹和货币成本。 该模型根据用户定义的优先级计算整体效率得分,可以通过自动代码分析或与性能测量工具集成。 这种方法通过实现实际、具有架构感知的算法比较来补充现有的理论模型,这些算法比较考虑了性能、可持续性和经济因素。 我们展示了一种开源实现,它分析代码,估计多维成本,并提供各种算法的效率建议。 我们解决了两个研究问题:(RQ1)多指标模型能否在架构中以高精度预测时间/能量? (RQ2)它与Big-O,ICE和EVM气体等基线相比如何? 验证显示与测量数据强相关性(h̊o̊>0.9),在多目标情景中优于基线。
对抗性强的量子态学习和测试
量子状态学习是物理学和计算机科学的一个基本问题。 由于近期量子设备容易出错,因此设计抗错算法非常重要。 除了设备错误外,其他意想不到的因素也可能会影响算法,例如粗心的人读出错误,甚至是恶意黑客故意改变测量结果。 因此,我们希望我们的算法即使在最坏的情况下也能工作,因为事情违背了我们的支持。 我们考虑单拷贝测量的实际设置,并提出γ对抗性腐败模型,假想的对手可以任意改变测量结果的γ段。 这比γ边界的SPAM噪声模型更强,其中测量后状态在跟踪距离中最多 γ 变化。 在我们更强的腐败模型下,我们使用非自适应测量来设计一种算法,可以在跟踪距离内学习到Õ(γ√(r)的未知等级r状态,前提是副本数量足够大。 我们进一步证明了Ω(γ√(r))的信息理论下限,用于非自适应测量,证明了我们算法的最优性。 我们的上下边界也用于量子态测试,其目标是测试未知状态是否等于给定状态或远离它。 我们的结果同时令人感到乐观和悲观。 对于一般状态,错误是维度依赖的,在最坏的情况下是γ√(d),这意味着只有一小部分(1/√(d))的结果才能完全破坏任何非自适应的学习算法。 然而,对于在许多量子算法中有用的恒定级状态,即使在最坏的情况对抗性设置中,也可以实现维度无关的错误。
叠加检测和QMA与非碰撞测量
我们证明验证器也可以进行单个非崩溃测量的 QMA 等于 EXXP,解决了 Aaronson 的一个开放问题。 我们显示这是经过修改的 QMA+ = EXXP [arXiv:2306.13247] 的必然结果。 受Blier和Tapp启发的许多结果的核心[arXiv:0709.0738]是一个非物理属性测试问题,决定量子态是否接近固定基础的元素。
使用转录网络进行模拟计算
转录网络是合成生物学中研究最广泛的系统类型之一。 虽然数字逻辑转录网络的完整性已经确立,但*analog*计算在生物系统中起着至关重要的作用,并为合成生物学应用提供了巨大的潜力。 虽然转录电路通常依赖于转录因子的共通性和高度非线性行为来调节蛋白质的*生产*,但它们通常用简单的线性*降解*术语建模。 相比之下,一般模拟动力学既需要非线性正态,也需要负数,似乎不仅需要控制转录(即生产)调节,还需要控制转录因子的降解率。 令人惊讶的是,我们证明控制转录因子产生(即转录率)而不明确控制降解在数学上是模拟计算的,实现了与生产和降解都是可编程的系统等效的能力。 我们在几个例子上展示了我们的方法,包括振荡和混沌动力学,模拟排序,内存,PID控制器和模拟extremum寻求。 我们的结果为使用合成转录网络进行新型模拟动力学的工程提供了系统方法,而不会增加降解控制的复杂性,并告知我们对自然转录电路能力的理解。 我们提供了一个编译器,以Python包的形式,可以采用任何多项式ODE系统,并将其转换为在适当条件下实现系统的等效转录网络。
用于线性代数问题的常数深度算术电路
我们设计了多项式大小、常数深度（即𝖠𝖢^0）的算术公式，用于计算两个多项式的最大公因数（GCD），以及相关的判别式、结式、Bézout系数、无平方分解问题，以及Sylvester矩阵和Bézout矩阵等结构化矩阵的求逆。我们的GCD算法可扩展到任意数量的多项式。此前，对于这些问题，已知的最佳算术公式需要超多项式大小，无论深度如何。这些结果基于新的算法技术，用于计算多项式根的各种对称函数，以及操作这些根的重数，而无需访问这些根。这些技术允许𝖠𝖢^0计算一大类线性和多项式代数问题，其中包括上述问题作为特例。我们将这些技术扩展到输入为多元多项式的问题，这些多项式由𝖠𝖢^0算术电路表示。在这里，我们也解决了诸如在𝖠𝖢^0中计算GCD和无平方分解等问题。
提高标准:古典和量子最短路径算法的渐近比较
单源最短路径(SSSP)问题是计算机科学的基石,具有广泛的应用,Dijkstra的算法长期以来一直是经典的基线。 虽然已经提出了各种量子算法,但它们的性能通常与这种几十年来的方法相吻合。 最近,Doutan等人引入了一种新的经典算法,其复杂性为O(m·(log n)^2/3,因此重塑了这种景观。 这一发展需要重新评估SSSP的量子优势叙事。 在本文中,我们根据这一新的经典前沿对现代量子和经典SSSP算法进行了系统的理论比较。 通过分析它们的理论成本函数,我们说明了它们的相对缩放如何比较图密度和路径长度不同的场景。 我们的分析提出了一个微妙的图景:复杂的量子算法,如Wesolowski和Piddock的量子算法,可以表现出更有利的渐近缩放,但只能在以短解决方案路径为特征的系统中。 相反,对于涉及长路径的问题,最先进的经典算法似乎保持缩放优势。 我们的工作为未来量子算法开发提供了最新的视角,并强调追求量子优势是一个动态的竞赛,其中经典的目标柱正在不断变化。
无线通信中多播光束成形的NP-完整性
在这项工作中,重新考虑无线通信中多播波束成形的经典问题。 现有的一项工作表明,多铸束形成问题是NP-hard。 在这个项目中,我们显示真实通道矩阵和波束器的相应决策问题是NP-complete。 最后,我们进行模拟,以揭示使用SAT/SMT求解器在各种设置中解决NP-complete波束成形问题的计算复杂性。
具有O(N^2log_2N)计算复杂性的矩阵乘法算法,用于可变精度算术
我们表明,假设具有可变精度算术的处理器的可用性,我们可以在计算复杂度中计算O(N^2log_2N)矩阵乘法。 我们通过 [A_11 A_12; A_21 A_22 ][ B_21 B_12; B_21 B_22 ]=[ A_11B_11+A_12B_21 A_11+A_12B_22; A_21 B_21 替换为 [A_11 A_11+A_21 B_21 B_21 B_21 B_21 B_21+A_22_22 ]=⌊[(A_11+ε A_12)(B_11+1/εB_21)(A_11+εA_12)(B_12(B_12/εB_22);(A_21+εA_22)(B_11+1/εB_21)(A_21+εA_22)(B_12+/εB_22)]⌋%1/ε1/ε/εB_22,其中⌊表示。 我们将块矩阵乘法乘法的数量从 8 减少到 4,保持加法数等于 4,并通过 ε 或 1/ε 引入 4 个块矩阵的乘法,以及 4 层和 4 个模数运算。 产生两个大小为N×N矩阵的计算复杂性可以从递归方程T(N)=4(N/2)^2(乘以ε和1/ε)加上4(N/2)^2(两个矩阵的加法)加上2N^2(地板和模数)加上4T(N/2)(四个递归调用)作为O(N^2log2)。 这些乘以数字尺度(如O((N/2)^2)的矩阵块的乘法。 我们还介绍了使用 vpa 可变精度算术模拟器的 MATLAB 代码,该仿真器可以使用 (4log_2N+1)N^2 vpa 操作来乘以 N× N 大小的矩阵。 这个模拟器使用 O(N) 数字来运行我们的算法。
通过计数行走来规范随机凝血图
众所周知,几乎所有的图形都可以通过称为颜色细化的简单组合程序来规范,也称为1维Weisfeiler-Leman算法。 在高概率的情况下,这种方法为随机输入图的每个顶点分配了一个唯一的标签,因此,它只适用于非对称图形。 如果输入图高度对称,组合精制技术的强度就成为一个微妙的问题。 我们证明,颜色细化和顶点个性化的组合产生了几乎所有循环图(即循环组的Cayley digraphs)的规范标签。 这一结果提供了顶点瞬态图类中组合细化的良好平均案例性能的第一个证据。 值得注意的是,我们甚至不需要色彩细化算法的全部功能。 我们表明,顶点 v 的规范标签可以通过计算从 v 到个体化顶点的每个长度的步数来获得。 我们的分析还暗示,几乎所有环状图在Tinhofer的意义上都是紧凑的,即它们的分数自态的多顶是不可或缺的。 最后,我们表明,可以通过更强大的二维Weisfeiler-Leman算法为几乎所有圆润图构建规范Cayley表示。
来自(几乎)必要假设的多验时间PIT
Kabanet和Imagliazzo(计算复杂性,2004年)的著名结果表明,PIT算法意味着电路下界,反之亦然。 从那时起,了解PIT和下界之间的精确连接一直是一大挑战。 特别是,一个主要目标是了解哪些下界足以获得高效的PIT算法,以及它们与结论所必需的下限有多接近。 我们构建多项式PIT算法,从下界到相对较小的剩余差距,这些算法是存在此类算法所必需的。 也就是说,我们证明这些下限是,到提到的小间隙,对于多项式时间PIT来说,都是足够和必要的,而不是特征零的字段。 在足够大的有限字段中,我们显示了一个类似的结果,其中PIT算法在时间n^log^(c)(n)中运行,即任意大常数c>1的c-迭代日志的功率。 这些改进的关键是研究统一设置中的PIT与下限,其中我们专注于证明统一算术电路及其变体的下界(以及从这些下界推断算法)。 事实上,通过在这种设置中工作,我们获得的结果比以前已知的多项式PIT与下界的结果要紧得多,并且实际上也比布尔环境中已知的硬度与随机性连接更紧。 我们的结果是通过结合最近从布尔硬度与随机性的技术,特别是Chen和Tell(FOCS 2021)的发电机,与郭,库马尔,萨普塔里希和所罗门(SIAM J.)的代数撞击集发生器相结合获得的结果。 2022年计算)以及Agrawal,Ghosh和Saxena(STOC 2018)以及Kumar,Saptharishi和Tengse(SODA 2019)的引导思想。
具有负相互作用的双状态自旋系统
我们研究计算双状态自旋系统的分区功能的近似性。 这个问题被一个2×2对称矩阵参数化。 之前关于此问题的结果仅限于矩阵具有非负条目的情况,或者仅限于对角线条目相等的情况,即。 正在模型。 在本文中,我们研究对任意2×2交互矩阵与真实条目的泛化。 我们表明,在参数空间的某些区域中,甚至很难确定分区函数的标志,而在其他地区,分区函数有完全多项式近似方案。 我们的研究结果揭示了几个新的计算阶段过渡。
平面故事计划中的几何学事项
故事计划将图形 G=(V,E) 可视化为 l 帧 Γ_1, ... Γ_l 的序列,每个图都是顶点子集 V_i ⊆ V 的诱导子图 G[V_i] 的绘图。 此外,每个顶点 v ∈ V 都包含在一个连续的帧 Γ_i, ..., Γ_j 序列中,连续帧中包含的所有顶点和边缘都相同,并且所有帧的结合都是 G 的绘图。 在GD 2022中,引入了平面故事计划的概念,其中每个框架都必须是平面(拓扑)绘图。 提供了几个(参数化)复杂性结果,用于识别承认平面故事计划的图形,包括NP-hardness。 在本文中,我们调查了GD论文中提出的一个开放问题,并表明平面故事平面图问题的几何和拓扑设置不同:我们提供了一个图形的实例,该图形承认平面故事平面故事计划,但没有平面几何故事计划,其中每个帧都是平面直线绘图。 尽管如此,通过将地形的还原证明调整到几何设置,我们表明,识别承认平面几何故事计划的图形仍然是NP-hard。