exponential time hypothesis

BQP和NP之间的关系是什么？ 独特游戏猜想（英语：unique games conjecture） 指数时间假说（英语：exponential time hypothesis）是真的吗？ 单向函数存在吗？ 两个n位数乘法算法速度最快的是什么？ 速度最快的矩阵乘法算法是什么？ 可以在多项式时间内做整数分解吗？

短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式（可能是指数（英语：Exponential time hypothesis））级别增长。 问题在1930年首次被形式化，為最佳化中被研究得最深入的问题之一，许多优化方法都奉其为基准。尽管问题在计算

。这个推论意味着对于一个问题而言，非确定性可以为图灵机节省的存储空间是相当有限的。作为对比，在时间复杂度理论中，指数时间假说（英语：exponential time hypothesis）猜想，对于时间复杂度而言，非确定型和确定型空间复杂度类之间的差距可能是指数级的。

{\displaystyle |V(H)|^{{\mathcal {O}}(k)}} 算法中，複雜度的指數可能無法再壓低太多：若指數時間假設（英语：exponential time hypothesis）（ETH）為真，則不存在時間複雜度為 | V ( H ) | o ( t w ( G ) / log ⁡ t w ( G

[quant-ph].  A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems[永久失效連結]. Proceedings