Abstract Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [6]. We say two compatible (i.e., having the same input types) control types that are about the same election system $$\mathcal {E}$$ E form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the attempted attacks can be successfully carried out (see the Preliminaries for a more formal definition) [31]. For each of the seven general (i.e., holding for all election systems) electoral control type collapsing pairs found by Hemaspaandra, Hemaspaandra, and Menton [31] and for each of the additional electoral control type collapsing pairs of Carleton et al. [10] for veto and approval (and many other election systems in light of that paper’s Theorems 3.6 and 3.9), both members of the collapsing pair have the same complexity since as sets they are the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [31] and Carleton et al. [10], we prove that the pair’s members’ search-version complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. For the concrete systems plurality, veto, and approval, we completely determine which of their (due to our results) polynomially-related collapsing search-problem pairs are polynomial-time computable and which are NP-hard.

Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that perhaps other pairs of control types are identical, and so work still is being needlessly duplicated. We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.

Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that FewP ⊆ ⊕ P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES.

A backbone of a boolean formula F is a collection S of its variables for which there is a unique partial assignment aS such that F[aS] is satisfiable (Monasson et al. 1999; Williams, Gomes, and Selman 2003). This paper studies the nontransparency of backbones. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values, aS, of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone S is intractable. Further, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency.

We show that the counting class LWPP remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., $$\rm PP^{Legitimate Deck} = PP$$ ) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning & Torán that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection and acceptance gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the $$\#{\rm P}$$ -based analogue of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does. Despite that nonrobustness result for a $$\#{\rm P}$$ -based class, we show that the $$\#{\rm P}$$ -based “exact counting” class $${\rm C}_{=}{\rm P}$$ remains unchanged even if one allows a polynomial number of target values for the number of accepting paths of the machine.

We discuss the connection between computational social choice (comsoc) and computational complexity. We stress the work so far on, and urge continued focus on, two less-recognized aspects of this connection. Firstly, this is very much a two-way street: Everyone knows complexity classification is used in comsoc, but we also highlight benefits to complexity that have arisen from its use in comsoc. Secondly, more subtle, less-known complexity tools often can be very productively used in comsoc.

A backbone of a boolean formula F is a collection S of its variables for which there is a unique partial assignment aS such that F[aS] is satisfiable (Monasson et al. 1999; Williams, Gomes, and Selman 2003). This paper studies the nontransparency of backbones. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values, aS, of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone S is intractable. Further, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency.

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates---single-peaked preferences---those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems---including those for Kemeny and Llull elections---fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Theta-two-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.

Scoring systems are an extremely important class of election systems. A length-m (so-called) scoring vector applies only to m-candidate elections. To handle general elections, one must use a family of vectors, one per length. The most elegant approach to making sure such families are "family-like'' is the recently introduced notion of (polynomial-time uniform) pure scoring rules, where each scoring vector is obtained from its precursor by adding one new coefficient. We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k<=3, k-veto with k<=2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a "hybrid" of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models for defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be "w.l.o.g." in fact do lose generality.

Many electoral bribery, control, and manipulation problems (which we will refer to in general as "manipulative actions" problems) are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked (i.e., is polarized along some axis/issue). However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend to merely be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates, for various notions of nearness and various election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to NP-hardness, but we also provide many instances where a reasonable number of mavericks can be tolerated without increasing the manipulative-action complexity.

In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections---attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks. By constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. This paper shows that for voters who follow the most central political-science model of electorates — single-peaked preferences — those protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we show that NP-hard bribery problems — including those for Kemeny and Llull elections- — fall to polynomial time. By using single-peaked preferences to simplify combinatorial partition challenges, we show that NP-hard partition-of-voters problems fall to polynomial time. We furthermore show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θ2p-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-hardness shields, and recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-hardness results on manipulation and control evaporate.

