Completeness in the Polynomial-Time Hierarchy A Compendium ∗

By M. Schaefer, S. Avenue, C. Umans. 2008

145 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences (2009, methodology): “We will prove Σ 2 -completeness by a Karp reduction from the complement of the Π 2 -complete language ∀∃3cnf [12].”
A SAT-Based Approach to Learn Explainable Decision Sets (2018, result): “(Sketch) The simplest solution is to use earlier results [36, 40] to argue that the decision versions of MINDS3 and MINDS4 are complete for NP.”