10 citations · 25 across the 13 of their papers we have counts for
Showing 2026Show all
2 papers · 1 filter
cs.CC2026
Unconditional -independence of a certified hitting-set principle
Martin Kolář
We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, i…
cs.CC2026
On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
Martin Kolář
The definition of \NP\ requires, for each member language~, a polynomial-time checking relation~ and a constant~ such that $w \in L \iff \exists y\,(|y| \leq |w|^k \wedge…