Mykyta Narusevych

collaborators

3 papers

math.LO2026

An independence of the MIN principle from the PHP principle

Mykyta Narusevych

The minimization principle $MIN (◃)$ studied in bounded arithmetic says that a strict linear ordering $◃$ on any finite interval $[0, \dots, n)$ has t…

math.LO2026

Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic

Mykyta Narusevych

We formulate a factorization hypothesis for linear orders definable by oracle polynomial-time machines. Assuming this hypothesis, we provide an approach to constructing a nonstanda…

math.LO2024

Ajtai's theorem for $T_{2}^{2} (R)$ and pebble games with backtracking

Eitetsu Ken, Mykyta Narusevych

We introduce a pebble game extended by backtracking options for one of the two players (called Prover) and reduce the provability of the pigeonhole principle for a generic predicat…

An independence of the MIN principle from the PHP principle

Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic

Ajtai's theorem for T22​(R) and pebble games with backtracking

Ajtai's theorem for $T_{2}^{2} (R)$ and pebble games with backtracking