We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the election’s winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.

Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Constructive control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate's victory. An election system in which an agent can sometimes affect the result and it can be determined in polynomial time on which inputs the agent can succeed is said to be vulnerable to the given type of control. An election system in which an agent can sometimes affect the result, yet in which it is NP-hard to recognize the inputs on which the agent can succeed, is said to be resistant to the given type of control. Aside from election systems with an NP-hard winner problem, the only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. This paper studies a parameterized version of Copeland voting, denoted by Copeland^\alpha, where the parameter \alpha is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. In every previously studied constructive or destructive control scenario, we determine which of resistance or vulnerability holds for Copeland^\alpha for each rational \alpha, 0 \leq \alpha \leq 1. In particular, we prove that Copeland^{0.5}, the system commonly referred to as ``Copeland voting,'' provides full resistance to constructive control, and we prove the same for Copeland^\alpha, for all rational \alpha, 0 < \alpha < 1. Among systems with a polynomial-time winner problem, Copeland voting is the first natural election system proven to have full resistance to constructive control. In addition, we prove that both Copeland^0 and Copeland^1 (interestingly, Copeland^1 is an election system developed by the thirteenth-century mystic Llull) are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational \alpha, 0 \leq \alpha \leq 1, Copeland^\alpha voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^\alpha. We also study Copeland^\alpha elections under more flexible models such as microbribery and extended control, we integrate the potential irrationality of voter preferences into many of our results, and we prove our results in both the unique-winner model and the nonunique-winner model. Our vulnerability results for microbribery are proven via a novel technique involving min-cost network flow.

Given a p‐order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if $(x, y) \in A$, then $|x|$ is polynomially bounded by $|y|$), an interval size function of A returns, for each string x in the universe, the number of strings in the interval between strings $b(x)$ and $t(x)$ (with respect to A), where $b(x)$ and $t(x)$ are functions that are polynomial‐time computable in the length of x. By choosing sets of interval size functions based on feasibility requirements for their underlying p‐orders, we obtain new characterizations of complexity classes. We prove that the set of all interval size functions whose underlying p‐orders are polynomial‐time decidable is exactly #P. We show that the interval size functions for orders with polynomial‐time adjacency checks are closely related to the class FPSPACE(poly). Indeed, FPSPACE(poly) is exactly the class of all nonnegative functions that are an interval size function minus a polynomial‐time computable function. We study two important functions in relation to interval size functions. The function #DIV maps each natural number n to the number of nontrivial divisors of n. We show that #DIV is an interval size function of a polynomial‐time decidable partial p‐order with polynomial‐time adjacency checks. The function #MONSAT maps each monotone boolean formula F to the number of satisfying assignments of F. We show that #MONSAT is an interval size function of a polynomial‐time decidable total p‐order with polynomial‐time adjacency checks. Finally, we explore the related notion of cluster computation.

The top part of Figure 1.1 shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same level. This is a standard "upward translation of equality" that has been known for over a decade. The issue of whether these hierarchies can translate equality downwards has proven vastly more challenging. In particular, with regard to Figure 1.1, consider the following claim: \[ \psigkmtt = \psigkmponett \implies \diffmsigk = \codiffmsigk = \bh(\sigmak). (*) \] Until recently, it was not known whether (*) ever held, except for the degenerate cases m = 0 and k = 0. Then Hemaspaandra, Hemaspaandra, and Hempel [SIAM J. Comput., 28 (1999), pp. 383--393] proved that (*) holds for all m, for k > 2. Buhrman and Fortnow [J. Comput. System Sci., 59 (1999), pp. 182--199] then showed that, when k = 2, (*) holds for the case m = 1. In this paper, we prove that for the case k = 2, (*) holds for all values of m. Since there is an oracle relative to which "for k = 1, (*) holds for all m" fails (see Buhrman and Fortnow), our achievement of the k = 2 case cannot be strengthened to k = 1 by any relativizable proof technique. The new downward translation we obtain also tightens the collapse in the polynomial hierarchy implied by a collapse in the bounded-query hierarchy of the second level of the polynomial hierarchy.

