This file contains bibliographic citations (with abstracts) for selected
papers produced at the University of Rochester. Most citations end
with a link to a PDF or (formerly) compressed postscript file.
These files are also available via anonymous ftp from
ftp.cs.rochester.edu (user anonymous, password your_name), in the
directory pub/.
Copyright on many of these papers may be owned by organizations other
than the University of Rochester, as indicated in the citations below.
For more information or for help obtaining technical
reports not available online, please contact
tr@cs.rochester.edu.
Keywords: computational social choice; bribery; Copeland elections; control; voting;.
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 [BTT92]. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate's victory [HHR07a]. An election system in which an agent can affect the result and in which recognizing the inputs on which the agent can succeed is NP-hard (polynomial-time solvable) is said to be resistant (vulnerable) 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 are highly artificial election systems created by hybridization [HHR07b]. We study 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 <= alpha <= 1. In particular, we prove that Copeland^0.5, the system commonly referred to as ``Copeland voting,'' provides full resistance to constructive control. Among the systems with a polynomial-time winner problem, this 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, the latter is an election system developed by the thirteenth-century mystic Ramon Llull) are resistant to all the standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational alpha, 0 <= alpha <= 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 and the nonunique-winner model. Our vulnerability results for microbribery are proven via a technique involving min-cost network flow.
Keywords: power index; computational complexity; #P; completeness;.
We study the complexity of the following problem: Given two weighted voting games G' and G'' that each contain a player p, in which of these games is p's power index value higher? We study this problem with respect to both the Shapley-Shubik power index [SS54] and the Banzhaf power index [Ban65,DS79]. Our main result is that for both of these power indices the problem is complete for probabilistic polynomial time (i.e., is $\pp$-complete). We apply our results to partially resolve some recently proposed problems regarding the complexity of weighted voting games. We also study the complexity of the raw Shapley-Shubik power index. Deng and Papadimitriou [DP94] showed that the raw Shapley-Shubik power index is #P-metric-complete. We strengthen this by showing that the raw Shapley-Shubik power index is many-one complete for #P. And our strengthening cannot possibly be further improved to parsimonious completeness, since we observe that, in contrast with the raw Banzhaf power index, the raw Shapley-Shubik power index is not #P-parsimonious-complete.
Keywords: data structures; approximate counting; streaming algorithms;.
We present the Bitwise Bloom Filter, a data structure for maintaining counts for a large number of items. The bitwise filter is an extension of the Bloom filter, a space-efficient data structure for storing a large set efficiently by discarding the identity of the items being held while still being able to determine whether it is in the set or not with high probability. We show how this idea can be extended to maintaining counts of items by maintaining a separate Bloom filter for every position in the bit representations of all the counts. We give both theoretical analysis of the accuracy of the Bitwise filter together with validation via experiments on real network data.
Keywords: Copeland; election manipulations; tie resolution;computational complexity;.
We study the complexity of manipulation for a family of election systems derived from Copeland voting via introducing a parameter alpha that describes how ties in head-to-head contests are valued. We show that the problem of manipulation for unweighted Copeland^alpha elections is NP-complete even if the size of the manipulating coalition is limited to two. Our result holds for all rational values of alpha such that 0 < alpha < 1 except for alpha = 1/2. We contrast our result with the fact that microbribery for Copeland^alpha is currently known to be in P exactly for alpha in {0,1/2,1} (complexity results for other values of alpha are unknown). Microbribery is a problem very closely related to manipulation. Since it is well known that manipulation via a single voter is easy for Copeland, ourresult is the first one where an election system originally known to be vulnerable to manipulation via a single voter is shown to be resistant to manipulation via a coalition of a constant number of voters. We also study the complexity of manipulation for Copeland^alpha for the case of a constant number of candidates. We show that here the exact complexity of manipulation often depends closely on the winner model as well as on the parameter alpha: Depending whether we try to make our favorite candidate a winner or a unique winner and whether alpha is 0, 1 or between these values, the problem of weighted manipulation for Copeland^alpha with three candidates is either in P or is NP-complete. Our results show that ways in which ties are treated in an election system, here Copeland voting, can be crucial to establishing complexity results for this system.
Keywords: computational social choice; bribery; Copeland elections; control;voting.
Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Faliszewski et al. [FHHR07] proved that Llull voting (which is here denoted by Copeland^1) and a variant (here denoted by Copeland^0) of Copeland voting are computationally resistant to many, yet not all, types of constructive control and that they also provide broad resistance to bribery. We study 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 Copeland elections. We establish resistance or vulnerability results, in every previously studied control scenario, for Copeland^alpha, for each rational alpha, 0 <alpha < 1. In particular, we prove that Copeland^0.5, the system commonly referred to as ``Copeland voting,'' provides full resistance to constructive control. Among the systems with a polynomial-time winner problem, this is the first natural election system proven to have full resistance to constructive control. Results on bribery and fixed-parameter tractability of bounded-case control proven for Copeland^0 and Copeland^1 in [FHHR07] are extended to Copeland^alpha for each rational alpha, 0 < alpha < 1; we also give results in more flexible models such as microbribery and extended control.
Keywords: computational choice; bribery; plurality voting; utility-based voting.
We study the concept of bribery in the situation where voters are willing to change their votes as we ask them, but where their prices depend on the nature of the change we request. Our model is an extension of the one of Faliszewski et al. [FHH06], where each voter has a single price for any change we may ask for. We show polynomial-time algorithms for our version of bribery for a broad range of voting protocols, including plurality, veto, approval, and utility based voting. In addition to our polynomial-time algorithms we provide NP-completeness results for a couple of our nonuniform bribery problems for weighted voters, and a couple of approximation algorithms for NP-complete bribery problems defined in [FHH06] (in particular, an FPTAS for plurality-weighted-$bribery problem).
Keywords: Complexity theory; cryptography; interval functions;small-world networks;.
Redundancy is a basic property of many computational settings. This thesis concerns techniques for eliminating redundancy in some cases, and exploiting it in others.We study one-way functions, i.e., functions that are easy to compute but hard to invert. Such functions were previously studied as cryptographic primitives. Since it remains an open question whether one-way functions exist, we study the question of their existence in relation to a variety of complexity-theoretic hypotheses.
Starting with one-way functions in which redundancy in the preimage is absolutely minimal, i.e. one-to-one, we provide the first characterization of the existence of one-way permutations by a complexity class separation hypothesis, namely $\P \neq \up \inter \coup$.
Next, we study a type of one-way function that provably can never be one-to-one. Strong, total, associative, one-way functions are two-argument, one-way functions that are hard to invert, even if one of their arguments is known. Such special, one-way functions were originally used to construct secret-key agreement and digital signature protocols. We study techniques for creating such functions whose amount of preimage redundancy (as a function of the length of the corresponding image element) is minimized. We show that, if $\p \neq \up$, then such special one-way functions exist and that we can go from total, associative polyomial-time computable functions to strong, total, associative, one-way functions at no cost in increased preimage redundancy.
Continuing our study of eliminating redundancy in functions, we examine the complexity of counting the sizes of intervals over orders having certain, natural, computational and redundancy properties. We show that having redundancy in the adjacency relations of the order adds almost nothing to the computational complexity of computing such intervals.
Finally, we look at a problem in routing on ad-hoc networks whose solution exploits redundancy. We provide a theoretical framework for analyzing the behavior of a variety of tableless routing schemes. We show that such schemes work well when there is redundancy between the network distance and the objective functions used to make routing decisions.
Keywords: approximation; Dodgson elections; election systems; frequently self-knowingly correct algorithms; greedy algorithms; optimal lobbying; preference aggregation.
We investigate issues related to two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Christian et al. [CFRS06] showed that optimal lobbying is intractable in the sense of parameterized complexity. We provide an efficient greedy algorithm that achieves a logarithmic approximation ratio for this problem and even for a more general variant---optimal weighted lobbying. We prove that essentially no better approximation ratio than ours can be proven for this greedy algorithm.The problem of determining Dodgson winners is known to be complete for parallel access to NP [HHR97]. Homan and Hemaspaandra [HH06] proposed an efficient greedy heuristic for finding Dodgson winners with a guaranteed frequency of success, and their heuristic is a ``frequently self-knowingly correct algorithm.'' We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. Furthermore, we study some features of probability weight of correctness with respect to Procaccia and Rosenschein's junta distributions [PR07].
Keywords: computational social choice; bribery; Copeland elections; control; Llull elections; voting.
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 [BTT92]. An election system in which such an agent's computational task is NP-hard is said to be resistant to the given type of control. The only election systems known to be resistant to all the standard control types are highly artificial election systems created by hybridization [HHR07]. In this paper, we prove that an election system developed by the 13th century mystic Ramon Llull and the well-studied Copeland election system are both resistant to all the standard types of (constructive) electoral control other than one variant of addition of candidates. This is the most comprehensive resistance to control yet achieved by any natural election system. In addition, we show that Llull and Copeland voting are very broadly resistant to bribery attacks, and we integrate the potential irrationality of voter preferences into many of our results.
Keywords: autoreducibility; length-decreasing self-reducibility; reductions; function classes; complete functions.
This paper studies the notions of autoreducibility and length-decreasing self-reducibility of functions and languages. Recently Glasser et al. have shown that for many classes C, including PSPACE and NP, it holds that all nontrivial complete languages are polynomial-time many-one autoreducible. In contrast, this paper shows that for many classes C such that P is a subset of C (e.g., PSPACE and NP) some complete languages in C are not polynomial-time length-decreasing self-reducible unless C is a subset of P and for classes C such that L is a subset of C and C is a subset of P (e.g., P and NL) some complete languages in C are not logarithmic-space length-decreasing self-reducible unless C is a subset of L.This paper also shows that contrast between autoreducibility and length-decreasing self-reducibility for the case of functions. In particular, the paper shows that many function complexity classes FC (including well-studied #P, SpanP, and GapP and not-so-well-studied but highly natural #PE and TotP) have the property that all complete functions in FC are polynomial-time Turing-autoreducible. For #P and TotP, the autoreductions can be made to be polynomial-time one-Turing (one query per input).
These results show that, under reasonable assumptions, the notions of length-decreasing self-reducibility and autoreducibility differ both on complete languages and on complete functions. In a similar vein, this paper shows that under reasonable assumptions autoreducibility and random-self-reducibility differ with respect to functions.
Keywords: computational complexity; graph diameter; kings; graph radius; initial components.
A king in a directed graph is a vertex from which each vertex in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king [Lan53]. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems [NT05] and semifeasible sets [HNP98, HT06, HOZZ06].In this paper, we study the complexity of recognizing kings. For each succinctly specified family of tournaments, the king problem is already known to belong to $\Pi_2^{\mathrm p}$ [HOZZ06]. We prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in $\Pi_2^{\mathrm p}$. That is, we show that \emph{every} set in $\Pi_2^{\mathrm p}$ other than $\emptyset$ and $\Sigma^*$ is equivalent to a king problem under $\leq_{\mathrm m}^{\mathrm p}$-reductions. Indeed, we show that the equivalence can even be instantiated via relatively simple padding, and holds even if the notion of kings is redefined to refer to $k$-kings (for any fixed $k \geq 2$)---vertices from which the all vertices can be reached via paths of length at most $k$. In contrast, we prove that recognizing whether a given vertex is a source (i.e., there exists a $k$ such that it is a $k$-king) yields languages that also fall within $\Pi_2^{\mathrm p}$, yet cannot be $\Pi_2^{\mathrm p}$-complete---or even $\Class{NP}$-hard---unless $\Class{P} = \Class{NP}$.
Using these and related techniques, we obtain a broad range of additional results about the complexity of king problems, diameter problems, and radius problems. It follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is $\Pi_2^{\mathrm p}$-complete. We show that the radius problem for arbitrary succinctly represented graphs is $\Sigma_3^{\mathrm p}$-complete, but that in contrast the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is $\Pi_2^{\mathrm p}$-complete.
Keywords: bribery; computational social choice; control; manipulation; voting.
We provide an overview of some recent progress on the complexity of election systems. The issues studied include the complexity of the winner, manipulation, bribery, and control problems.
Keywords: computational social choice; multiagent systems; preference aggregation; computational complexity; elections; control; vulnerability; resistance; immunity; susceptibility.
Electoral control refers to attempts by an election's organizer ("the chair") to influence the outcome by adding/deleting/partitioning voters or candidates. The ground-breaking work of Bartholdi, Tovey, and Trick [BTT92] on (constructive) control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible.We introduce and study a method of combining two or more candidate- anonymous election schemes in such a way that the combined scheme possesses all the resistances to control (i.e., all the NP-hardnesses of control) possessed by any of its constituents: It combines their strengths. From this and new resistance constructions, we prove for the first time that there exists an election scheme that is resistant to all twenty standard types of electoral control.
Keywords: nonuniform complexity; Kolmogorov random sets; sparse sets; leaf languages.
Unger studied the balanced leaf languages defined via poly-logarithmically sparse leaf pattern sets. Unger shows that $\np$-complete sets are not polynomial-time many-one reducible to such balanced leaf language unless the polynomial hierarchy collapses to Theta^p_2 and that Sigam^p_2-complete sets are not polynomial-time bounded-truth-table reducible (respectively, polynomial-time Turing reducible) to any such balanced leaf language unless the polynomial hierarchy collapses to Delta^p_2 (respectively, Sigma^p_4).This paper studies the complexity of the class of such balanced leaf languages, which will be denoted by VSLL. In particular, the following tight upper and lower bounds of VSLL are shown:
1. coNP is included in VSLL and VSLL is included in coNP/poly (the former inclusion is already shown by Unger).
2. coNP/1 is not included in VSLL unless PH collapses to Theta^p_2.
3. For no constant c>0, VSLL is included coNP/n^c.
4. P/(loglog(n) + O(1)) is included in VSLL.
5. For no h(n) = loglog(n) + omega(1), P/h is included in VSLL.
Keywords: closure property; computational complexity; integer division; NPMV; NPSV; proper subtraction; refinement; solution elimination; solution reduction; #P.
Given a function based on the computation of an NP machine, can one in general eliminate some solutions? That is, can one in general decrease the ambiguity? This simple question remains, even after extensive study by many researchers over many years, mostly unanswered. However, complexity-theoretic consequences and enabling conditions are known. In this tutorial-style article we look at some of those, focusing on the most natural framings: reducing the number of solutions of NP functions, refining the solutions of NP functions, and subtracting from or otherwise shrinking #P functions. We will see how small advice strings are important here, but we also will see how increasing advice size to achieve robustness is central to the proof of a key ambiguity-reduction result for NP functions.
Keywords: comparison network; comparator network; oblivious sorting; parallel sorting; analysis of algorithms; sorting network.
We further siimplify Paterson's version of the Ajtai-Komlos-Szemeredi sorting network, and its analysis, mainly by tuning the invariant to be maintained.
Keywords: approval voting; bribery; computational complexity; Condorcet winner; dichotomy theorem; distributed artificial intelligence; Dodgson election; election manipulation; election system; Kemeny election; voting rule; multiagent system; plurality rule; preference aggregation; scoring system; Young election.
We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by a certain amount of bribing voters 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.
Keywords: network monitoring; network security; streaming algorithms; data streams; entropy.
Using entropy of traffic distributions has been shown to aid a wide variety of network monitoring applications such as anomaly detection, clustering to reveal interesting patterns, and traffic classification. However, realizing this potential benefit in practice requires accurate algorithms that can operate on high-speed links, with low CPU and memory requirements. Estimating the entropy in a streaming model to enable such fine-grained traffic analysis has been a challenging problem. We give lower bounds for this problem, showing that neither approximation nor randomization alone will let us compute the entropy efficiently.We present two algorithms for randomly approximating the entropy in a time and space efficient manner, applicable for use on very high speed (greater than OC-48) links. Our first algorithm for entropy estimation, inspired by the seminal work of Alon et al. for estimating frequency moments, has strong theoretical guarantees on the error and resource usage. Our second algorithm utilizes the observation that the efficiency can be substantially enhanced by separating the high-frequency items (or elephants), from the low-frequency items (or mice). Evaluations on real-world traffic traces from different deployment scenarios demonstrate the utility of our approaches.
Keywords: computational complexity; selector functions; positive reducibility; self-reducibility; p-selective sets.
We eliminate some special cases from the proofs of two theorems in which a machine instantiating a many-query reduction to a p-selective set is made to use only one query. The first theorem, originally proved by Buhrman, Torenvliet, and van Emde Boas [BTvEB93], states that any set that positively reduces to a p-selective set has a many-one reduction to that same set. The second, originally proved by Buhrman and Torenvliet [BT96], states that self-reducible p-selective sets are in P.
Keywords: self-knowing correctness; greedy algorithms; heuristic algorithms; frequently self-knowingly correct algorithms; Dodgson elections; Dodgson winner; Dodgson score.
In the year 1876 the mathematician Charles Dodgson, who wrote fiction under the now more famous name of Lewis Carroll, devised a beautiful voting system that has long fascinated political scientists. However, determining the winner of a Dodgson election is known to be complete for the \Theta_2^p level of the polynomial hierarchy. This implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates---although the number of voters may still be polynomial in the number of candidates---a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it ``knows'' that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.
Keywords: computational complexity; unambiguous computing; unique discovery; closure properties; cluster computing; edge detection.
We study the robustness---the invariance under definition changes---of the cluster class CL#P [HHKW05]. This class contains each #P function that is computed by a balanced Turing machine whose accepting paths always form a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition of CL#P is heavily influenced by the defining paper's focus on (global) orders. In contrast, we define a cluster class, CLU#P, to capture what seems to us a more natural model of cluster computing. We prove that the naturalness is costless: CL#P = CLU#P. Then we exploit the more natural, flexible features of CLU#P to prove new robustness results for CL#P and to expand what is known about the closure properties of CL#P.The complexity of recognizing edges---of an ordered collection of computation paths or of a cluster of accepting computation paths---is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges---the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters.
Keywords: reference affinity; NP-complete; divide-and-conquer computation; sampling method; data locality.
In POPL 2002, Petrank and Rawitz showed a universal result---finding optimal data placement is not only NP-hard but also impossible to approximate within a constant factor if P <> NP. Here we study a recently published concept called reference affinity, which characterizes a group of data that are always accessed together in computation. On the theoretical side, we give the complexity for finding reference affinity in program traces, using a novel reduction that converts the notion of distance into satisfiability. We also prove that reference affinity automatically captures the hierarchical locality in divide-and-conquer computations including matrix solvers and N-body simulation. The proof establishes formal links between computation patterns in time and locality relations in space.On the practical side, we show that efficient heuristics exist. In particular, we present a sampling method and show that it is more effective than the previously published technique, especially for data that are often but not always accessed together. We show the effect on generated and real traces. These theoretical and empirical results demonstrate that effective data placement is still attainable in general-purpose programs because common (albeit not all) locality patterns can be precisely modeled and efficiently analyzed.
Keywords: self-reducibility; autoreducibility; PSPACE-complete; NP-complete; NL-complete.
Recently Gla{\ss}er et al. have shown that for many classes $C$ including PSPACE and NP it holds that all of its nontrivial many-one complete languages are autoreducible. This immediately raises the question of whether all many-one complete languages are Turing self-reducible for such classes $C$.This paper considers a simpler version of this question---whether all PSPACE-complete (NP-complete) languages are length-decreasing self-reducible. We show that if all PSPACE-complete languages are length-decreasing self-reducible then PSPACE = P and that if all NP-complete languages are length-decreasing self-reducible then NP = P.
The same type of result holds for many other natural complexity classes. In particular, we show that (1) not all NL-complete sets are logspace length-decreasing self-reducible, (2) unconditionally not all PSPACE-complete languages are logspace length-decreasing self-reducible, and (3) unconditionally not all EXP-complete languages are polynomial-time length-decreasing self-reducible.
Keywords: approval voting; computational complexity; computational resistance; computational vulnerability; Condorcet voting; destructive control; election systems; immunity; plurality voting; vote suppression; preference aggregation; multiagent systems; tie-breaking rules; voting systems; distributed artificial intelligence.
Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preference aggregation to destructive control. That is, we study the ability of an election's chair to, through such mechanisms as voter/candidate addition/suppression/partition, ensure that a particular candidate (equivalently, alternative) does not win. And we study the extent to which election systems can make it impossible, or computationally costly (NP-complete), for the chair to execute such control. Among the systems we study---plurality, Condorcet, and approval voting---we find cases where systems immune or computationally resistant to a chair choosing the winner nonetheless are vulnerable to the chair blocking a victory. Beyond that, we see that among our studied systems no one system offers the best protection against destructive control. Rather, the choice of a preference aggregation system will depend closely on which types of control one wishes to be protected against. We also find concrete cases where the complexity of or susceptibility to control varies dramatically based on the choice among natural tie-handling rules.
Keywords: advice classes; associative selector functions; function refinement; linear advice; low hierarchy; NP-hardness; NPSV-selective sets; P-selective sets; semifeasible algorithms.
The study of semifeasible algorithms was initiated by Selman's work a quarter of century ago [Sel79,Sel81,Sel82]. Informally put, this research stream studies the power of those sets L for which there is a deterministic (or in some cases, the function may belong to one of various nondeterministic function classes) polynomial-time function f such that when at least one of x and y belongs to L, then f(x,y) \in L \cap \{x,y\}. The intuition here is that it is saying: "Regarding membership in L, if you put a gun to my head and forced me to bet on one of x or y as belonging to L, my money would be on f(x,y)."In this article, we present a number of open problems from the theory of semifeasible algorithms. For each we present its background and review what partial results, if any, are known.
Keywords: tournaments; Pi-Two completeness; P-selectivity; succintly specified graphs; kings; complexity classification.
A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king [Lan53]. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of the semifeasible sets [HNP98,HT05] and in the study of the complexity of reachability problems [Tan01,NT02].In this paper, we study the complexity of recognizing kings. For each succinctly specified family of tournaments, the king problem is known to belong to $\Pi_2^p$ [HOZZ]. We prove that this bound is optimal: We construct a succinctly specified tournament family whose king problem is $\Pi_2^p$-complete. It follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is $\Pi_2^p$-complete. We also obtain $\Pi_2^p$-completeness results for k-kings in succinctly specified j-partite tournaments, $k,j \geq 2$, and we generalize our main construction to show that $\Pi_2^p$-completeness holds for testing k-kingship in succinctly specified families of tournaments for all $k \geq 2$.
Keywords: computational complexity; complexity classes; relativization; polynomial degree bounds; graph rreconstruction; directed hypergraphs.
We attain two main objectives in this thesis. First, we employ test languages to prove limitations of proof techniques to resolve certain questions in complexity theory. In this part of the thesis, we study the relationship between quantum classes and counting classes via closure properties, collapses, and relativized separations. We show that the best known classical bounds for quantum classes such as EQP and BQP cannot be significantly improved using relativizable proof techniques. In some cases, we strengthen known relativized separations between quantum and counting classes to their relativized immunity separations. Furthermore, using the closure properties of certain gap-definable counting classes, we prove strong consequences, in terms of the complexity of the polynomial hierarchy, of the following hypotheses: NQP is contained in BQP, and EQP equals NQP. Aside from using test languages to study the relationship between quantum and counting classes, we use test languages to construct, via degree bounds of polynomials, relativized worlds that exhibit separations of classes and nonexistence of complete sets.Second, we study certain concrete problems and characterize their complexity either by showing completeness results for complexity classes or by relating their complexity to some well-studied computational problem (e.g., the graph isomorphism problem). In this part of the thesis, we study concrete problems related to the reconstruction of a graph from a collection of vertex-deleted or edge-deleted subgraphs, and concrete problems related to a notion of linear connectivity in directed hypergraphs. We show that the problems we study related to the reconstruction of graphs either are isomorphic (in complexity-theoretic sense) to the graph isomorphism problem or are many-one hard for the graph isomorphism problem. In our study related to directed hypergraphs, we introduce a notion of linear hyperconnectivity, denoted by L-hyperpath, in directed hypergraphs and show how this notion can be used to model problems in diverse domains. We study problems related to the cyclomatic number of directed hypergraphs with respect to L-hypercycles (the minimum number of hyperedges that need to be deleted so that the directed hypergraph becomes free of L-hypercycles) and obtain completeness results for different levels of the polynomial hierarchy.
Keywords: semifeasible algorithms; advice complexity; P-selectivity; immunity.
We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset, but we also prove that every infinite P-selective set has some infinite subset in EXP/1. Informally put, the immunity of P-sel is so fragile that it is pierced by a single bit of information.The above claims follow from broader results that we obtain about the immunity of the P-selective sets. In particular, we prove that for every recursive function f, P-sel is DTIME(f)-immune. Yet we also prove that P-sel is not \Pi_2^p/1-immune.
Keywords: computational complexity; elections; election manipulation; scoring systems; dichotomy theorems; voting.
Scoring protocols are a broad class of voting systems. Each is defined by a vector $(\alpha_1,\alpha_2,\ldots,\alpha_m)$, $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_m$, of integers such that each voter contributes $\alpha_1$ points to his/her first choice, $\alpha_2$ points to his/her second choice, and so on, and any candidate receiving the most points is a winner.What is it about scoring-protocol election systems that makes some have the desirable property of being NP-complete to manipulate, while others can be manipulated in polynomial time? We find the complete, dichotomizing answer: Diversity of dislike. Every scoring-protocol election system having two or more point values assigned to candidates other than the favorite---i.e., having $||\{\alpha_i \condition 2 \leq i \leq m\}||\geq 2$---is NP-complete to manipulate. Every other scoring-protocol election system can be manipulated in polynomial time. In effect, we show that---other than trivial systems (where all candidates alway tie), plurality voting, and plurality voting's transparently disguised translations---\emph{every} scoring-protocol election system is NP-complete to manipulate.
Keywords: reference affinity; data locality; NPC; N-body simulation; memory hierarchy.
To study data placement on memory hierarchy, we present a model called {\em reference affinity}. Given a program trace, the model divides program data into hierarchical partitions (called affinity groups) based on a parameter $k$, which specifies the number of distinct data elements between accesses to members of each affinity group. Trivial solutions exist for the two ends of the hierarchy. At the top, when $k$ is no less than the data size, all program data belong to one affinity group. At the bottom, when $k$ is 0, each element is an affinity group.We present two theoretical results. The first is the complexity. We show that finding and checking affinity groups are in P when $k=1$ and $k=2$. When $k=3$, the checking problem is NP-complete, and the finding problem is NP-hard. The second is the uses. We show that reference affinity captures the hierarchical data locality from the trace of a hierarchical computation. As additional evidence, we cite empirical results for general-purpose programs.
Keywords: computational complexity; counting complexity; interval size functions; p-orders; adjacency checks; number of divisors; cluster computation.
Given a p-order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if (x, y) is an element of 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.
Keywords: simple stochastic games; Hoffman-Karp algorithm; algorithm analysis.
We obtain the first nontrivial worst-case upper bound on the number of iterations required by the well-known Hoffman-Karp algorithm for the simple stochastic game problem. We also describe a randomized variant of the Hoffman-Karp algorithm and analyze the expected number of iterations required by it in the worst case.
Keywords: computational complexity; complexity-theoretic one-way functions; associativity; commutativity; strong noninvertibility.
abi and Sherman [RS97,RS93] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to ``P does not equal NP.''More generally, in this paper we completely characterize which types of one-way functions stand or fall together with (plain) one-way functions---equivalently, stand or fall together with P not equaling NP. We look at the four attributes used in Rabi and Sherman's seminal work on algebraic properties of one-way functions (see [RS97,RS93]) and subsequent papers---strongness (of noninvertibility), totality, commutativity, and associativity---and for each attribute, we allow it to be required to hold, required to fail, or ``don't care.'' In this categorization there are 3^4 = 81 potential types of one-way functions. We prove that each of these 81 feature-laden types stand or fall together with the existence of (plain) one-way functions.
Keywords: legitimate deck; graph isomorphism; reconstruction numbers; graph reconstruction.
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts $c \geq 1$ of deletion:1) $GI \equiv^{l}_{iso} VDC_{c}$, $GI \equiv^{l}_{iso} EDC_{c}$, $GI \leq^{l}_{m} LVD_c$, and $GI \equiv^{p}_{iso} LED_c$.
2) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-VDC_c$ and $GI \equiv^{p}_{iso} k-EDC_c$.
3) For all $k \geq 2$, $GI \leq^{l}_{m} k-LVD_c$.
4) $GI \equiv^{p}_{iso} 2-LVC_c$.
5) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-LED_c$.
For many of these results, even the $c = 1$ case was not previously known.
Similar to the definition of reconstruction numbers $vrn_{\exists}(G)$ [HP85] and $ern_{\exists}(G)$ (see page 120 of [LS03]), we introduce two new graph parameters, $vrn_{\forall}(G)$ and $ern_{\forall}(G)$, and give an example of a family $\{G_n\}_{n \geq 4}$ of graphs on $n$ vertices for which $vrn_{\exists}(G_n) < vrn_{\forall}(G_n)$. For every $k \geq 2$ and $n \geq 1$, we show that there exists a collection of $k$ graphs on $(2^{k-1}+1)n+k$ vertices with $2^{n}$ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.
Keywords: structural complexity; unambiguous computation; alternation; relativization.
Unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally-unique games by Aida et al. [ACRW04] and in the design of efficient protocols involving globally-unique games by Crasmaru et al. [CGRS04]. This paper explores the power of unambiguity in alternating Turing machines in the following settings:(1) We show that unambiguity based hierarchies---AUPH, UPH, and \slant{UPH}---are infinite in some relativized world. For each $k$ >= 2, we construct another relativized world where the unambiguity based hierarchies collapse so that they have exactly $k$ distinct levels and their $k$'th levels coincide with PSPACE. These results shed light on the relativized power of the unambiguity based hierarchies, and parallel the results known for the case of the polynomial hierarchy.
(2) We define the bounded-level unambiguous alternating solution class UAS(k), for every $k >= 1, as the class of sets for which strings in the set are accepted unambiguously by some polynomial-time alternating Turing machine N with at most $k$ alternations, while strings not in the set either are rejected by $N$ or are accepted with ambiguity by N. We construct a relativized world where, for all $k >= 1$, $UP_{\leq k}$ is a subset of $UP_{\leq k+1}$ and $UAS(k)$ is a subset of $UAS(k+1)$.
(3) Finally, we show that robustly $k$-level unambiguous alternating polynomial-time Turing machines accept languages that are computable in $P^{\Sigma^{p}_{k} \oplus A}$, for every oracle $A$. This generalizes a result of Hartmanis and Hemachandra [HH90].
Keywords: computational complexity; problem classification.
Computer scientists, programmers, and engineers need to determine the complexity of computational problems on a daily basis, and they typically ask the following questions: Is the problem easy or hard? If it is easy, is there a really efficient algorithm for the problem? If the problem is hard, how hard is it? Are there large subclasses of problems that are easy? Are there efficient approximation algorithms for the problem? Finding the answers to these questions pertaining to problem classification can be arduous and daunting for someone who is not an expert in the domain. Different problems, even from the same domain, may require vastly different proof techniques for problem classification. Thus, it is highly desirable to have easily applicable tools (theorems, classification tests, algorithms, and dichotomy results) that classify a wide range of problems. In this thesis we provide such general tools for determining the complexity of problems arising in the following settings: boolean circuits, language properties of central complexity classes (such as NP, PP, and ParityP), cycles in graphs, oracle (database) access, theoretical bmodels of computer simulation, and structural restrictions on the witness functions of nondeterministic polynomial-time Turing machines.
Keywords: cannibalistic computation; context-free languages; linear space; overhead-free computation; CFL; deterministic context-free languages; DCFL; in-place algorithms; space overhead; two-stack automata; DLINSPACE; restarting automata; RRW-automata; editing Turing machines; space reuse.
We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space.Though some context-sensitive languages cannot be accepted by such machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.
Keywords: linear advice; selector functions; P-selectivity; associativity; commutativity; P/linear; NP/linear; advice complexity; semifeasible computation; algebraic properties.
This paper provides a tutorial overview of the advice complexity of the semifeasible sets---informally put, the class of sets having a polynomial-time algorithm that, given as input any two strings of which at least one belongs to the set, will choose one that does belong to the set. No previous familiarity with either the semifeasible sets or advice complexity will assumed, and when we include proofs we will try to make the material as accessible as possible via providing intuitive, informal presentations.Karp and Lipton (1980) introduced advice complexity about a quarter of a century ago. Advice complexity asks, for a given power of interpreter, how many bits of ``help'' suffice to accept a given set. Thus, this is a notion that contains aspects both of informational complexity and of computational complexity. We will see that for some powers of interpreter the (worst-case) complexity of the semifeasible sets is known right down to the bit (and beyond), but that for the most central power of interpreter---deterministic polynomial time---the complexity is currently known only to be at least linear and at most quadratic.
While overviewing the advice complexity of the semifeasible sets, we will stress also the issue of whether the functions at the core of semifeasibility---so-called selector functions---can without cost be chosen to possess such algebraic properties as commutativity and associativity. We will see that this is relevant, in ways both potential and actual, to the study of the advice complexity of the semifeasible sets.
Keywords: certificates; P-producible sets; complexity theory; inverse problems; coNP-hardness; NP.
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. As part of our work we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.
Keywords: odd-even merge; merging networks; sorting networks; comparison networks; oblivious merging; oblivious sorting; parallel sorting; bitonic sort; parallel processing; analysis of algorithms.
Batcher's bitonic merge has been presented in two distinct recursive ways. We show that a transparently equivalent redefinition of bitonicity clarifies the correctness of the more elegant of the approaches, and we outline a proof that the two approaches do yield the same networks.
Keywords: complexity classes; gap-definability; polynomial degree bounds; Turing hardness; relativization theory.
Resolving an issue open since Fenner, Fortnow, and Kurtz raised it in [FFK94], we prove that LWPP is not uniformly gap-definable and that WPP is not uniformly gap-definable. We do so in the context of a broader investigation, via the polynomial degree bound technique, of the lowness, Turing hardness, and inclusion relationships of counting and other central complexity classes.
Keywords: semi-feasible algorithms; advice complexity; relativization theory; computational complexity.
Ko proved that the P-selective sets are in the advice class P/quadratic. Hemaspaandra et al. showed that P-selective sets are in PP/linear. Hemaspaandra and Torenvliet improved this upper bound and proved that that P-selective sets are in NP/linear. From this result it follows that if P-sel \not\subseteq P/linear, then P \neq NP, and so it cannot be proven using relativizable techniques. They also raised the following question: P-sel \subseteq P/linear? That is, they asked whether each P-selective set has linear advice. This question is interesting in light of the fact that the P-selective sets constructed using the classic left-cut technique all have linear advice complexity. In this paper, we prove that no relativizable technique can resolve this question. In fact, we prove that there is an oracle A such that PP^A \inter P-sel^A \not\subseteq P^A/linear. In our proof, we use Kolmogorov random permutations in conjunction with random tournaments to construct a P-selective set with the desired properties. This construction may be of independent interest in relativization theory.
Keywords: Turing reduction; oracle (database) access; padding functions; computational complexity.
We study reductions that limit the extreme adaptivity of Turing reductions. In particular, we study reductions that make a rapid, structured progression through the set to which they are reducing: Each query is strictly longer (shorter) than the previous one. We call these reductions query-increasing (query-decreasing) Turing reductions. We also study query-nonincreasing (query-nondecreasing) Turing reductions. These are Turing reductions in which the sequence of query lengths is nonincreasing (nondecreasing). We ask whether these restrictions in fact limit the power of reductions. We prove that query-increasing and query-decreasing Turing reductions are incomparable with (that is, are neither strictly stronger than nor strictly weaker than) truth-table reductions and are strictly weaker than Turing reductions. In addition, we prove that query-nonincreasing and query-nondecreasing Turing reductions are strictly stronger than truth-table reductions and strictly weaker than Turing reductions. Despite the fact that we prove query-increasing and query-decreasing Turing reductions to in the general case be strictly weaker than Turing reductions, we identify a broad class of sets A for which any set that Turing reduces to A will also reduce to A via both query-increasing and query-decreasing Turing reductions. In particular, this holds for all tight paddable sets, where a set is said to be tight paddable exactly if it is paddable via a function whose output length is bounded tightly both from above and from below in the length of the input. We prove that many natural NP-complete problems such as satisfiability, clique, and vertex cover are tight paddable.
Keywords: complexity classes; hyperconnection; cyclomatic number; directed hypergraphs.
We introduce a notion of linear hyperconnection (formally denoted L-hyperpath) between nodes in a directed hypergraph and relate this notion to existing notions of hyperpaths in directed hypergraphs. We show that many interesting questions in problem domains such as secret transfer protocols, routing in packet filtered networks, and propositional satisfiability are basically questions about existence of L-hyperpaths or about cyclomatic number of directed hypergraphs w.r.t. L-hypercycles (the minimum number of hyperedges that need to be deleted to make a directed hypergraph free of L-hypercycles). We prove that the L-hyperpath existence problem, the cyclomatic number problem, the minimum cyclomatic set problem, and the minimal cyclomatic set problem are each complete for a different level (respectively, NP, $\Sigma^{p}_{2}$, $\Pi^{p}_{2}$, and DP) of the polynomial hierarchy.
Keywords: computational complexity; kings; ranking; immunity; bi-immunity; Toda equivalence classes; semi-feasible computation; P-selectivity; left cuts; P-printability tournaments.
We identify two properties that for P-selective sets are effectively computable. Namely we show that, for any P-selective set, finding a string that is in a given length's top Toda equivalence class (very informally put, a string from Sigma^n that the set's P-selector function declares to be most likely to belong to the set) is FP^{Sigma_2^p} computable, and we show that each P-selective set contains a weakly-P^{Sigma_2^p}$-rankable subset.
Keywords: cycle modularity problems; graph theory; computational complexity; algorithms.
The even cycle problem for both undirected [Tho88] and directed [RST99] graphs has been the topic of intense research in the last decade. In this paper, we study the computational complexity of cycle length modularity problems. Roughly speaking, in a cycle length modularity problem, given an input (undirected or directed) graph, one has to determine whether the graph has a cycle $C$ of a specific length (or one of several different lengths), modulo a fixed integer. We denote the two families (one for undirected graphs and one for directed graphs) of problems by $(S,m)-UC$ and $(S,m)-DC$, where $m \in \naturalnumber$ and $S \subseteq \{0, 1, \ldots, m-1\}$. $(S,m)-UC$ (respectively, $(S,m)-DC$) is defined as follows: Given an undirected (respectively, directed) graph $G$, is there a cycle in $G$ whose length, modulo $m$, is a member of $S$? In this paper, we fully classify (i.e., as either polynomial-time solvable or as $\np$-complete) each problem $(S,m)-UC$ such that $0 \in S$ and each problem $(S,m)-DC$ such that $0 \notin S$. We also give a sufficient condition on $S$ and $m$ for the following problem to be polynomial-time computable: $(S,m)-UC$ such that $0 \notin S$.
Keywords: computational complexity; quantum complexity classes; gap-definable counting classes; relativization theory; strong separations; reduction closure properties.
We study the complexity of quantum complexity classes such as EQP, BQP, and NQP (quantum analogs of P, BPP, and NP, respectively) using classical complexity classes such as ZPP, WPP, and C_{=}P. The contributions of this paper are threefold. First, via oracle constructions, we show that no relativizable proof technique can improve the best known classical upper bound for BQP (BQP \subseteq AWPP [FR99]) to BQP \subseteq WPP and the best known classical lower bound for EQP (P \subseteq EQP) to ZPP \subseteq EQP. Second, we prove that there are oracles A and B such that, relative to A, coRP is immune to NQP and relative to B, BQP is immune to P^{C_{=}P}. Extending a result of de Graaf and Valiant [dGV02], we construct a relativized world where EQP is immune to ModpP. Third, motivated by the fact that counting classes (e.g., LWPP, AWPP, etc.) are the best known classical upper bounds on quantum complexity classes, we study properties of these counting classes. We prove that WPP is closed under polynomial-time truth-table reductions, while we construct an oracle relative to which WPP is not closed under polynomial-time Turing reductions. The latter result implies that proving the equality of the similar appearing classes LWPP and WPP would require nonrelativizable proof techniques. We also prove that both AWPP and APP are closed under UP-Turing reductions. We use closure properties of WPP and AWPP to prove interesting consequences, in terms of the complexity of the polynomial-hierarchy, of the following hypotheses: NQP \subseteq BQP and EQP = NQP.
Keywords: greedy search; heuristic search; ad-hoc routing; small worlds; landscapes.
Kleinberg provides the first theoretical characterization of the algorithmic aspects of small-world graphs embedded in metric spaces. The algorithms that Kleinberg studies are closely related to decentralized routing schemes used in ad-hoc networking environments. We study decentralized routing on fitness landscapes, which are a model that generalizes the properties of metric graphs and allows us to consider factors other than distance in designing decentralized routing schemes. We show that certain features of landscapes upper bound the amount of flooding necessary in order for greedy, decentralized routing schemes to successfully deliver messages. Finally, we show that, in Kleinberg's model, there is a phase transition in the amount of flooding necessary for efficient routing.
Keywords: computational complexity; selective; membership comparable; self-reduction; low information content; sparse; graph isomorphism; graph automorphism; circuit value problem; reachability problem.
We study whether sets inside NP can be reduced to sets with low information content but possibly still high computational complexity. Examples of sets with low information content are tally sets, sparse sets, P-selective sets and membership comparable sets. For the graph automorphism and isomorphism problems GA and GI, for the directed graph reachability problem GAP, for the determinant function det, and for logspace self-reducible languages we establish the following results:o If GA is polynomial-time truth-table reducible to a P-selective set, then GA is in P.
o If GI is O(log n)-membership comparable, then GI is in RP.
o If GAP is logspace O(1)-membership comparable, then GAP is in L.
o If det is logspace Turing reducible to an L-selective set, then det is in FL.
o If a language A is logspace self-reducible and logspace Turing reducible to an L-selective set, then A is in L.
The last result is a strong logspace version of the characterisation of P as the class of self-reducible P-selective languages. As P and NL have logspace self-reducible complete sets, it also establishes a logspace analogue of the conjecture that if SAT is polynomial-time Turing reducible to a P-selective set, then SAT is in P.
Keywords: associations; maximally frequent itemset; distributed data mining; heterogeneous; similarity.
This paper proposes a new measure for similarity between basket datasets. The new measure is calculated from support counts using a formula inspired by information entropy. Experiments on both real and synthetic datasets show the effectiveness of the measure. This paper also studies the problem of finding a mapping between categorical database attribute sets using similarity measures. A generic approach for identifying such a mapping is proposed. The approach is implemented based on the similarity measure proposed in the paper and its performance has been evaluated and validated. Moreover, this paper also explores the applications of using the similarity measure to mine distributed datasets.
Keywords: space overhead; space reuse; overhead-free computation; linear space; context-sensitive languages; context-free languages; deterministic linear languages; meta-linear languages.
We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that subclasses of the context-free languages can even be accepted in polynomial time with absolutely no space overhead.
Keywords: P-selectivity; NP-selectivity; nondeterministic selectivity; selector functions; advice complexity; nonuniform complexity; semi-feasible computation; algebraic properties; associativity; commutativity; immunity; printability; tournaments; digraphs.
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 [Ko, 1983] and the best current lower bound is linear [Hemaspaandra and Torenvliet, 1996].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.
Keywords: determinant; rank; enumerative approximation; counting logspace classes.
We investigate the complexity of enumerative approximation of two elementary problems in linear algebra, computing the rank and the determinant of a matrix. In particular, we show that if there exists an enumerator that, given a matrix, outputs a list of constantly many numbers, one of which is guaranteed to be the rank of the matrix, then it can be determined in AC^0 (with oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the enumerator is an FL function, then the problem of computing the rank is in FL. The result holds for matrices over any commutative ring whose size grows at most polynomially with the size of the matrix. The existence of such an enumerator also implies a slightly stronger collapse of the exact counting logspace hierarchy.For the determinant function Det we establish the following two results: 1. If Det is poly-enumerable in logspace, then Det is in FL. 2. For any prime p, if Det-mod-p is (p-1)-enumerable in Mod_pL, then Det-mod-p is in FL. These results give a perspective on the approximability of many elementary linear algebra problems equivalent to computing the rank or the determinant. Due to the close connection between the determinant function and #L, as well as between the rank function and AC^0(C_=L), our results might yield a better understanding of the exact power of counting in logspace and the relationships among the complexity classes sandwiched between NL and uniform TC^1.
Keywords: counting properties; lower bounds; ambiguity; circuits; UP; NP; nondeterministic computation; Rice's Theorem; computation paths.
Rice's Theorem states that all nontrivial language properties of recursively enumerable sets are undecidable. Borchert and Stephan started the search for complexity-theoretic analogs of Rice's Theorem, and proved that every nontrivial counting property of boolean circuits is UP-hard. Hemaspaandra and Rothe improved the UP-hardness lower bound to UP_{O(1)}-hardness. The present paper raises the lower bound for nontrivial counting properties from UP_{O(1)}-hardness to FewP-hardness, i.e., from constant-ambiguity nondeterminism to polynomial-ambiguity nondeterminism. Furthermore, we prove that no relativizable technique can raise this lower bound to FewP-1-truth-table-hardness. We also prove a Rice-style theorem for NP, namely that every nontrivial language property of NP sets is NP-hard.
Keywords: estimation; joint probability; support count, minAB; prodAB; data mining.
Estimating joint probabilities plays an important role in many data mining and machine learning tasks. In this paper we introduce two methods, minAB and prodAB, to estimate joint probabilities. Both methods are based on a light-weight structure, partition support. The core idea is to maintain the partition support of itemsets over logically disjoint partitions and then use it to estimate joint probabilities of itemsets of higher cardinalities. We present extensive mathematical analyses on both methods and compare their performances on synthetic datasets. We also demonstrate a case study of using the estimation methods in a priori algorithm for fast association mining. Moreover, we explore the usefulness of the estimation methods in other mining/learning tasks. Experimental results show the effectiveness of the estimation methods.
Keywords: one-way functions; one-to-one functions; complexity-theoretic cryptography; permutations; self-witnessing languages.
A desirable property of one-way functions is that they be total, one-to-one, and onto---in other words, that they be permutations. We prove that one-way permutations exist exactly if P is the intersection of UP and coUP. This provides the first characterization of the existence of one-way permutations based on a complexity-class separation and shows that their existence is equivalent to a number of previously studied complexity-theoretic hypotheses.We also study permutations in the context of witness functions of nondeterministic Turing machines. A language is in PermUP if, relative to some unambiguous, nondeterministic, polynomial-time Turing machine accepting the language, the function mapping each string to its unique witness is a permutation of the members of the language. We show that under standard complexity-theoretic assumptions PermUP is a nontrivial subset of UP.
We study SelfNP, the set of all languages such that, relative to some nondeterministic, polynomial-time Turing machine that accepts the language, the set of all witnesses of strings in the language is identical to the language itself. We show that SAT is a member of SelfNP, and under standard complexity-theoretic assumptions, SelfNP is to equal to NP.
Keywords: structural complexity; competing provers; nonuniform complexity; symmetric alternation; Karp-Lipton Theorem; Yap's Theorem; Kaemper-AFK Theorem; lowness.
Via competing provers, we show that if a language A is self-reducible and has polynomial-size circuits then S2(A)=S2. Building on this, we strengthen the Kaemper-AFK Theorem, namely, we prove that if NP subseteq (NP intersect coNP)/poly then the polynomial hierarchy collapses to S2(NP intersect coNP). We also strengthen Yap's Theorem, namely, we prove that if NP subseteq coNP/poly then the polynomial hierarchy collapses to S2(NP). Under the same assumptions, the best previously known collapses were to ZPP(NP) and ZPP(NP(NP)) respectively ([KW98,BCK+94], building on [KL80,AFK89,Kaem91,Yap83]). It is known that S2 subseteq ZPP(NP) [Cai01]. That result and its relativized version show that our new collapses indeed improve the previously known results. Since the Kaemper-AFK Theorem and Yap's Theorem are used in the literature as bridges in a variety of results---ranging from the study of unique solutions to issues of approximation---our results implicitly strengthen all those results.
Keywords: Rice's Theorem; counting properties; boolean circuits; ambiguity-bounded computation; computational complexity.
Rice's Theorem states that all nontrivial language properties of recursively enumerable sets are undecidable. Borchert and Stephan [BS00] started the search for complexity-theoretic analogs of Rice's Theorem, and proved that every nontrivial counting property of boolean circuits is UP-hard. Hemaspaandra and Rothe [HR00] improved the UP-hardness lower bound to UP_{O(1)}-hardness. The present paper raises the lower bound for nontrivial counting properties from UP_{O(1)}-hardness to FewP-hardness, i.e., from constant-ambiguity nondeterminism to polynomial-ambiguity nondeterminism. We also prove a Rice-style theorem for NP, namely that every nontrivial language property of NP sets is NP-hard, and we prove that every P-constructibly semi-switching counting property of circuits is PP-hard.
Keywords: quantum computing; computational complexity; almost-everywhere superiority.
We prove that, relative to some black box, there are languages for which polynomial-time quantum machines are exponentially faster than each classical machine almost everywhere.
Keywords: no-search easy-hard technique; downward-collapse; computational complexity.
The top part of the preceding figure [figure appears in actual paper] 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 {\em downwards\/} has proven vastly more challenging. In particular, with regard to the figure above, consider the following claim: $$P_{m-tt}^{\Sigma_k^p} = P_{m+1-tt}^{\Sigma_k^p} \implies DIFF_m(\Sigma_k^p) coDIFF_m(\Sigma_k^p) = BH(\Sigma_k^p).~~~~(*)$$ This claim, if true, says that equality translates downwards between levels of the bounded-query hierarchy and the boolean hierarchy levels that (before the fact) are immediately below them.Until recently, it was not known whether~(*) {\em ever\/} held, except for the degenerate cases $m=0$ and $k=0$. Then Hemaspaandra, Hemaspaandra, and Hempel~\cite{hem-hem-hem:j:downward-translation} proved that~(*) holds for all $m$, for $k > 2$. Buhrman and Fortnow~\cite{buh-for:j:two-queries} 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~\cite{buh-for:j:two-queries}, our achievement of the $k=2$ case cannot to 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.
Keywords: P-selectivity; selector functions; advice complexity; nonuniform complexity; semi-feasible computation; algebraic properties; associativity; commutativity; immunity; printability; tournaments.
Karp and Lipton, in their seminal 1980 paper, introduced the notion of advice (nonuniform) complexity, which since has been of central importance in complexity theory. Nonetheless, much remains unknown about the optimal advice complexity of classes having polynomial advice complexity.In particular, let P-sel denote the class of all P-selective sets [Selman 1979]. For the nondeterministic advice complexity of P-sel, linear upper and lower bounds are known [Hemaspaandra and Torenvliet 1996]. However, for the deterministic advice complexity of P-sel, the best known upper bound is quadratic [Ko 1983], and the best known lower bound is the linear lower bound inherited from the nondeterministic case. This paper establishes an algebraic sufficient condition for P-sel to have a linear upper bound: If all P-selective sets are associatively P-selective then the deterministic advice complexity of P-sel is linear. (The weakest previously known sufficient condition was P=NP.)
Relatedly, we prove that every associatively P-selective set is commutatively, associatively P-selective.
Keywords: computational complexity; easiness bands; emptiness testing; exponential gaps; NP-hardness; P-immunity; positive reductions; printability; self-reducibility.
No P-immune set having exponential gaps is positive-Turing self-reducible.
Keywords: computational complexity; sparse complete sets; polynomial-time reductions.
This paper discusses advances, due to the work of Cai, Naik, and Sivakumar and Glasser, in the complexity class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
Keywords: space-bounded computation, probabilistic computation, probabilistic plus nondeterministic computation, parallel computation, Turing machines, finite-state automata, multihead finite-state automata, auxiliary pushdown automata, residue number system, matrix inversion, derandomization, class hierarchy, head hierarchy, logspace reductions, probabilistic automata, stochastic languages, Markov chains, Arthur-Merlin games, games against nature.
We present hierarchical characterizations and reductions of classes of languages recognized by logarithmic-space (logspace, for short) probabilistic Turing machines, and by Arthur-Merlin games and games against Nature, both with logspace probabilistic verifiers. We decompose each logspace complexity class into a hierarchy based on the corresponding multihead two-way finite automata, and we prove that most of these hierarchies are strict, even with respect to languages over a single-letter alphabet. We also obtain efficient reductions of our logspace complexity classes to low levels in the corresponding hierarchies.Another focus is on space-efficient deterministic simulation of space-bounded Turing machines with probabilistic and mixed (i.e., probabilistic and nondeterministic) transitions. We present new results for two classes of machines, defined respectively in terms of logarithmic and sublogarithmic space bounds:
1) For logarithmic bounds, we obtain several new complete problems. These include variants of Savitch's maze-threading problem that are solvable by surprisingly simple devices. In particular, it follows that matrix inversion problems, which seem computationally hard, are efficiently reducible to languages recognized by one-way probabilistic devices that seem quite weak.
2) For sublogarithmic bounds, we find deterministic simulations significantly more space-efficient than the previously known simulations. In particular, for one-head probabilistic finite automata, we obtain an optimal, logspace deterministic simulation. Since our simulations are presented in the more general setting of Markov chains, they may have other applications as well. For use in the simulations, we develop space-efficient (and parallel-time-efficient) deterministic techniques for working with succinct residue representations of large natural numbers.
We extend our study to pushdown automata and auxiliary-pushdown automata with probabilistic and mixed transitions. We give characterizations in terms of well-known complexity classes for the classes of languages recognized by these automata. It follows that the differences between classes of languages such as P and PSPACE, NL and SAC^1, and PL and Diff_>(#SAC^1) all derive from the difference between using one symbol and using two symbols on a pushdown store, in certain settings.
Finally, we define and investigate probabilistic automata with "logspace-constructible" transition probabilities.
Keywords: cryptography; one-way functions; worst-case cryptocomplexity.
Rabi, Rivest, and Sherman alter the standard notion of noninvertibility to a new notion they call strong noninvertibility, and show---via explicit cryptographic protocols for secret-key agreement ([Rabi and Sherman 1993; Rabi and Sherman 1997] attribute this to Rivest and Sherman) and digital signatures [Rabi and Sherman 1993; Rabi and Sherman 1997]---that strongly noninvertible functions would be very useful components in protocol design. Their definition of strong noninvertibility has a small twist (``respecting the argument given'') that is needed to ensure cryptographic usefulness. In this paper, we show that this small twist has a large, unexpected consequence: Unless P=NP, some strongly noninvertible functions are invertible.
Keywords: parallel access; polynomial ambiguity; computational complexity; parallel census technique; USAT; FewP; nondeterministic computation; exponentially length-decreasing reductions.
We discuss the history and uses of the parallel census technique---an elegant tool in the study of certain computational objects having polynomially bounded census functions. A sequel will discuss advances (including [Cai, Naik, and Sivakumar, 1995] and [Glasser, 2000]), some related to the parallel census technique and some due to other approaches, in the complexity-class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
Keywords: associativity; computational complexity; cryptocomplexity; cryptography; ambiguity; algebraic cryptography; one-way functions.
Rabi and Sherman [1997] present a cryptographic paradigm based on associative, one-way functions that are strong (i.e., hard to invert even if one of their arguments is given) and total. Hemaspaandra and Rothe [1999] proved that such powerful one-way functions exist exactly if (standard) one-way functions exist, thus showing that the associative one-way function approach is as plausible as previous approaches. In the present paper, we study the degree of ambiguity of one-way functions. Rabi and Sherman showed that no associative one-way function (over a universe having at least two elements) can be unambiguous (i.e., one-to-one). Nonetheless, we prove that if standard, unambiguous, one-way functions exist, then there exist strong, total, associative, one-way functions that are \mathcal{O}(n)-to-one. This puts a reasonable upper bound on the ambiguity. Our other main results are: (1) P \neq FewP if and only if there exists an (n^{\mathcal{O}(1)})-to-one, strong, total AOWF. (2) No \mathcal{O}(1)-to-one total, associative functions exist in \Sigma^* \times \Sigma^* \rightarrow \Sigma^*. (3) For every nondecreasing, unbounded, total, recursive function g : \mathbb{N} \rightarrow \mathbb{N}, there is a g(n)-to-one, total, commutative, associative, recursive function in \Sigma^* \times \Sigma^* \rightarrow \Sigma^*.
(Superceded by TR 746)
Keywords: solution reduction; solution-pruning algorithms; cardinality types; function refinement; lowness; semi-feasible computation; selectivity theory; computational complexity.
We study whether one can prune solutions from NP functions. Though it is known that, unless surprising complexity class collapses occur, one cannot reduce the number of accepting paths of NP machines [Ogihara and Hemachandra 1993], we nonetheless show that it often is possible to reduce the number of solutions of NP functions. For finite cardinality types, we give a sufficient condition for such solution reduction. We also give absolute and conditional necessary conditions for solution reduction, and in particular we show that in many cases solution reduction is impossible unless the polynomial hierarchy collapses.
Keywords: one-way functions; cryptography; associativity of one-way functions; commutativity of one-way functions; strongly noninvertible functions.
We survey recent developments in the study of (worst-case) one-way functions having strong algebraic and security properties. According to [Rabi and Sherman, 1993], this line of research was initiated in 1984 by Rivest and Sherman who designed two-party secret-key agreement protocols that use strongly noninvertible, total, associative one-way functions as their key building blocks. If commutativity is added as an ingredient, these protocols can be used by more than two parties, as noted by Rabi and Sherman [1993] who also developed digital signature protocols that are based on such enhanced one-way functions.Until recently, it was an open question whether one-way functions having the algebraic and security properties that these protocols require could be created from any given one-way function. Recently, Hemaspaandra and Rothe [1999] resolved this open issue in the affirmative, by showing that one-way functions exist if and only if strong, total, commutative, associative one-way functions exist. We discuss this result, and the work of Rabi, Rivest, and Sherman, and recent work of Homan [1999] that makes progress on related issues.
Keywords: quantum computing; lower bounds; almost-everywhere hardness; computational complexity.
Simon [Sim97] as extended by Brassard and H{\o}yer [BH97] shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine infinitely often. The present paper shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine almost everywhere.
Keywords: computational complexity; space complexity; probabilistic Turing machine; nodeterministic Turing machine; multihead finite automaton.
Nondeterministic Turing acceptors can be viewed as probabilistic acceptors with errors that are one-sided but not significantly bounded. In his seminal work on resource-bounded probabilistic Turing machines, Gill showed how to transform such a machine to one that does have a good error bound, at only modest cost in space usage. We describe a simpler transformation that incurs absolutely no cost in space usage.If we change each probabilistic transition to a nondeterministic one, then we get a space-preserving transformation in the opposite direction as well, assuming the definitions are right. Thus the complexity classes are exactly the same, and we have the same space-bound hierarchy for bounded-one-sided-error probabilistic computation that we have for nondeterministic computation. Similarly, we have the same number-of-heads complexity classes and hierarchy for bounded-one-sided-error probabilistic multihead finite automata as for nondeterministic ones.
Keywords: computational complexity theory; graphs of functions; parallel versus sequential access; polynomial-time reductions.
We provide optimal inclusions and separations between parallel and sequential self-checking, i.e., regarding the parallel and sequential reduction relationships between functions and their graphs. In particular, we show that there are functions for which parallel self-checking is exponentially more expensive than sequential self-checking. Prior to this work, it had not been established that parallel self-checking ever needed to be even one query more expensive than sequential self-checking.
Keywords: computational complexity; cryptography; security of secret-key agreement and digital signature protocols; complexity-theoretic one-way functions; associativity.
Rabi and Sherman (1997) 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 multi-party secret-key agreement), associative one-way functions as their key building blocks. Though Rabi and Sherman did prove that associative one-way functions exist if P \neq 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 \neq NP then "strong," total, commutative, associative one-way functions exist.
Keywords: computational complexity; enumerative counting; census functions; tally NP sets.
We study the question of whether every P set has an easy (i.e., polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of language and function classes such as the containment of #P_1 in FP, where #P_1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P_{1}^{PH} function can be computed in FP^{#P_{1}^{#P_{1}}}. Consequently, every P set has an easy census function if and only if every set in the polynomial hierarchy does. We show that the assumption #P_1 being contained in FP implies P = BPP and that PH is contained in MOD_{k}P for each k \geq 2, which provides further evidence that not all sets in P have an easy census function. We also relate a set's property of having an easy census function to other well-studied properties of sets, such as rankability and scalability (the closure of the rankable sets under P-isomorphisms). Finally, we prove that it is no more likely that the census function of any set in P can be approximated (more precisely, can be n^{\alpha}-enumerated in time n^{\beta} for fixed \alpha and \beta) than that it can be precisely computed in polynomial time.
Keywords: downward translation of equality; polynomial hierarchy; boolean hierarchy; easy-hard technique; downward collapse; computational complexity.
During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of this nine-paper progression actually achieve downward collapse---that is, they show that high-level collapses induce collapses at (what beforehand were thought to be) lower complexity levels. For example, for each $k \geq 2$ it is now known that if $P^{\Sigma^p_k[1]} = P^{\Sigma^p_k[2]}$ then PH = $\Sigma^p_k$. This article surveys the history, the results, and the technique---the so-called easy-hard method---of these nine papers.J. Kadin. The polynomial time hierarchy collapses if the boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263-1282, 1988. Erratum appears in the same journal, 20(2):404.
K. Wagner. Number-of-query hierarchies. Technical Report 158, Univ. Augsburg, Inst. Mathematik, Augsburg, Germany, October 1987.
K. Wagner. Number-of-query hierarchies. Technical Report 4, Univ. Wurzburg, Inst. Informatik, Wurzburg, Germany, February 1989.
R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing, 25(2):340-354, 1996.
R. Beigel, R. Chang, and M. Ogiwara. A relationship between difference hierarchies and relativized polynomial hierarchies. Mathematical Systems Theory, 26(3):293-310, 1993.
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. An upward separation in the polynomial hierarchy. Technical Report Math/Inf/96/15, Friedrich-Schiller-Univ. Jena, Fak. Mathematik und Informatik, Jena, Germany, June 1996.
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. A downward collapse within the polynomial hierarchy. SIAM Journal on Computing. To appear.
H. Buhrman and L. Fortnow. Two queries. Proc., 13th Annual IEEE Conf. on Computational Complexity. To appear.
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. Translating equality downwards. Technical Report 657, University of Rochester, Department of Computer Science, Rochester, NY, April 1997.
Keywords: easy-hard technique; polynomial hierarchy; translations of equality; computational complexity; downward collapse.
Hemaspaandra et al. (1997) proved that, for m > 0 and 0 < i < k - 1: if (\Sigma^p_i) \bold\Delta DIFF_m(\Sigma^p_k) is closed under complementation, then DIFF_m(\Sigma^p_k) = coDIFF_m(\Sigma^p_k). This sharply asymmetric result fails to apply to the case in which the hypothesis is weakened by allowing the (\Sigma^p_i) to be replaced by any class in its difference hierarchy. We so extend the result by proving that, for s,m > 0 and 0 < i < k - 1: if DIFF_s(\Sigma^p_i) \bold\Delta DIFF_m(\Sigma^p_k) is closed under complementation, then DIFF_m(\Sigma^p_k) = coDIFF_m(\Sigma^p_k).
Keywords: computational complexity; immunity; relativized computation; circuit lower bounds; counting classes.
Ko and Bruschi showed that in some relativized world, PSPACE (in fact, ParityP) contains a set that is immune to the polynomial hierarchy (PH). In this paper, we study and settle the question of (relativized) separations with immunity for PH and the counting classes PP, C_=P, and ParityP in all possible pairwise combinations. Our main result is that there is an oracle A relative to which C_=P contains a set that is immune to BPP^{ParityP}. In particular, this C_=P^A set is immune to PH^A and ParityP^A. Strengthening results of Tor\'{a}n and Green, we also show that, in suitable relativizations, NP contains a C_=P-immune set, and ParityP contains a PP^{PH}-immune set. This implies the existence of a C_=P^B-simple set for some oracle B, which extends results of Balc\'{a}zar et al. and provides the first example of a simple set in a class not known to be contained in PH. Our proof technique requires a circuit lower bound for "exact counting" that is derived from Razborov's lower bound for majority.
Keywords: DNA computation; Boolean circuits.
This paper studies seemingly the smallest DNA computational model. This model assumes as its computation basis merge, detect, synthesize, anneal, and length-specific separation, but does not assume sequence-specific separation as in many other DNA computational models. Uncertainty occurring in some of the operations is taken into consideration, and the decision by computation under the model is defined in terms of robustness. This paper shows tight upper bounds on the power of this computational model in terms of circuits. For every $k\geq 1$, the languages robustly accepted by programs under this model in $O(\log^k n)$ steps using polynomially many DNA molecules resides between $\NC^{k}$ and $\SAC^{k+1}$.
Keywords: satisfiability threshold; Horn satisfiability; positive unit resolution.
This paper studies the phase transition in random Horn satisfiability: under the random model $\Omega(n,m)$ in which a formula is obtained by choosing $m$ clauses independently, uniformly at random, and with repetition from all Horn clauses in $n$ variables, $\theta(n)=2^{n}$ is the satisfiability threshold for the Horn satisfiability. The threshold is coarse since, if $\mu(n) = c\cdot 2^{n}$ then \[ \lim_{n\goesto \infty} \PR_{\Phi \in \Omega(n,\mu(n))}\, [\mbox{$\Phi$ is satisfiable}] = 1-F(e^{-c}), \] where $F(x)=(1-x)(1-x^2)(1-x^4)(1-x^8)\cdots$. This resolves both of the two remaining cases of the problem of analyzing phase transitions of the six maximally tractable cases in Schaefer's Dichotomy Theorem.
Keywords: selectivity theory; tournaments; computational complexity theory; P-selective sets; linear advice classes; limited nondeterminism.
Hemaspaandra and Torenvliet showed that each P-selective set can be accepted by a polynomial-time nondeterministic machine using linear advice and quasilinear nondeterminism. We extend this by showing that each P-selective set can be accepted by a polynomial-time nondeterministic machine using linear advice and linear nondeterminism.
Keywords: robust reductions; overproductive reductions; underproductive reductions; strong nondeterministic reductions; sparse complete sets; Karp-Lipton Theorem; computational complexity theory.
We continue the study of robust reductions initiated by Gavald\`{a} and Balc\'{a}zar. In particular, a 1991 paper of Gavald\`{a} and Balc\'{a}zar claimed an optimal separation between the power of robust and nondeterministic strong reductions. Unfortunately, their proof is invalid. We re-establish their theorem. Generalizing robust reductions, we note that robustly strong reductions are built from two restrictions, robust underproductivity and robust overproductivity, both of which have been separately studied before in other contexts. By systematically analyzing the power of these reductions, we explore the extent to which each restriction weakens the power of reductions. We show that one of these reductions yields a new, strong form of the Karp-Lipton Theorem.
Keywords: query order; boolean hierarchy; polynomial hierarchy; translations of equality.
Hemaspaandra, Hempel, and Wechsung raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned---inasfar as they can be learned without resolving whether or not the polynomial hierarchy collapses---for both the polynomial hierarchy and the boolean hierarchy. In the polynomial hierarchy, query order never matters. In the boolean hierarchy, query order sometimes does not matter and, unless the polynomial hierarchy co