Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL ALGORITHM:
Reports tagged with polynomial algorithm:
TR21-049 | 1st April 2021
Juraj Hromkovic

Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations

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 ... more >>>




ISSN 1433-8092 | Imprint