The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets---i.e., the amount of Karp--Lipton advice needed for polynomial-time machines to recognize them in general---the best current upper bound is quadratic [K. Ko, J. Comput. System Sci., 26 (1983), pp. 209--221] and the best current lower bound is linear [L. Hemaspaandra and L. Torenvliet, Theoret. Comput. Sci., 154 (1996), pp. 367--377]. We prove that every associatively P-selective set is commutatively, associatively P-selective. Using this, we establish an algebraic sufficient condition for the P-selective sets to have a linear upper bound (which thus would match the existing lower bound) on their deterministic advice complexity: If all P-selective sets are associatively P-selective, then the deterministic advice complexity of the P-selective sets is linear. The weakest previously known sufficient condition was P = NP. We also establish related results for algebraic properties of, and advice complexity of, the nondeterministically selective sets.

Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan (1997) initiated the search for complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard, and that a number of closely related problems are SPP-hard. The present paper studies whether their UP-hardness result itself can be improved to SPP-hardness. We show that their UP-hardness result cannot be strengthened to SPP-hardness unless unlikely complexity class containments hold. Nonetheless, we prove that every P-constructibly bi-infinite counting property of circuits is SPP-hard. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.

We establish a condition necessary and sufficient for the existence of one-way permutations: One-way permutations exist if and only if there exist total one-one one-way functions whose range is P-rankable.

Rabi and Sherman presented novel digital signature and unauthenticated secret-key agreement protocols, developed by themselves and by Rivest and Sherman. These protocols use strong, total, commutative (in the case of multiparty secret-key agreement), associative one-way functions as their key building blocks. Although Rabi and Sherman did prove that associative one-way functions exist if P≠NP, they left as an open question whether any natural complexity-theoretic assumption is sufficient to ensure the existence of strong, total, commutative, associative one-way functions. In this paper, we prove that if P≠NP then strong, total, commutative, associative one-way functions exist.

Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the polynomial hierarchy. In particular, we prove that, for k > 2, if ${\rm P}^{\Sigma^p_k[1]} = {\rm P}^{\Sigma^p_k[2]}$ then $\Sigma^p_k = \Pi^p_k = {\rm PH}$. We extend this to obtain a more general downward collapse result.

We study the effect of queryorder on computational power and show that ${\rm P}^{{\rm BH}_j[1]:{\rm BH}_k[1]}$\allowbreak---the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by one query to the kth level of the boolean hierarchy---equals ${\rm R}_{{j+2k-1}{\scriptsize\mbox{-tt}}}^{p}({\rm NP})$ if j is even and k is odd and equals ${\rm R}_{{j+2k}{\scriptsize\mbox{-tt}}}^{p}({\rm NP})$ otherwise. Thus unless the polynomial hierarchy collapses it holds that, for each $1\leq j \leq k$, ${\rm P}^{{\rm BH}_j[1]:{\rm BH}_k[1]} = {\rm P}^{{\rm BH}_k[1]:{\rm BH}_j [1]} \iff (j=k) \lor (j\mbox{ is even}\, \land k=j+1)$. We extend our analysis to apply to more general query classes.

We prove that the join of two sets may actually fall into a lower level of the extended low hierarchy than either of the sets. In particular, there exist sets that are not in the second level of the extended low hierarchy, EL2, yet their join is in EL2. That is, in terms of extended lowness, the join operator can lower complexity. Since in a strong intuitive sense the join does not lower complexity, our result suggests that the extended low hierarchy is unnatural as a complexity measure. We also study the closure properties of EL2 and prove that EL2 is not closed under certain Boolean operations. To this end, we establish the first known (and optimal) EL2 lower bounds for certain notions generalizing P-selectivity, which may be regarded as an interesting result in its own right.

In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner—a candidate who beats all other candidates in pairwise majority-rule elections. Bartholdi, Tovey, and Trick provided a lower bound—NP-hardness—on the computational complexity of determining the election winner in Carroll's system. We provide a stronger lower bound and an upper bound that matches our lower bound. In particular, determining the winner in Carroll's system is complete for parallel access to NP, that is, it is complete for Theta_ 2 p for which it becomes the most natural complete problem known. It follows that determining the winner in Carroll's elections is not NP-complete unless the polynomial hierarchy collapses.

