Pith. sign in

REVIEW 2 major objections 5 minor 41 references

Complexity of Unambiguous Problems in $\Sigma^P_2$

T0 review · 2 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every unambiguous second-level problem captured by PTW, PCW, or PMA is contained in S2P, and hence in ZPP^NP—far below the generic Σ2P bound.

desk verdict A genuinely useful framework for unambiguous Sigma_2^P problems, with one load-bearing unproved code construction in the dice results; the rest of the architecture looks sound. read the letter →

arxiv 2510.19084 v3 pith:WBQZOPWB submitted 2025-10-21 cs.CC cs.GT

Matan Gilboa , Paul W. Goldberg , Elias Koutsoupias , Noam Nisan This is my paper · ORCID
classification cs.CCcs.GT MSC 68Q1568Q17
keywords unambiguouscomputationpolynomialhierarchyS2PZPP^NPCondorcetwinnertournamentintransitivedicehedonicgames
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's central claim is that many unambiguous problems in Σ2P—problems whose yes-instances have exactly one witness—fall into three syntactic classes, and every problem in those classes is contained in S2P, a symmetric-witness class known to sit inside ZPP^NP. This matters because the generic upper bound for these problems is Σ2P; S2P containment makes them solvable by a randomized polynomial-time algorithm with an NP oracle, a much lower complexity. The paper establishes the chain Δ2P ⊆ PCW ⊆ PTW ⊆ S2P and coNP ⊆ PMA ⊆ S2P, and uses the classes to classify concrete problems: strictly dominant strategies, consensus, winner-threshold, and two-voter Condorcet are Δ2P-complete; strong popularity in additive hedonic games and graph/circuit intransitive dice are PCW-complete. It also shows that small ambiguous twists of unambiguous problems jump to Σ2P-complete, demonstrating that uniqueness is the reason these problems are easy. Finally, weak dominance is shown to be equivalent to two-quantified unique satisfiability and to lie between Π2P and D2P.

What carries the argument

