一个$ o（n^k）$算法仅需要一个$ o（2^n）$计算（对于所有n个实例）是p或np

Question

让$ a $一个决策问题和$ a $一个算法在$ o（n^k）$中求解它。

但是，要构建$ a_n $，我们需要计算某些东西（策略路径，魔术数字，...），我们可以计算使用某些常规算法$ r $ in $ o（2^n）$。

好吧，$ a $是多项式（然后，所有$ a_n $都在 p）和$ r $是指数。

我们 不能 解决大型实例，因为$ r $是不切实际的。

但是，实际上，我们可以在大力计算$ a_n = r（n）$之后解决大型实例。

我的问题是双重的：

• 理论上如何考虑此类问题？他们是否被明确研究？有特殊情况吗？一些文学要读？

• 在实践中如何解决此类问题？他们是否已经被研究了？有特殊情况吗？一些文学要读？

Answer 1

如果“事物”是多项式大小的，那么它是在P/Poly中进行的，该课程已经进行了深入研究，尽管这是一个非常有趣的子类，我不相信这是一个非常有趣的子类。如果您有一种属于此子类的算法，我相信理论计算机科学家可能会对它感兴趣。

如果“事物”可以是指数级的大小，那么“事物”可能只是大小$ n $的所有答案的表格，因此，所有注册时间的所有算法都将属于此类。实际上，由于算法r之后是A exptime，因此该课程将等于注入时间。