ECCC-Report TR21-049https://eccc.weizmann.ac.il/report/2021/049Comments and Revisions published for TR21-049en-usThu, 01 Apr 2021 15:52:24 +0300
Paper TR21-049
| Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations |
Juraj Hromkovic
https://eccc.weizmann.ac.il/report/2021/049We 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$."Thu, 01 Apr 2021 15:52:24 +0300https://eccc.weizmann.ac.il/report/2021/049