Kon*_*itz 0 algorithm asymptotic-complexity lower-bound
P中是否存在已证明O(n ^ 2)或更高的渐近下界的问题？(n是问题实例可以表示的位数).这不是一个功课问题,只是好奇心.
Dav*_*tat 6
是的,时间层次定理意味着存在这样的问题.它们可能不自然,因为它们涉及所有O(n ^ 2)时间算法的对角化.
归档时间：
12 年，5 月 前
查看次数：
375 次
最近记录：