The load-bearing formulation is the tournament-on-strings perspective: an unambiguous Σ2P problem is encoded as asking for a source in an exponentially large tournament (or weak tournament) whose comparisons are answerable by a polynomial-time circuit; antisymmetry of the beat relation guarantees uniqueness. For the S2P upper bound, the paper uses a classical tournament fact—a sourceless tournament has a logarithmic-size set of vertices that collectively beat every vertex—which supplies a short symmetric no-instance certificate. For Condorcet and dice problems, it amplifies pairwise margins through many voters and then de-randomizes the amplification using ε-pairwise codes (explicitly constr

What would settle it

Try to verify or break Theorem B.14. For arbitrary q, T, and ε, one needs an explicit poly-constructible ε-pairwise code over [q]^n with n = poly(q, ε^{-1}, log T) and size T. Finding a triple (q, T, ε) for which any such code requires n super-polynomial in log T would refute the PCW-membership of the dice problems; conversely, a published construction would close the gap. The rest of the paper's containments do not depend on this code.

Watch

Extended reading notes

Core claim

The paper's core discovery is that the semantic class UΣ2P, despite being unlikely to have complete problems, contains three robustly identifiable syntactic layers, and all three are strictly easier than the enclosing class. PTW is defined by reductions to the problem of finding a source in an exponentially large weak tournament whose edge relation is a Boolean circuit; PCW is defined by reductions to finding a Condorcet string among polynomially many circuit voters; PMA is defined by reductions to finding a vertex adjacent to all vertices on one side of a sparse bipartite graph whose edge count is syntactically bounded below twice the number of vertices on the other side. The paper proves Δ

Load-bearing premise

The load-bearing premise is the existence, stated in Appendix B as Theorem B.14 without proof or public reference, of poly-constructible ε-pairwise codes with length polynomial in q, ε^{-1}, and log T; this de-randomization step is what puts Graph-Dice and Ckt-Dice in PCW, and if such codes do not exist the PCW upper bound for the dice problems collapses.

Editorial extensions

If this is right

  • Every problem in PTW, PCW, or PMA is in S2P, hence in ZPP^NP: a randomized polynomial-time algorithm with an NP oracle decides it, far below the generic Σ2P bound.
  • Δ2P ⊆ PCW makes Δ2P-hardness a standard tool for Condorcet-type problems; the paper proves Δ2P-completeness of strong dominant strategy, circuit consensus, circuit winner-threshold, and two-voter Condorcet.
  • Strong popularity in additively separable hedonic games is PCW-complete, settling an open problem left by earlier coNP-hardness results.
  • Graph-Dice and Ckt-Dice are PCW-complete, so the intransitive-dice winner problem has exactly the complexity of the Condorcet-winner framework.
  • Uniqueness is doing the work: the ambiguous variants Ckt-Unique-Value and 2-Ckt-Pareto are Σ2P-complete, while their unambiguous relatives sit in S2P.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An extension the paper leaves implicit: any problem whose solution space can be ordered by a circuit-computable weak tournament should be placeable in S2P by the same logarithmic-certificate argument, so the method should transfer to other social-choice existence questions beyond the four listed.
  • The parameterized Ckt-Condorcet[k] gap for k ≥ 3 is an open next step; the pairwise-code de-randomization is what lets the paper handle large voter sets, so testing whether three voters are still Δ2P-complete or have become PCW-complete would isolate exactly how intransitivity raises difficulty.
  • The PCW upper bound for dice problems is the only main result that depends on an unproved coding-theory existence statement (Theorem B.14); the rest of the S2P containments rest only on the tournament-certificate argument, so a reader who doubts the code construction can still accept PTW⊆S2P and PMA⊆S2P.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper defines three syntactic subclasses of UΣP2 — PTW (Polynomial Tournament Winner), PCW (Polynomial Condorcet Winner), and PMA (Polynomial Majority Argument) — whose unambiguity arises from tournament-source, Condorcet-winner, and majority-edge combinatorial principles. The main structural claims are ΔP2 ⊆ PCW ⊆ PTW ⊆ S2P and coNP ⊆ PMA ⊆ S2P, giving the first broad nontrivial upper bound (S2P, hence ZPPNP) for natural unambiguous ΣP2 problems. The paper also classifies concrete problems: Ashg-Strong-Popularity, Graph-Dice, and Ckt-Dice are shown PCW-complete; Strong-Dominant-Strategy, Ckt-Consensus, Ckt-Winner-Threshold, and Ckt-Condorcet[2] are shown ΔP2-complete; ambiguous variants Ckt-Unique-Value and 2-Ckt-Pareto are shown ΣP2-complete; and WDom-Strategy is shown equivalent to U∃∀-Sat, placed in DP2 and ΠP2-hard. All proofs are deferred to an appendix, with the ASHG reduction in a dedicated appendix section.

Significance. If the results hold, this is a substantial contribution. The paper identifies robust syntactic mechanisms that guarantee uniqueness inside ΣP2, proves meaningful upper bounds for all of them, and resolves the previously open complexity of strong popularity in additively separable hedonic games. The new classes are defined via complete problems and related to established classes through external reductions; I did not find a circularity. The main structural results (Theorems 3.3 and 5.3) appear sound and are independent of the coding-theoretic gap discussed below. The concrete classifications, especially the ASHG result, are technically demanding and are presented in impressive detail. However, the headline completeness classification of Graph-Dice and Ckt-Dice currently rests on an unproved theorem attributed to personal communication, which must be resolved before the paper can be accepted.

major comments (2)
  1. [Appendix B, Theorem B.14 and proof of Theorem 4.6] Theorem B.14 — the poly-constructible ε-pairwise code with n = poly(q, ε^{-1}, log T) — is stated without proof and only attributed to personal communication from A. Ta-Shma and N. Ta-Shma. This theorem is load-bearing: in the proof of Theorem 4.6 it supplies the deterministic code used to reduce Strict-Ckt-Dice to Ckt-Condorcet, with parameters m' = poly(m,n) and ε < 1/(2m^4). Without a proof or a verifiable public reference, the polynomial-time construction of the circuits C'_i cannot be justified, and the PCW upper bound for Graph-Dice and Ckt-Dice collapses. The asserted parameters are plausible by probabilistic arguments, but explicit poly-constructibility is exactly the nontrivial missing ingredient. This must be fixed by supplying a proof or a public citation.
  2. [Appendix D, Theorem 6.1 (Ckt-Consensus and Strong-Dominant-Strategy)] In the S2P-membership style algorithms for Ckt-Consensus and Strong-Dominant-Strategy, the final NP-oracle queries are written as ∃x′, i such that Ci(x′) ≥ Ci(x*) and ∃x′, y such that C(x′||y) ≥ C(x*||y), respectively, without requiring x′ ≠ x*. Since x′ = x* makes both queries trivially true, the algorithms as written would always output 0. The intended fix is to require x′ ≠ x* (or to use a strict inequality). This is a local fix, but it is necessary for the correctness of the ΔP2 upper-bound proofs.
minor comments (5)
  1. [Section 1, Introduction] Typo: “notable notable examples” should read “notable examples.”
  2. [Appendix B, Lemma B.10] The statement says “C′ is a Yes-instance if and only if C′ is a Yes-instance”; the first occurrence should be C (the original instance).
  3. [Appendix G, throughout] Lemmas G.4–G.39 are labeled “Lemma” but are consistently cross-referenced as “Theorem G.x.” Please normalize the cross-referencing.
  4. [Appendix G, Lemma G.19] The notation “XX′(Gi)” and “XX∗(Gi)” appears to be a typo for x′(Gi) and x∗(Gi).
  5. [Appendix A, proof of Theorem 3.2] The intuitive explanation before the formal construction says “if there was only one edge between x and y, say (y,x), then we add the edge (x, v_{x,y})”; this seems reversed relative to the formal case analysis. Please clarify the intuition.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the novel classes are defined syntactically via complete problems and their containments are proved directly; the unproved personal-communication coding lemma is a correctness risk, not circularity.

full rationale

I walked the derivation chain for the main claims. PTW is defined as the many-one closure of Weak-Tournament-Source, PCW as the closure of Ckt-Condorcet, and PMA as the closure of Edge-Majority. The containments PTW ⊆ S_2^P, PCW ⊆ PTW, and PMA ⊆ S_2^P are proved directly from these syntactic definitions and standard S_2^P witness arguments (Theorems 3.3, 4.2, 5.3). The completeness results for Ashg-Strong-Popularity, Graph-Dice, and Ckt-Dice are proved by explicit polynomial-time reductions to and from the defining problems; no parameter is fitted to data, and no prediction is a renamed input. The only self-citation, [BG25], is used as a contrasting hardness result (weak popularity is ΣP2-complete) and to state an open problem; it is not load-bearing for the new upper bounds. The one substantive weakness is Theorem B.14, an existence theorem for poly-constructible ε-pairwise codes attributed solely to personal communication from Amnon Ta-Shma and Noam Ta-Shma, with no proof or public reference in the paper. That theorem is load-bearing for the PCW-membership direction of Strict-Ckt-Dice and hence for the PCW-completeness of Graph-Dice and Ckt-Dice, because it de-randomizes the reduction from Strict-Ckt-Dice to Ckt-Condorcet. This is an unverified external assumption and therefore a correctness/completeness risk, but it is not circularity: the theorem is not derived from the paper's classes, is not a renamed version of the paper's target claim, and is not a self-citation. Accordingly, the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 3 invented entities

The paper introduces three new syntactic complexity classes and proves structural results about them. No free parameters are fitted to data. The main non-standard load-bearing assumption is the unproved coding-theory theorem (B.14) used in the dice reductions. The new classes themselves are internal mathematical constructs rather than empirically testable entities.

assumptions (3)
  • ad hoc to paper Theorem B.14: For every q,T,ε>0 there exists a poly-constructible ε-pairwise code S over [q]^n with |S|=T and n=poly(q,ε^{-1},log T).
    Invoked without proof in Theorem 4.6 to derandomize the reduction from Strict-Ckt-Dice to Ckt-Condorcet; attributed to personal communication. If this construction is unavailable, the PCW upper bound for the dice problems fails.
  • domain assumption Known complexity-theoretic background: S^P_2 ⊆ ZPP^NP (Cai07), Δ^P_2 = P^NP, TSP-Unique-Opt is Δ^P_2-complete (Pap84), and the dual characterization of the polynomial hierarchy.
    Used throughout as standard external benchmarks for comparing the new classes. These are established results from the literature, not derived in this paper.
  • standard math Boolean circuits can be converted to Boolean formulas preserving solutions (Cook–Levin theorem).
    Used in Section 8 to switch between circuit and formula representations in the reductions involving U∃∀-Sat and WDom-Strategy.
invented entities (3)
  • PTW (Polynomial Tournament Winner)
    purpose: Syntactic class of unambiguous Σ^P_2 problems whose uniqueness arises from a tournament winner; defined via Weak-Tournament-Source.
    New mathematical construct; its significance is internal to the complexity-theoretic framework, with no falsifiable handle outside the paper.
  • PCW (Polynomial Condorcet Winner)
    purpose: Subclass of PTW capturing problems where comparisons come from majority vote among polynomially many voters.
    New mathematical construct; completeness results connect it to concrete problems, but these are internal mathematical facts, not external empirical predictions.
  • PMA (Polynomial Majority Argument)
    purpose: Syntactic class capturing unambiguous Σ^P_2 problems whose uniqueness comes from a majority-of-edges argument.
    New mathematical construct; no external falsifiable consequences outside the paper's own theorems.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity of Unambiguous Problems in $\Sigma^P_2$." pith.science (2026). https://pith.science/paper/WBQZOPWB

@misc{pith2026251019084,
  author       = {Pith},
  title        = {Pith review of: Complexity of Unambiguous Problems in $\Sigma^P_2$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WBQZOPWB}},
  note         = {Machine review of arXiv:2510.19084}
}
abstract