Cai and Furst proved that every PSPACE language can be solved via a large number of identical simple tasks, each of which is provided with the original input, its own unique task number, and at most three bits of output from the previous task. In the Cai–Furst model, the tasks are required to be run in the order specified by the task numbers. To study the extent to which the Cai–Furst PSPACE result is due to this strict scheduling, we remove their ordering restriction, allowing tasks to execute in any serial order. That is, we study the extent to which complex tasks can be decomposed into large numbers of simple tasks that can be scheduled arbitrarily. We provide upper bounds on the complexity of the sets thus accepted. Our bounds suggest that Cai and Furst's surprising PSPACE result is due in large part to the fixed order of their task execution. In fact, our bounds suggest the possibility that even relatively low levels of the polynomial hierarchy cannot be accepted via large numbers of simple tasks that can be scheduled arbitrarily. However, adding randomization recaptures the polynomial hierarchy. The entire polynomial hierarchy can be accepted by large numbers of arbitrarily scheduled probabilistic tasks passing only a single bit of information between successive tasks (and using J. Simon's “exact counting” acceptance mechanism). In fact, we show that the class of languages so accepted is exactly NPPP.

Threshold machines are Turing machines whose acceptance is determined by what portion of the machine's computation paths are accepting paths. Probabilistic machines are Turing machines whose acceptance is determined by the probability weight of the machine's accepting computation paths. In 1975, Simon proved that for unbounded-error polynomial-time machines these two notions yield the same class, PP\@. Perhaps because Simon's result seemed to collapse the threshold and probabilistic modes of computation, the relationship between threshold and probabilistic computing for the case of bounded error has remained unexplored. In this paper, we compare the bounded-error probabilistic class BPP with the analogous threshold class, $\bpppath$, and, more generally, we study the structural properties of $\bpppath$. We prove that $\rm BPP_{path}$ contains both $\np^{\bpp}$ and $\p^{\rm NP[\log]}$ and that $\rm BPP_{path}$ is contained in $\p^{{\rm \Sigma}_2^p[\log]}$, $\rm BPP^{NP}$, and PP\@. We conclude that, unless the polynomial hierarchy collapses, bounded-error threshold computation is strictly more powerful than bounded-error probabilistic computation. We also consider the natural notion of secure access to a database: an adversary who watches the queries should gain no information about the input other than perhaps its length. We show for both $\bpp$ and $\bpppath$ that if there is any database for which this formalization of security differs from the security given by oblivious database access, then $\p\neq \pspace$\@. It follows that if any set lacking small circuits can be securely accepted, then $\p\neq\pspace$.

It is known that for any class $\tweak{\cal C}$ closed under union and intersection, the Boolean closure of ${\cal C}$, the Boolean hierarchy over $\tweak{\cal C}$, and the symmetric difference hierarchy over $\tweak{\cal C}$ all are equal. We prove that these equalities hold for any complexity class closed under intersection; in particular, they thus hold for unambiguous polynomial time (UP). In contrast to the NP case, we prove that the Hausdorff hierarchy and the nested difference hierarchy over UP both fail to capture the Boolean closure of UP in some relativized worlds. Karp and Lipton proved that if nondeterministic polynomial time has sparse Turing-complete sets, then the polynomial hierarchy collapses. We establish the first consequences from the assumption that unambiguous polynomial time has sparse Turing-complete sets: (a) $\up \seq \mbox{Low}_2$, where $\mbox{Low}_2$ is the second level of the low hierarchy, and (b) each level of the unambiguous polynomial hierarchy is contained one level lower in the promise unambiguous polynomial hierarchy than is otherwise known to be the case.

