机构名称：
¥ 1.0
在阐明了算法的概念后，证明了许多经典问题的算法不可分辨性（例如，小组元素的认同，流形的同态性，同型二芬太汀方程的溶解性等）。这消除了找到解决方案的实用方法的问题。然而，由于这些算法规定的大量工作，解决其他问题的算法并不能消除它们的类似问题。这是所谓的顺序搜索问题的情况：最小化布尔功能，搜索有限的长度证明，确定图同构以及其他。所有这些问题都是通过列举所有可能性组成的琐碎算法来解决的。但是，这些算法需要指数级的工作时间，而数学家已经形成了信念，即对它们的简单算法是不可能的。已经获得了许多认真的论点以支持其有效性（见[1，2]），但没有人能够证明这一说法。（例如，尚未证明找到数学证据比验证它们需要更多的时间。）但是，如果我们假设存在无法通过简单算法解决的顺序搜索类型的某些（甚至是人为构造的）问题（就计算量而言），则可以证明许多“经典”顺序搜索问题（包括最小化问题，包括最小化问题，证明搜索问题等）也具有此属性。这构成了本文的主要结果。
通用顺序搜索问题-Lance Fortnow
主要关键词
相关文件推荐
