A common approach used to efficiently solve problems is to develop sequential greedy algorithms. Such algorithms are easily implemented and provide polynomial-time solutions. A natural next step towards building more efficient algorithms is to develop parallel algorithms. However, sequential greedy algorithms seldom lead to parallel algorithms; computing the output of sequential greedy algorithms is often shown to be P-complete and thus "inherently sequential" under the commonly believed assumption that P ≠ NC, where NC is the class of efficiently parallelizable problems. Greedy edge-induced (resp., vertex-induced) subgraph building algorithms for a property π operate like so. For given graph G, a subgraph of G is built by adding edges (resp., vertices) in a given order unless the inclusion of said edge (resp., vertex) would contradict property π within the subgraph. For vertex-induced greedy subgraph building algorithms, Miyano (1989) provided a comprehensive result: computing the subgraph output by such algorithms is typically P-complete. In contrast, little is known about its edge-induced counterpart. In this work, we analyze the complexity of the Lexicographically First Maximal H-free edge-induced subgraph problem, which is concerned with computing the output of greedy edge-induced subgraph building algorithms where the property π is that the subgraph is H-free. This gives us insight into the largely overlooked edge-induced versions of greedy subgraph building algorithms and into how graph structure influences the complexity of such algorithms. Our primary contribution is a trichotomy theorem for the cases where H is a tree: we show that the problem is either P-complete, CC-complete, or in L, where CC is the class of problems solvable using comparator circuits - or, equivalently, problems reducible to the lexicographically first maximal matching problem. In contrast, the vertex-induced version is either P-complete or in L, and such dichotomy theorems are much more common. Our additional technical contributions include: (1) an iterative approach to hardness proofs by focusing on a set of "smaller" problems and extending hardness via simple constructions, and (2) expanding on the scarce set of problems known to be CC-complete.

Formal methods in computer science aim to increase reliability and robustness of software or hardware designs. Unfortunately, formal methods are typically only accessible to specialized professionals. One of the reasons of this limited accessibility is the lack of exposure to formal methods in undergraduate education, even for computer science majors. We aim to rectify this by developing self-contained, turnkey Jupyter notebooks that will introduce students to SMT solvers, an important tool in formal methods, to solve problems related to their courses. This allows students to explore formal methods while not distracting from their coursework. In this work, we report on four Jupyter notebooks that we developed and deployed for this purpose.

Approval-Based Committee (ABC) rules are an important tool for choosing a fair set of candidates when given the preferences of a collection of voters. Though finding a winning committee for many ABC rules is NP-hard, natural variations for these rules with polynomial-time algorithms exist. The recently introduced Method of Equal Shares, an important ABC rule with desirable properties, is also computable in polynomial time. However, when working with very large elections, polynomial time is not enough and parallelization may be necessary. We show that computing a winning committee using these polynomial-time ABC rules (including the Method of Equal Shares) is P-hard, thus showing they cannot be parallelized. In contrast, we show that finding a winning committee can be parallelized when the votes are single-peaked or single-crossing for the important ABC rule Chamberlin-Courant.