Is there an NP function that, when given a satisfiable formula as input, outputs one satisfying assignment uniquely? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of assignments? We show that if there is such a nondeterministic function, then the polynomial hierarchy collapses to ${\text{ZPP}}^{{\text{NP}}} $ (and thus, in particular, to ${\text{NP}}^{{\text{NP}}} $). Because the existence of such a function is known to be equivalent to the statement “every NP function has an NP refinement with unique outputs,” our result provides the strongest evidence yet that NP functions cannot be refined. We prove our result via a result of independent interest. We say that a set A is NPSV-selective (NPMV-selective) if there is a 2-ary partial NP function with unique values (a 2-ary partial NP function) that decides which of its inputs (if any) is “more likely” to belong to A; this is a nondeterministic analog of the recursion-theoretic notion of the semirecursive sets and the extant complexity-theoretic notion of P-selectivity. Our hierarchy-collapse result follows by combining the easy observation that every set in NP is NPMV-selective with the following result: If $A \in {\text{NP}}$ is NPSV-selective, then $A \in {{({\text{NP}} \cap {\text{coNP}})} / {{\text{poly}}}}$. Relatedly, we prove that if $A \in {\text{NP}}$ is NPSV-selective, then A is ${\text{Low}}_2 $. We prove that the polynomial hierarchy collapses even further, namely to NP, if all coNP sets are NPMV-selective. This follows from a more general result we prove: Every self-reducible NPMV-selective set is in NP.

A set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for the set — an algorithm that given any two strings decides which is “more likely” to be in the set. This paper establishes a strict hierarchy among the various reductions and equivalences to P-selective sets.

Ko proved that the P-selective sets are in the advice class P/quadratic, and Hemaspaandra, Naik, Ogihara, and Selman showed that they are in PP/linear. We strengthen the latter result by establishing that the P-selective sets are in NP/linear ∩ coNP/linear. We show linear advice to be optimal.

"Downward separation" results show that when small classes collapse, larger ones also collapse. For example, Stockmeyer proved that if P=NP, then the polynomial hierarchy collapses to P, and this result itself holds in every relativized world. In contrast, we construct a relativized world in which the exponential-time limited nondeterminism hierarchy does not display such behavior: its tower levels collapse yet its upper levels separate. "Upward separation" results typically show that polynomial-time classes differ on sparse or tally sets if and only if their exponential analogs differ. For example, Hartmanis, Immerman, and Sewelson proved that NP-P contains sparse sets if and only if E ≠ NE, and this result itself holds in every relativized world. In contrast, we construct relativized worlds in which probabilistic classes do not display upward separation, e.g., a world A in which BPPA-PA contains sparse sets even though BPEA = EA. We also construct a relativized world B in which NPB has PB-immune sparse sets yet NEB is not EB-immune. On the other hand, we provide a structural sufficient condition for upward separation.

This paper explores two generalizations within NP of self-reducibility: Arvind and Biswas’s kernel constructibility and Khadilkar and Biswas’s committability. Informally stated, kernel constructible sets have (generalized) self reductions that are easy to check, though perhaps hard to compute, and committable sets are those sets for which the potential correctness of a partial proof of set membership can be checked via a query to the same set (that is, via a self-reduction). We study these two notions of generalized self reducibility on nondense sets. We show that sparse kernel constructible sets are of low complexity, extend previous results showing that sparse committable sets are of low complexity, and provide structural evidence of interest in its own right—namely, that if all sparse disjunctively self-reducible sets are in P then ${\text{FewP}} \cap {\text{FewP}}$ is not P-bi-immune—that our extension is unlikely to be extended further. We obtain density-based sufficient conditions for kernel-constructibility: sets whose complements are captured by nondense sets are perforce kernel constructible. Using sparse languages and Kolmogorov complexity theory as tools, we argue that kernel constructibility is orthogonal to standard notions of complexity.

The P-selective sets (Selman, 1979) are those sets for which there is a polynomial-time algorithm that, given any two strings, determines which is “more likely” to belong to the set: if either of the strings is in the set, the algorithm chooses one that is in the set. We prove that, for each k, the k-ary Boolean connectives under which the P-selective sets are closed are exactly those that are either completely degenerate or almost-completely degenerate. We determine the complexity of the index set of the r.e. P-selective sets — ∑30-complete.

The low hierarchy in NP [27] and the extended low hierarchy [8] have been useful in