Various practical problems within the class $\Sigma_{2}^P$ possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing all unambiguous $\Sigma_{2}^P$ problems is denoted $U\Sigma_{2}^P$. Examples include the existence of (1) a dominating strategy in a game, (2) a Condorcet winner, (3) a strongly popular partition in hedonic games, and (4) a winner (source) in a tournament. The computational complexity of unambiguous problems is not well understood, leaving many questions unresolved. We address this gap in a broad complexity-theoretic sense; our main contributions consist of the following. - We identify three syntactic subclasses of $U\Sigma_{2}^P$ associated with general properties of problems that guarantee uniqueness: Polynomial Tournament Winner (PTW), Polynomial Condorcet Winner (PCW), and Polynomial Majority Argument (PMA). - We establish complexity upper and lower bounds for our proposed classes. In particular, we show that they are all contained in $S_2^P$ and are thus significantly easier than the immediate $\Sigma_{2}^P$ upper bound. - We characterize the complexity of various practical problems using this framework.

Figures

Figures reproduced from arXiv: 2510.19084 by the authors.

Figure 1
Figure 1. Our proposed complexity classes (in red) relative to known subclasses of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Assignment gadget of bit xi . Dots represent single agents; circles represent sets of m replicas. a 0 i a 1 i g 0 i g 1 gˆ i 0 i gˆ 1 i ℓ g i ˆℓ g i [PITH_FULL_IMAGE:figures/full_fig_p043_2.png] view at source ↗
Figure 4
Figure 4. Not-gadget of gate Gi = ¬Gj . g 0 j g 0 k g 1 j g 1 k g 0 i g 1 i gˆ 0 i gˆ 1 i ℓ g i ˆℓ g i wi zi wˆi zˆi 2 3 2 2 [PITH_FULL_IMAGE:figures/full_fig_p043_4.png] view at source ↗
Figures from the paper (1 more)
Figure 7
Figure 7. Figure 7: High-level illustration of the reduction used in the proof of Theorem 4.5, for [PITH_FULL_IMAGE:figures/full_fig_p044_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 2 linked inside Pith

  1. [2]

    Generalized intransitive dice: Mimicking an arbitrary tournament

    Ethan Akin. Generalized intransitive dice: Mimicking an arbitrary tournament. Journal of Dynamics and Games , 8(1):1--20, 2020

    2020

  2. [1]

    The computational complexity of structure-based causality

    Gadi Aleksandrowicz, Hana Chockler, Joseph Y Halpern, and Alexander Ivrii. The computational complexity of structure-based causality. Journal of Artificial Intelligence Research , 58:431--451, 2017

    2017

  3. [3]

    Trading group theory for randomness

    L \'a szl \'o Babai. Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages 421--429, 1985

    1985

  4. [4]

    Finding and recognizing popular coalition structures

    Felix Brandt and Martin Bullinger. Finding and recognizing popular coalition structures. Journal of Artificial Intelligence Research , 74:569--626, 2022

    2022

  5. [5]

    On the unique satisfiability problem

    Andreas Blass and Yuri Gurevich. On the unique satisfiability problem. Information and Control , 55(1-3):80--88, 1982

    1982

  6. [6]

    Settling the complexity of popularity in additively separable and fractional hedonic games

    Martin Bullinger and Matan Gilboa. Settling the complexity of popularity in additively separable and fractional hedonic games. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25 , pages 3771--3779, 8 2025

    2025

  7. [7]

    Does co-np have short interactive proofs? Information Processing Letters , 25(2):127--132, 1987

    Ravi B Boppana, Johan Hastad, and Stathis Zachos. Does co-np have short interactive proofs? Information Processing Letters , 25(2):127--132, 1987

    1987

  8. [8]

    The stability of hedonic coalition structures

    Anna Bogomolnaia and Matthew O Jackson. The stability of hedonic coalition structures. Games and Economic Behavior , 38(2):201--230, 2002

    2002

Show all 41 references
  1. [9]

    S ^p_2 ZPP ^ NP

    Jin-Yi Cai. S ^p_2 ZPP ^ NP . Journal of Computer and System Sciences , 73(1):25--35, 2007

    2007

  2. [10]

    More on BPP and the polynomial-time hierarchy

    Ran Canetti. More on BPP and the polynomial-time hierarchy. Information Processing Letters , 57(5):237--241, 1996

    1996

  3. [11]

    A central limit theorem for intransitive dice

    Luis G Coelho, Tertuliano Franco, Lael V Lima, Jo \ a o PC de Paula, Jo \ a o V A Pimenta, Guilherme L F Silva, and Daniel Ungaretti. A central limit theorem for intransitive dice. arXiv preprint arXiv:2310.17083 , 2023

    2023

  4. [12]

    Intransitive dice tournament is not quasirandom

    Elisabetta Cornacchia and Jan H a z a. Intransitive dice tournament is not quasirandom. arXiv preprint arXiv:2011.10067 , 2020

    2011 arXiv

  5. [13]

    Symmetric exponential time requires near-maximum circuit size

    Lijie Chen, Shuichi Hirahara, and Hanlin Ren. Symmetric exponential time requires near-maximum circuit size. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1990--1999, 2024

    1990

  6. [14]

    The complexity of theorem-proving procedures

    Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing , STOC '71, page 151–158. Association for Computing Machinery, 1971

    1971

  7. [15]

    Essai sur l'application de l'analyse \`a la probabilit \'e des d \'e cisions rendues \`a la pluralit \'e des voix

    Marquis De Condorcet. Essai sur l'application de l'analyse \`a la probabilit \'e des d \'e cisions rendues \`a la pluralit \'e des voix . Imprimerie Royale, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York

    1972

  8. [16]

    On the representation of directed graphs as unions of orderings

    Paul Erd o s and Leo Moser. On the representation of directed graphs as unions of orderings. Math. Inst. Hung. Acad. Sci , 9:125--132, 1964

    1964

  9. [17]

    Paradox of nontransitive dice and elusive principle of indifference

    Martin Gardner. Paradox of nontransitive dice and elusive principle of indifference. Scientific American , 223(6):110, 1970

    1970

  10. [18]

    Match making: assignments based on bilateral preferences

    Peter G \"a rdenfors. Match making: assignments based on bilateral preferences. Behavioral Science , 20(3):166--173, 1975

    1975

  11. [19]

    Complexity measures for public-key cryptosystems

    Joachim Grollmann and Alan L Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing , 17(2):309--335, 1988

    1988

  12. [20]

    On isomorphisms and density of NP and other complete sets

    Juris Hartmanis and Leonard Berman. On isomorphisms and density of NP and other complete sets. In Proceedings of the eighth annual ACM symposium on Theory of computing , pages 30--40, 1976

    1976

  13. [21]

    A game of nontransitive dice

    Artem Hulko and Mark Whitmeyer. A game of nontransitive dice. Mathematics Magazine , 92(5):368--373, 2019

    2019

  14. [22]

    Deciding the winner in parity games is in UP co- UP

    Marcin Jurdzi \'n ski. Deciding the winner in parity games is in UP co- UP . Information Processing Letters , 68(3):119--124, 1998

    1998

  15. [23]

    Total functions in the polynomial hierarchy

    Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H Papadimitriou. Total functions in the polynomial hierarchy. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) , pages 44--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2021

    2021

  16. [24]

    Range avoidance and the complexity of explicit constructions

    Oliver Korten. Range avoidance and the complexity of explicit constructions. Bulletin of EATCS , 145(1), 2025

    2025

  17. [25]

    The complexity of optimization problems

    Mark W Krentel. The complexity of optimization problems. In Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages 69--76, 1986

    1986

  18. [26]

    Symmetric exponential time requires near-maximum circuit size: Simplified, truly uniform

    Zeyong Li. Symmetric exponential time requires near-maximum circuit size: Simplified, truly uniform. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 2000--2007, 2024

    2000

  19. [27]

    Unambiguous polynomial hierarchies and exponential size

    Klaus-Jörn Lange and Peter Rossmanith. Unambiguous polynomial hierarchies and exponential size. In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory , pages 106--115. IEEE, 1994

    1994

  20. [28]

    Unambiguous computations and locally definable acceptance types

    Rolf Niedermeier and Peter Rossmanith. Unambiguous computations and locally definable acceptance types. Theoretical Computer Science , 194(1-2):137--161, 1998

    1998

  21. [29]

    On the complexity of unique solutions

    Christos H Papadimitriou. On the complexity of unique solutions. Journal of the ACM (JACM) , 31(2):392--400, 1984

    1984

  22. [30]

    Computational Complexity

    Christos H Papadimitriou. Computational Complexity . Addison-Wesley, 1994

    1994

  23. [31]

    The complexity of facets (and some facets of complexity)

    Christos H Papadimitriou and Mihalis Yannakakis. The complexity of facets (and some facets of complexity). In Proceedings of the fourteenth annual ACM symposium on Theory of computing , pages 255--260, 1982

    1982

  24. [32]

    Domination and irredundance in tournaments

    Kenneth B Reid, Alice A McRae, Sandra Mitchell Hedetniemi, and Stephen T Hedetniemi. Domination and irredundance in tournaments. Australasian journal of combinatorics , 29:157--172, 2004

    2004

  25. [33]

    Symmetric alternation captures BPP

    Alexander Russell and Ravi Sundaram. Symmetric alternation captures BPP . computational complexity , 7(2):152--162, 1998

    1998

  26. [34]

    Balanced non-transitive dice ii: tournaments

    Alex Schaefer. Balanced non-transitive dice ii: tournaments. arXiv preprint arXiv:1706.08986 , 2017

    2017 arXiv

  27. [35]

    On the difference between one and many: preliminary version

    Janos Simon. On the difference between one and many: preliminary version. In International Colloquium on Automata, Languages, and Programming , pages 480--491. Springer, 1977

    1977

  28. [36]

    The voting problem

    Richard Stearns. The voting problem. The American Mathematical Monthly , 66(9):761--763, 1959

    1959

  29. [37]

    The polynomial-time hierarchy

    Larry J Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science , 3(1):1--22, 1976

    1976

  30. [38]

    A reduction from satisfiability to hamiltonian circuits that preserves the number of solutions

    Leslie G Valiant. A reduction from satisfiability to hamiltonian circuits that preserves the number of solutions. Manuscript, Leeds , 1974

    1974

  31. [39]

    Relative complexity of checking and evaluating

    Leslie G Valiant. Relative complexity of checking and evaluating. Information processing letters , 5(1):20--23, 1976

    1976

  32. [40]

    NP is as easy as detecting unique solutions

    Leslie G Valiant and Vijay V Vazirani. NP is as easy as detecting unique solutions. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , STOC '85, page 458–463, New York, NY, USA, 1985. Association for Computing Machinery

    1985

  33. [41]

    Complete sets and the polynomial-time hierarchy

    Celia Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science , 3(1):23--33, 1976

    1976

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.