A classic result of Paul, Pippenger, Szemer\'edi and Trotter states that DTIME(n) is strictly contained in NTIME(n). The natural question then arises: could DTIME(t(n)) be contained in NTIME(n) for some superlinear time-constructible function t(n)? If such a function t(n) does exist, then there also exist effective nondeterministic guessing strategies to speed up deterministic computations. In this work, we prove limitations on the effectiveness of nondeterministic guessing to speed up deterministic computations by showing that the existence of effective nondeterministic guessing strategies would have unlikely consequences. In particular, we show that if a subpolynomial amount of nondeterministic guessing could be used to speed up deterministic computation by a polynomial factor, then P is strictly contained in NTIME(n). Furthermore, even achieving a logarithmic speedup at the cost of making every step nondeterministic would show that SAT is in NTIME(n) under appropriate encodings. Of possibly independent interest, under such encodings we also show that SAT can be decided in O(n lg n) steps on a nondeterministic multitape Turing machine, improving on the well-known O(n(lg n)^c) bound for some constant but undetermined exponent c which is at least 1.
翻译:Paul、 Pippenger、 Szemer\'edi 和 Trotter 的经典结果显示, DTIME (n) 严格包含在 NTIME (n) 中。 自然问题由此产生: 对于某些超线时间可建函数 t(n) 来说, DTIME (t(n) 是否包含在 NTIME (n) 中? 如果此函数 t(n) 确实存在, 那么也存在有效的非决定性猜想策略来加速确定性计算。 在这项工作中, 我们证明, 非确定性猜想加快确定性计算的效果有限, 通过显示有效的非确定性猜想策略的存在不太可能带来后果。 特别是, 我们显示,如果使用非确定性猜想的亚极化数量来加速确定性计算, 那么P 严格地包含在 NTIME (n) 中。 此外, 即便在每一步不确定性解析度的计算方法的成本上, 也证明, SAT 在不确定性OTIME (n) 中, 最有可能在不固定的轨道中显示, 在不固定的状态下, 也显示我们确定性 正在调整的ODIME (n) 。