works on
computational complexity 1nondeterministic turing machines 1np vs copnp 1oracle separations 1proof complexity 1

From the 1 of 1 linked paper with an AI index.

collaborators

1 paper

cs.CC2026

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines

Tianrong Lin

The paper constructs a language that can be decided by a nondeterministic Turing machine in polynomial time but not by any coNP machine, and uses this to claim a separation between…