Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-049 | 19th April 2021 20:42

Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations

RSS-Feed




Revision #1
Authors: Juraj Hromkovic
Accepted on: 19th April 2021 20:42
Downloads: 17
Keywords: 


Abstract:

We call any consistent and sufficiently powerful formal theory that enables to algorithmically verify whether a text is a proof \textbf{algorithmically verifiable mathematics} (av-mathematics). We study the question whether nondeterminism is more powerful than determinism for polynomial time computations in the framework of av-mathematics. Our main results are as follows. \\
"$\P \subsetneq \NP$ or for any deterministic, polynomial time compression algorithm $A$ there exists a nondeterministic, polynomial time compression machine $M$ that reduces infinitely many binary strings logarithmically stronger than $A$." \\
"$\P \subsetneq \NP$ or f-time resource bounded Kolmogorov complexity of any binary string $x$ can be computed in deterministic polynomial time for each polynomial, time constructible function $f$."\\
For computing models with "efficient" interpreters we prove the following theorem:\\
"For each polynomial, time constructible function $f$, $\TIMEf \subsetneq \NTIMEf$ or one can essentially stronger compress words nondeterministically in time $\Oh{f(n)}$ than deterministically in time $f(n)$."



Changes to previous version:

strengthening some of the results


Paper:

TR21-049 | 1st April 2021 14:32

Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations





TR21-049
Authors: Juraj Hromkovic
Publication: 1st April 2021 15:52
Downloads: 135
Keywords: 


Abstract:

We call any consistent and sufficiently powerful formal theory that enables to algorithmically in polynomial time verify whether a text is a proof \textbf{efficiently verifiable mathematics} (ev-mathematics). We study the question whether nondeterminism is more powerful than determinism for polynomial time computations in the framework of ev-mathematics. Our main results are as follows. \\
"$\P \subsetneq \NP$ or for any deterministic, polynomial time compression algorithm $A$ there exists a nondeterministic, polynomial time compression machine $M$ that reduces infinitely many binary strings logarithmically stronger than $A$." \\
"$\P \subsetneq \NP$ or f-time resource bounded Kolmogorov complexity of any binary string $x$ can be computed in deterministic polynomial time for each polynomial time constructible function $f$."



ISSN 1433-8092 | Imprint