Effective guessing has unlikely consequences

DOI10.1007/S00224-023-10119-XMaRDI QIDQ6109068zbMATH OpenOpenAlexFDO

Authors András Z. Salamon, Michael Wehar

Publication date 26 July 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2111.02138

zbMATH Keywords

computational complexitylimited nondeterminismstructural complexitycomplexity class containmentseffective guessing

Mathematics Subject Classification ID

Theory of computing (68Qxx) Circuits, networks (94Cxx) Theory of data (68Pxx)

Abstract: 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.

Cites work

• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• A Remark on Stirling's Formula
• A Turing machine time hierarchy
• Computability and complexity theory.
• Hierarchies for semantic classes
• Lower bounds on the complexity of recognizing SAT by Turing machines
• New non-uniform lower bounds for uniform classes
• Nonuniform ACC circuit lower bounds
• On the Computational Complexity of Algorithms
• Reducibility among combinatorial problems
• Satisfiability Is Quasilinear Complete in NQL
• The complexity of theorem-proving procedures
• Time- and tape-bounded Turing acceptors and AFLs
• Turing machines that take advice
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(1)

• scientific article; zbMATH DE number 1906339 (Why is no real title available?)

This page was built for publication: Effective guessing has unlikely consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109068)