XiaoMi-AI文件搜索系统
World File Search System顺序搜索
通用顺序搜索问题-Lance Fortnow
证明。让P是一个顺序搜索问题，与n相当的参数长度无法及时求解。我们将证明每个问题1-6至少与p一样困难。通过引理1（以下证明），问题1-6是通用的顺序搜索问题。这意味着可以将P减少到这些问题中的每一个。让我们考虑将P减少到问题I（其中我是1到6的任何数字）。There exist three algorithms r ( x ), p ( y ), and s ( y ), working in time compara- ble to the length of the argument, such that: 1) P ( x, p ( y )) ⇔ Problem i ( r ( x ) , y ) 2) P ( x, y ) ⇔ Problem i ( r ( x ) , s ( y )) Suppose, for contradiction, that problem i can be solved in time less than f ( n ).然后我们可以如下求解P：1）给定X的输入X，计算R（x）。2）时间少于f（n）解决问题I（r（x），y）。3）如果找到溶液y，请计算p（y）以获取p。
通用顺序搜索问题-Lance Fortnow
在阐明了算法的概念后，证明了许多经典问题的算法不可分辨性（例如，小组元素的认同，流形的同态性，同型二芬太汀方程的溶解性等）。这消除了找到解决方案的实用方法的问题。然而，由于这些算法规定的大量工作，解决其他问题的算法并不能消除它们的类似问题。这是所谓的顺序搜索问题的情况：最小化布尔功能，搜索有限的长度证明，确定图同构以及其他。所有这些问题都是通过列举所有可能性组成的琐碎算法来解决的。但是，这些算法需要指数级的工作时间，而数学家已经形成了信念，即对它们的简单算法是不可能的。已经获得了许多认真的论点以支持其有效性（见[1，2]），但没有人能够证明这一说法。（例如，尚未证明找到数学证据比验证它们需要更多的时间。）但是，如果我们假设存在无法通过简单算法解决的顺序搜索类型的某些（甚至是人为构造的）问题（就计算量而言），则可以证明许多“经典”顺序搜索问题（包括最小化问题，包括最小化问题，证明搜索问题等）也具有此属性。这构成了本文的主要结果。