On the Pseudo-Deterministic Query Complexity of NP Search Problems

Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul SanthanamCCC 2021 · OpenReview

TL;DR

This paper introduces and analyzes "pseudo-deterministic query complexity," a model for randomized algorithms that must produce a consistent output for any given input. The authors prove a significant separation between randomized and pseudo-deterministic query complexity for certain NP search problems, showing that pseudo-determinism can be exponentially harder. Surprisingly, they also demonstrate that in the average-case, zero-error setting, these different notions of complexity collapse.

What Problem Does This Paper Address?

The paper delves into the nuances of computational complexity, specifically focusing on "pseudo-deterministic query complexity." Imagine a randomized algorithm that, for any input, must always output the same answer with high probability, even though it uses randomness. This is the essence of pseudo-determinism. The authors investigate how this requirement impacts the efficiency of solving search problems, particularly those related to NP. They aim to understand the power and limitations of pseudo-deterministic algorithms compared to standard randomized algorithms, especially in the context of query complexity (how many times an algorithm needs to "look up" information about the input). A key challenge is to find problems where pseudo-determinism imposes a significant overhead, and to explore scenarios where this overhead disappears.

Methods

The core of the paper's contribution lies in establishing lower bounds for pseudo-deterministic query complexity. They achieve this by:

  • Connecting to Proof Complexity: The authors leverage results from proof complexity, specifically concerning the difficulty of refuting random unsatisfiable CNF formulas using proof systems like Nullstellensatz and Sum-of-Squares.
  • Utilizing Huang's Sensitivity Theorem: A crucial step involves applying Huang's recent breakthrough on the Sensitivity Conjecture, which relates the degree of a function to its sensitivity. This connection allows them to translate proof complexity lower bounds into lower bounds on sensitivity, and subsequently to pseudo-deterministic query complexity.
  • Defining and Analyzing Canonical Problems: They introduce and analyze a specific problem called "FIND1" (finding a '1' in a vector with at least half '1's) and a family of search problems based on random unsatisfiable CNF formulas. These problems serve as benchmarks for their theoretical results.
  • Average-Case Analysis: For the surprising result about complexity collapse, they employ averaging arguments and sophisticated simulation techniques to show that in the zero-error, average-case setting, deterministic, randomized, and pseudo-deterministic algorithms become equivalent in terms of query complexity.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and uses abstract problem instances (random CNF formulas, binary strings) rather than specific datasets.

Key Insights and Ideas

  • Pseudo-determinism can be exponentially harder: The paper demonstrates an exponential separation between randomized query complexity and pseudo-deterministic query complexity for certain NP search problems. This is a significant finding, as it shows that the requirement of a consistent output can dramatically increase computational cost.
  • The "FIND1" problem as a canonical example: The problem of finding a '1' in a dense binary vector (FIND1) is identified as a key problem for understanding pseudo-deterministic complexity in the FNP class.
  • Surprising collapse in the average-case, zero-error setting: Perhaps the most counter-intuitive finding is that when algorithms are allowed to make mistakes only on average (zero-error average-case), deterministic, randomized, and pseudo-deterministic algorithms become essentially equivalent in terms of query complexity. This suggests that the strict consistency requirement of pseudo-determinism is less impactful when errors are averaged out.
  • Connections to combinatorial coloring: The research reveals a link between pseudo-deterministic query complexity and problems in extremal graph theory, specifically concerning the sensitivity of hypercube colorings.

Key Results

  • Ω(√n) lower bound for pseudo-deterministic query complexity: The authors prove a lower bound of Ω(√n) for a family of search problems based on random unsatisfiable CNF instances and for the FIND1 problem. This bound is shown to be tight in the quantum setting.
  • Exponential separation: This Ω(√n) lower bound implies an exponential separation between randomized query complexity and pseudo-deterministic query complexity for these problems.
  • Average-case collapse: For zero-error algorithms, the paper shows that deterministic, randomized, and pseudo-deterministic query complexities are equivalent up to polylogarithmic factors on average over any distribution.
  • Applications to proof complexity: The work provides insights into the relationship between pseudo-deterministic algorithms and proof systems like Resolution, leading to an exponential separation between random and pseudo-deterministic tree-like Resolution refutations.

Limitations and Future Work

  • Conjecture for Ω(n) lower bound: The authors conjecture that the Ω(√n) lower bound for FIND1 and related problems can be improved to Ω(n) for pseudo-deterministic query complexity. Achieving this would require bypassing current techniques that incur a quadratic loss (like sensitivity).
  • Superpolynomial/exponential lower bounds for pseudo-deterministic Resolution: The paper leaves open the question of proving stronger (superpolynomial or exponential) lower bounds for pseudo-deterministic Resolution refutations.
  • Generalizing to other algebraic proof systems: The authors pose questions about whether similar relationships can be established for stronger algebraic proof systems like Sherali-Adams and Sum-of-Squares.
  • Communication Complexity: The paper highlights the importance of studying pseudo-determinism in the context of communication complexity, suggesting that similar separations might be achievable there, though current lifting techniques might not directly apply due to the nature of canonical solutions.

Summary updated

Abstract

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.
BibTeX
@inproceedings{goldwasser2021pseudo,
  author = {Shafi Goldwasser and Russell Impagliazzo and Toniann Pitassi and Rahul Santhanam},
  title = {{On the Pseudo-Deterministic Query Complexity of NP Search Problems}},
  booktitle = {CCC},
  year = {2021},
  url = {https://openreview.net/forum?id=0OwgfmgG85},
}

Loading related content...

Figure