For various polynomial-time reducibilities r, this paper asks whether being r-reducible to a sparse set is a broader notion than being r-equivalent to a sparse set. Although distinguishing equivalence and reducibility to sparse sets, for many-one or 1-truth-table reductions, would imply that $P \ne NP$, this paper shows that for k-truth-table reductions, $k \geq 2$, equivalence and reducibility to sparse sets provably differ. Though Gavaldà and Watanabe have shown that, for any polynomial-time computable unbounded function $f( \cdot )$, some sets $f(n)$-truth-table reducible to sparse sets are not even Turing equivalent to sparse sets, this paper shows that extending their result to the 2-truth-table case would provide a proof that $P\ne NP$. Additionally, this paper studies the relative power of different notions of reducibility, and proves that disjunctive and conjunctive truth-table reductions to sparse sets are surprisingly powerful, refuting a conjecture of Ko.

Long and Selman (1986) proved that, for most familiar pairs of complexity classes, separating the classes with a tally oracle is no easier than truly separating the classes. Refuting a claim in the literature, we prove for the first time that for many familiar pairs of complexity classes, separating the classes with a tally oracle is easier than truly separating the classes.

We show that probabilistic polynomial time (PP) is closed under polynomial-time parity reductions. As corollaries, we show that several complexity classes are contained in PP.

In this paper a new property of sets, near-testability, is introduced. A set S is near-testable$(S \in NT)$ if the membership relation for all immediate neighbors is polynomially computable; i.e., if the function $t(x) = \chi _S (x) + \chi _S (x - 1)(\bmod 2)$ is polynomially computable. The near-testable sets form a subclass of the class $ \oplus P$ (parity polynomial time), introduced by Papadimitriou and Zachos, and Goldschlager and Parberry. $ \oplus P$ has a complete set $ \oplus SAT$ that has recently been shown by Valiant and Vazirani to be hard for $NP$ under randomized polynomial-time reductions. It is proved that there is a uniform polynomial one-one reduction that takes every set in $ \oplus P$ to a near-testable set, and it is shown that the image of $ \oplus SAT$ under this reduction (which we call $NTSAT$) is polynomially isomorphic to $ \oplus SAT$. As corollaries it is shown that $NTSAT$ is complete for both $NT$ and for $ \oplus SAT$, that $NTSAT$ is hard for $NP$ under randomized polynomial-time reductions, and that the existence of one-way functions implies the existence of sets that are near-testable but not polynomially decidable. It is then asked whether near-testability is preserved under p-isomorphisms. This leads to a generalization, $NT^ * $, of $NT$ similar to those introduced by Meyer and Paterson and by Ko for self-reducible sets. With this more general definition, $NT^ * $ is shown to be closed under polynomial-time isomorphisms while remaining a subclass of $ \oplus P$. It is conjectured that it is a proper subclass. In fact it is shown that, relative to a random oracle, the containments $P \subseteq NT \subseteq NT^ * \subseteq \oplus P$ are proper with probability one. It is also shown that, relative to a random oracle, with probability one $NT$ and $NT^ * $ are incomparable with both $NP$ and with $coNP$. Finally, the effects that the distribution and density of elements have on the complexity of near-testable sets are considered.

This paper completely characterizes the complexity of implicit membership testing in terms of the well-known complexity class OptP, optimization polynomial time, and concludes that many complex sets have polynomial-time implicit membership tests.

The One-way Conjecture states that the existence of nonisomorphic NP-complete sets implies the existence of one-way functions. This paper gives a relativized counterexample to the conjecture by constructing a relativized world that has nonisomorphic NP-complete sets, but lacks one-way functions.

Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets—including all exponential-time complete sets, all NP-complete sets yet obtained by direct construction, and the complements of all such sets—are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are ⪯p1si-self-reducible are polynomially enumerable by iterations, and that all recursive sets that are p1si-self-reducible are bi-enumerable. We also show that when the ⪯p1si-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no NP-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to NP. We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.

