Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
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." Show more
Publication status
publishedExternal links
Journal / series
Electronic Colloquium on Computational ComplexityPages / Article No.
Publisher
Universität TrierOrganisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics