2026-07-20T06:22:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14310 2024-03-06T10:53:56Z ddc:004 open_access

On the Pseudo-Deterministic Query Complexity of NP Search Problems Goldwasser, Shafi Impagliazzo, Russell Pitassi, Toniann Santhanam, Rahul Pseudo-determinism Query complexity Proof complexity We study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF instances, and also for the promise problem (FIND1) of finding a 1 in a vector populated with at least half one’s. This gives an exponential separation between randomized query complexity and pseudo-deterministic complexity, which is tight in the quantum setting. As applications we partially solve a related combinatorial coloring problem, and we separate random tree-like Resolution from its pseudo-deterministic version. In contrast to our lower bound, we show, surprisingly, that in the zero-error, average case setting, the three notions (deterministic, randomized, pseudo-deterministic) collapse. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shafi Goldwasser and Russell Impagliazzo and Toniann Pitassi and Rahul Santhanam 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.36 urn:nbn:de:0030-drops-143104 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.36 eng https://creativecommons.org/licenses/by/4.0/legalcode