This paper completely characterizes the Θkp levels of the polynomial hierarchy in terms of Kolmogorov complexity. From the characterization, it follows that the Θkp and Δkp levels of the polynomial hierarchy are equal if and only if every Δkp language is accepted by some Δkp machine whose pronouncements (query answers) are Kolmogorov simple. Analogous results are obtained for the exponential hierarchy.

This paper structurally characterizes the complexity of ranking. A set A is (strongly) P-rankable if there is a polynomial time computable function f so that for all x, f(x) computes the number of elements of A that are lexicographically ⩽ x, i.e., the rank of x with respect to A. This is the strongest of three notions of P-ranking we consider in this paper. We say a class C is P-rankable if all sets in C are P-rankable. Our main results show that with the same certainty with which we believe counting to be complex, and thus with at least the certainty with which we believe P ≠ NP, P has no uniform, strong, weak, or enumerative ranking functions. We show that: • P and NP are equally likely to be P-rankable, i.e., P is P-rankable if and only if NP is P-rankable. • P is P-rankable if and only if P = P#P. This extends work of Blum, Goldberg, and Sipser. • Even the two weaker notions of P-ranking that we study are hard if P ≠ P#P. •If P has small ranking circuits, then it has small ranking circuits of relatively low complexity. • If P has small ranking circuits then counting is in the polynomial hierarchy, i.e., P#P ⊆Σ2p = PH. • P/poly has small ranking circuits if and only if P#P/poly = P#P/poly = P/poly. • If P is P-rankable, then P/poly has small ranking circuits. This links the ranking complexity of uniform and nonuniform classes. • The ranks of some strings in easy sets are of high relative time-bounded Kolmogorov complexity unless P = P#P. It follows that even a type of approximate ranking, enumerative ranking, is hard unless P = P#P. • The complexity of generating “the next largest” element in a set has clear structural characterizations. In particular, (1) we can efficiently find some element of polynomial hierarchy sets at an input length if and only if P = PH ∩ P/poly, and (2) we can efficiently find some element of a polynomial hierarchy set greater than an input if and only if all sets in NP have infinite P-printable subsets.

A robust machine is a machine that maintains some computational property for every oracle. In this paper we study robustly complementary, robustly categorical, robustly ∑∗-accepting, and robustly ∑∗-spanning machines. We prove that robust machines squander their powerful nondeterministic oracle access in all relativizations—relative to any oracle A, their languages and properties can be computed in PNPA.

An n -variable Boolean formula may have anywhere from 0 to 2 n satisfying assignments. Can a polynomial-time machine, given such a formula, reduce this exponential number of possibilities to a small number of possibilities? We call such a machine an enumerator and prove that if there is a good polynomial-time enumerator for #P (i.e., one where for every Boolean formula f , the small set has at most O (| f | 1− ε ) numbers), then P = NP = P # P and probabilistic polynomial time equals polynomial time. Furthermore, we show that #P polynomial-time Turing reduces to enumerating #P.

Composed of the levels E (i.e., ∪c DTIME[2cn]), NE, PNE, NPNE, etc., the strong exponential hierarchy is an exponential-time analogue of the polynomial-time hierarchy. This paper shows that the strong exponential hierarchy collapses to PNE, its Δ2 level. E ≠ pNE = NPNE ∪ NPNPNE ∪ … The proof stresses the use of partial census information and the exploitation of nondeterminism. Extending these techniques, we derive new quantitative relativization results: if the weak exponential hierarchy's ΔJ + 1 and Σj + 1 levels, respectively EΣjp and NEΣjp, do separate, this is due to the large number of queries NE makes to its Σjp database. Our techniques provide a successful method of proving the collapse of certain complexity classes.