Abstract Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighbor instances, that is, instances with one local modification? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems, most notably, graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, colorability and vertex cover. For example, we show that it is $$\text {NP}$$ NP -hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in $$\text {P}$$ P . We observe that vertex cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for $$\text {DP}$$ DP (differences of $$\text {NP}$$ NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For vertex cover, we show that recognizing $$\beta $$ β -vertex-critical graphs is complete for $$\Theta _2^\text {p}$$ Θ 2 p (parallel access to $$\text {NP}$$ NP ), obtaining the first completeness result for a criticality problem for this class.

Determining the complexity of election attack problems is a major research direction in the computational study of voting problems. The paper “Towards completing the puzzle: complexity of control by replacing, adding, and deleting candidates or voters” by Erdélyi et al. (JAAMAS 2021) provides a comprehensive study of the complexity of control problems. The sole open problem is constructive control by replacing voters for 2-Approval. We show that this case is in P, strengthening the recent RP (randomized polynomial-time) upper bound due to Fitzsimmons and Hemaspaandra (IJCAI 2022). We show this by transforming 2-Approval CCRV to weighted matching. We also use this approach to show that priced bribery for 2-Veto elections is in P. With this result, and the accompanying (unsurprising) result that priced bribery for 3-Veto elections is NP-complete, this settles the complexity for k-Approval and k-Veto standard control and bribery cases.

Introductory assignments in CS Theory ask students to construct instances of various computational models (such as finite automata, regular expressions, context-free grammars, or push-down automata) for a given language. Verifying the correctness of their model instance is challenging for beginner CS Theory students since the concepts are abstract and there are infinitely many possible inputs. The popular JFLAP software allows students to visualize the running of their instance on a specific input. We recently developed a server extension to JFLAP which checks whether a student's instance is equivalent to the instructor's solution and, if not, it returns a "witness string,'' an input string on which the student's construction and the correct solution differ.

The first step in classifying the complexity of an NP problem is typically showing the problem in P or NP-complete. This has been a successful first step for many problems, including voting problems. However, in this paper we show that this may not always be the best first step. We consider the problem of constructive control by replacing voters (CCRV) introduced by Loreggia et al. [2015, https://dl.acm.org/doi/10.5555/2772879.2773411] for the scoring rule First-Last, which is defined by (1, 0, ..., 0, -1). We show that this problem is equivalent to Exact Perfect Bipartite Matching, and so CCRV for First-Last can be determined in random polynomial time. So on the one hand, if CCRV for First-Last is NP-complete then RP = NP, which is extremely unlikely. On the other hand, showing that CCRV for First-Last is in P would also show that Exact Perfect Bipartite Matching is in P, which would solve a well-studied 40-year-old open problem. Considering RP as an option for classifying problems can also help classify problems that until now had escaped classification. For example, the sole open problem in the comprehensive table from Erdélyi et al. [2021, https://doi.org/10.1007/s10458-021-09523-9] is CCRV for 2-Approval. We show that this problem is in RP, and thus easy since it is widely assumed that P = RP.

Computing theory is often perceived as challenging by students, and verifying the correctness of a student's automaton or grammar is time-consuming for instructors. Aiming to provide benefits to both students and instructors, we designed an automated feedback tool for assignments where students construct automata or grammars. Our tool, built as an extension to the widely popular JFLAP software, determines if a submission is correct, and for incorrect submissions it provides a "witness" string demonstrating the incorrectness.

Graph parameters such as the clique number and the chromatic number are central in many areas, ranging from computer networks to linguistics to computational neuroscience to social networks. In particular, the chromatic number of a graph can be applied in solving practical tasks as diverse as pattern matching, scheduling jobs to machines, allocating registers in compiler optimization, and even solving Sudoku puzzles. Typically, however, the underlying graphs are subject to (often minor) changes. To make these applications of graph parameters robust, it is important to know which graphs are stable in the sense that adding or deleting single edges or vertices does not change them. We initiate the study of stability of graphs in terms of their computational complexity. We show for various central graph parameters that deciding the stability of a given graph is complete for Θ2p, a well-known complexity class in the second level of the polynomial hierarchy.

The computational study of election problems generally focuses on questions related to the winner or set of winners of an election. But social preference functions such as Kemeny rule output a full ranking of the candidates (a consensus). We study the complexity of consensus-related questions, with a particular focus on Kemeny and its qualitative version Slater. The simplest of these questions is the problem of determining whether a ranking is a consensus, and we show that this problem is coNP-complete. We also study the natural question of the complexity of manipulative actions that have a specific consensus as a goal. Though determining whether a ranking is a Kemeny consensus is hard, the optimal action for manipulators is to simply vote their desired consensus. We provide evidence that this simplicity is caused by the combination of election system (Kemeny), manipulative action (manipulation), and manipulative goal (consensus). In the process we provide the first completeness results at the second level of the polynomial hierarchy for electoral manipulation and for optimal solution recognition.

Computing theory analyzes abstract computational models to rigorously study the computational difficulty of various problems. Introductory computing theory can be challenging for undergraduate students, and the overarching goal of our research is to help students learn these computational models. The most common pedagogical tool for interacting with these models is the Java Formal Languages and Automata Package (JFLAP). We developed a JFLAP server extension, which accepts homework submissions from students, evaluates the submission as correct or incorrect, and provides a witness string when the submission is incorrect. Our extension currently provides witness feedback for deterministic finite automata, nondeterministic finite automata, regular expressions, context-free grammars, and pushdown automata.

Voting rules based on scores generally determine the winner by computing the score of each candidate and the winner is the candidate with the best score. It would be natural to expect that computing the winner of an election is at least as hard as computing the score of a candidate. We show that this is not always the case. In particular, we show that for Young elections for dichotomous preferences the winner problem is easy, while determining the score of a candidate is hard. This complexity behavior has not been seen before and is unusual. The easiness of the winner problem for dichotomous Young crucially uses the fact that dichotomous preferences guarantee the transitivity of the majority relation. In addition to dichotomous preferences we also look at single-peaked preferences, the most well-studied domain restriction that guarantees the transitivity of the majority relation. We show that for the three major hard voting rules and their natural variants, dichotomous Young is the only case where winner is easy and score is hard. This also solves an open question from Lackner and Peters (AAAI 2017), by providing a polynomial-time algorithm for Dodgson score for single-peaked electorates.

Computing theory is an important part of computer science education, introducing students to computational models of increasing power to study possibilities and limitations of computation. The subject is, however, very abstract and mathematical, and students often struggle with it. Students must master various computational models, but there is often a lengthy delay from the time a model is introduced until a student gets feedback on their related assignment. During this time, the course has typically moved far ahead, and students become progressively more lost. To alleviate this problem, we developed a prototype of an automated feedback tool for CS theory, which extends the widely used JFLAP software. Our tool currently handles student submissions of deterministic and non-deterministic finite automata, regular expressions, context-free grammars, and push-down automata homework, where an instructor specifies the target language and the students receive immediate feedback on their submissions. Currently, for incorrect submissions, the feedback is in the form of a "witness'' string, specifying a string on which the submission fails. Beyond regular languages, our tool attempts to solve undecidable problems; fortunately, the undecidability does not occur on typical homework assignments. We are collecting preliminary evaluation data from students using the prototype tool in their course. In our future work, we will analyze the data, and we aim to produce automated partial credit (along with the witness feedback) using SAT and QBF solvers.

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.

Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.

The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the preferences of the electorate succinctly, as the distinct votes and their counts. Though the succinct representation may be exponentially smaller than the nonsuccinct, we find only one natural case where the complexity increases, in sharp contrast to the case where each voter has a weight, where the complexity usually increases.

Scoring systems are an extremely important class of election systems. We study the complexity of manipulation, constructive control by deleting voters (CCDV), and bribery for scoring systems. For manipulation, we show that for all scoring rules with a constant number of different coefficients, manipulation is in P. And we conjecture that there is no dichotomy theorem.

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.

The minimization problem for propositional formulas is an important optimization problem in the second level of the polynomial hierarchy. In general, the problem is Σ p 2-complete under Turing reductions, but restricted versions are tractable. We study the complexity of minimization for formulas in two established frameworks for restricted propositional logic: The Post framework allowing arbitrarily nested formulas over a set of Boolean connectors, and the constraint setting, allowing generalizations of CNF formulas. In the Post case, we obtain a dichotomy result: Minimization is solvable in polynomial time or coNP-hard. This result also applies to Boolean circuits. For CNF formulas, we obtain new minimization algorithms for a large class of formulas, and give strong evidence that we have covered all polynomial-time cases.

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.

Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a very general classification for a wide class of relevant logics: Many important subclasses of modal logics can be obtained by restricting the allowed models with first-order Horn formulas. We show that the satisfiability problem for each of these logics is either NP-complete or PSPACE-hard, and exhibit a simple classification criterion. Further, we prove matching PSPACE upper bounds for many of the PSPACE-hard logics.

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.

More than a quarter of a century ago, the question of the complexity of determining whether a given Boolean formula is minimal motivated Meyer and Stockmeyer to define the polynomial hierarchy. This problem (in the standard formalized version---that of Garey and Johnson) has been known for decades to be coNP-hard and in NP NP , and yet no one had even been able to establish (many-one) NP-hardness. In this paper, we show that and more: The problem in fact is (many-one) hard for parallel access to NP.

Motivated by description logics, we investigate what happens to the complexity of modal satisfiability problems if we only allow formulas built from literals, ∧, ◊, and □. Previously, the only known result was that the complexity of the satisfiability problem for K drops from PSPACE‐complete to coNP‐complete. In this paper we show that not all modal logics behave like K. In particular, we show that the complexity of the satisfiability problem with respect to frames in which each world has at least one successor drops from PSPACE‐complete to P, but that in contrast the satisfiability problem with respect to the class of frames in which each world has at most two successors remains PSPACE‐complete. As a corollary of the latter result, we also solve the open problem from the complexity classification of description logics. In the last section, we classify the complexity of the satisfiability problem for K for all other restrictions on the set of operators.

Bodlaender, Thilikos, and Yamazaki (1997) investigate the computational complexity of the problem of whether the Minimum Degree Greedy Algorithm can approximate a maximum independent set of a graph within a constant factor of r, for fixed rational r ⩾ 1. They denote this problem by Sr and prove that for each rational r ⩾ 1, Sr is coNP-hard. They also provide a PNP upper bound of Sr, leaving open the question of whether this gap between the upper and the lower bound of Sr can be closed. For the special case of r = 1, they show that S1 is even DP-hard, again leaving open the question of whether S1 can be shown to be complete for DP or some larger class such as PNP. In this note, we completely solve all the questions left open by Bodlaender et al. Our main result is that for each rational r ⩾ 1, Sr is complete for P∥NP, the class of sets solvable via parallel access to NP.

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 investigate the computational complexity of the minimization problem for Boolean formulas. Depending on the definition, these problems are trivially in /spl Sigma//sub 2//sup P/ or II/sub 2//sup P/, and these are the best upper bounds known. The only previously known lower bounds are also trivial, and are coNP lower bounds at best, thus leaving quite a large gap between the upper and lower bounds. In this paper, we prove much better lower bounds: hardness for parallel access to NP for those cases in which coNP was the best previously known lower bound, and coNP-hardness for the case in which no lower bound was previously known.

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.

We distinguish self-reducibility of a languageLwith the question of whether search reduces to decision forL. Results include: (i) If NE≠E, then there exists a setLin NP−P such that search reduces to decision forL, search doesnotnonadaptively reduce to decision forLandLis not self-reducible. (ii) If UE≠E, then there exists a languageL∈UP−P such that search nonadaptively reduces to decision for L, but L is not self-reducible. (iii) If UE∩co-UE≠E, then there is a disjunctive self-reducible languageL∈UP−P for which search doesnotnonadaptively reduce to decision. We prove that if NE⊈BPE, then there is a languageL∈NP−BPP such thatLis randomly self-reducible,notnonadaptively randomly self-reducible, andnotself-reducible. We obtain results concerning trade-offs in multiprover interactive proof systems and results that distinguish checkable languages from those that are nonadaptively checkable. Many of our results are proven by constructing p-selective sets. We obtain a p-selective set that isnot⩽Ptt-equivalent to any tally language, and we show that if P=PP, then every p-selective set is ⩽PT-equivalent to a tally language. Similarly, if P=NP, then every cheatable set is ⩽Pm-equivalent to a tally language. We construct a recursive p-selective tally set that isnotcheatable.

Polynomials over finite fields are used to show that any sparse set can conjunctively reduce to a tally set. This leads to new results and to simple proofs of known results about various classes that lie between P and P/poly.

We prove general theorems about the relationship between the complexity of multi-modal logics and the complexity of their uni-modal fragments. Halpern and Moses (1985) show that the complexity of a multi-modal logic without any interaction between the modalities may be higher than the complexity of the individual fragments. We show that under reasonable assumptions the complexity can increase only if the complexity of all the uni-modal fragments is below PSPACE. In addition, we completely characterize what happens if the complexity of all fragments is below PSPACE.>