On the pseudo-deterministic query complexity of NP search problems

DOI10.4230/lipics.ccc.2021.36OpenAlexW3186369772MaRDI QIDQ6115399

Rahul Santhanam, Toniann Pitassi, Russell Impagliazzo

Publication date: 12 July 2023

Full work available at URL: https://doi.org/10.4230/lipics.ccc.2021.36

zbMATH Keywords

proof complexityquery complexitypseudo-determinism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

This page was built for publication: On the pseudo-deterministic query complexity of NP search problems