The Boolean Hierarchy I: Structural Properties [J. Cai et al., SIAM J. Comput ., 17 (1988), pp. 1232–252] explores the structure of the boolean hierarchy, the closure of NP with respect to boolean operations. This paper uses the boolean hierarchy as a tool with which to extend and explain three important results in structural complexity theory. (1) Hartmanis, Immerman, and Sewelson [ Proc. 15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391] showed that ${\text{E}} = {\text{NE}}$ if and only if ${\text{NP}} - {\text{P}}$ contains no sparse sets. In this paper it is shown that this reflects a behavior of the boolean hierarchy. When ${\text{E}} = {\text{NE}}$, sparse sets fall from alternate levels of the boolean hierarchy (Fig. 2(a)). Furthermore, it is shown that capturable sets (i.e., subsets of sparse NP sets) are banished from the boolean hierarchy when ${\text{E}} = {\text{NE}}:{\text{E}} = {\text{NE}}$ implies that ${\text{BH}} - {\text{P}}$ has no capturable sets. (2) Counting classes are natural candidates as complete languages for the levels of the boolean hierarchy. The authors show that in relativized worlds counting classes are not complete for the levels of the boolean hierarchy. Relatedly, the work of Blass and Gurevich [Inform, and Control, 55 (1982), pp. 80–88] is extended and it is concluded that counting classes are weak in some relativized worlds. (3) Karp and Lipton [Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309] showed that if NP has a sparse oracle (i.e., if there is a sparse set S so ${\text{NP}} \subseteq {\text{P}}^S $; equivalently, if NP has small circuits), then the polynomial hierarchy collapses to ${\text{NP}}^{{\text{NP}}} $. The authors demonstrate that this cannot be much improved. There is a relativized world in which NP has a sparse oracle, yet the boolean hierarchy is infinite. Thus no proof that relativizes can show: NP has .a sparse oracle implies that the polynomial hierarchy equals the boolean hierarchy. The results of this paper present new ideas and techniques, and put previous results about NP and ${\text{D}}^{\text{P}} $ in a richer perspective. Throughout, the emphasis is on the structure of the boolean hierarchy and its relations with more common classes.

In this paper, we study the complexity of sets formed by boolean operations (union, intersection, and complement) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together these form the boolean hierarchy. We present many results about the structure of the boolean hierarchy: separation and immunity results, natural complete languages, and structural asymmetries between complementary classes. We show that in some relativized worlds the boolean hierarchy is infinite, and that for every k there is a relativized world in which the boolean hierarchy extends exactly k levels. We prove natural languages, variations of VERTEX COVER, complete for the various levels of the boolean hierarchy. We show the following structural asymmetry: though no set in the boolean hierarchy is ${\text{D}}^{\text{P}} $-immune, there is a relativized world in which the boolean hierarchy contains ${\text{coD}}^{\text{P}} $-immune sets. Thus, this paper explores the structural properties of the boolean hierarchy. A companion paper [J. Cai et al., SIAM J. Comput. 18 (1989), to appear] uses the boolean hierarchy to extend known results on small circuits [R. Karp and R. Lipton, Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309], sparse sets in NP-P [J. Hartmanis, N. Immerman, and V. Sewelson, Proc.15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391], and counting classes [A. Blass and Y. Gurevich, Inform. and Control, 55 (1982), pp. 80–88].

This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of their machines. Counting classes, probabilistic classes, and intersection classes often lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for which UPA has no complete languages and other relativizations for which PB≠UPB≠NPB and UPB has complete languages. Among other results we show that (1) UP has complete languages if and only if there exists a set R in P of Boolean formulas, each having at most one satisfying assignment so that SAT∩R is complete for UP. (2) P ≠ UP if and only if there exists a set S in P of Boolean formulas, each having at most one satisfying assignment, such that S ∩ SAT is not in P. (3) P ≠ UP ∩ coUP if and only if there exists a set S in P of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas in S. We suggest the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic class BPP. There is a relativized word where BPPA has no complete languages. If BPP has complete languages, then it has a complete language of the form B ∩ Majority, where B ϵ P and Majority = {f¦f is true for at least half of all assignments} is the canonical PP-complete set.

The polynomial hierarchy, composed of the levels P, NP, PNP, NPNP, etc., plays a central role in classifying the complexity of feasible computations. It is not known whether the polynomial hierarchy collapses.

Simulated annealing is a computational heuristic for obtaining approximate solutions to combinatorial optimization problems. It is used to construct good source codes, error-correcting codes, and spherical codes. For certain sets of parameters codes that are better than any other known in the literature are found.