Restricted Information from Nonadaptive Queries to NP

We investigate classes of sets that can be decided by bounded truth-table reductions to an NP set in which evaluators donothave full access to the answers to the queries but get only restricted information such as the number of queries that are in the oracle set or even just this number modulom, for somem?2. We also investigate the case in which evaluators are nondeterministic. We show that when we vary the information that the evaluators get, this can change the resulting power of the evaluators. We locate all these classes within levels of the Boolean hierarchy which allows us to compare the complexity of such classes.     

Space bounded computations: review and new separation results

In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch's theorem and the Immerman-Szelepcsényi theorem do not hold in the range lg lg n to lg n. We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.     

Preprocessing of Intractable Problems

Some computationally hard problems, e.g., deduction in logical knowledge bases– are such that part of an instance is known well before the rest of it, and remains the same for several subsequent instances of the problem. In these cases, it is useful to preprocess off-line this known part so as to simplify the remaining on-line problem. In this paper we investigate such a technique in the context of intractable, i.e., NP-hard, problems. Recent results in the literature show that not all NP-hard problems behave in the same way: for some of them preprocessing yields polynomial-time on-line simplified problems (we call them compilable), while for other ones their compilability implies some consequences that are considered unlikely. Our primary goal is to provide a sound methodology that can be used to either prove or disprove that a problem is compilable. To this end, we define new models of computation, complexity classes, and reductions. We find complete problems for such classes, “completeness” meaning they are “the less likely to be compilable.” We also investigate preprocessing that does not yield polynomial-time on-line algorithms, but generically “decreases” complexity. This leads us to define “hierarchies of compilability,” that are the analog of the polynomial hierarchy. A detailed comparison of our framework to the idea of “parameterized tractability” shows the differences between the two approaches.     

Holographic reduction, interpolation and hardness

We introduce the method of proving complexity dichotomy theorems by holographic reductions. Combined with interpolation, we present a unified strategy to prove #P-hardness. Specifically, we prove a complexity dichotomy theorem for a class of counting problems on 2–3 regular graphs expressible by Boolean signatures. For these problems, whenever a holographic reduction followed by interpolation fails to prove #P-hardness, we can show that the problem is solvable in polynomial time.     

On the complexity of distributed query optimization

While a significant amount of research efforts has been reported on developing algorithms, based on joins and semijoins, to tackle distributed query processing, there is relatively little progress made toward exploring the complexity of the problems studied. As a result, proving NP-hardness of or devising polynomial-time algorithms for certain distributed query optimization problems has been elaborated upon by many researchers. However, due to its inherent difficulty, the complexity of the majority of problems on distributed query optimization remains unknown. In this paper we generally characterize the distributed query optimization problems and provide a frame work to explore their complexity. As it will be shown, most distributed query optimization problems can be transformed into an optimization problem comprising a set of binary decisions, termed Sum Product Optimization (SPO) problem. We first prove SPO is NP-hard in light of the NP-completeness of a well-known problem, Knapsack (KNAP). Then, using this result as a basis, we prove that five classes of distributed query optimization problems, which cover the majority of distributed query optimization problems previously studied in the literature, are NP-hard by polynomially reducing SPO to each of them. The detail for each problem transformation is derived. We not only prove the conjecture that many prior studies relied upon, but also provide a frame work for future related studies     

Characterizations of reduction classes modulo oracle conditions

It is known that nondeterministic polynomial time truth-table reducibility is exactly the same as nondeterministic polynomial time Turing reducibility. Here we study the standard nondeterministic reducibilities (conjunctive, bounded truth-table, bounded positive truth-table, and many-one) and show that each is a restriction of nondeterministic polynomial time Turing reducibility corresponding to acceptance modulo a set of oracle conditions. Then we show that the reduction classes of these reducibilities are classes of formal languages and as such have language theoretic characterization theorems. The same program is carried out for polynomial space.This research was supported in part by the National Science Foundation under Grants MCS77-23493, MSC80-11979, MCS81-20263, and MCS83-12472. The work of the second author was also supported by the United States-Israel Educational Foundation (Fulbright Award).     

On expressive power of regular realizability problems

A regular realizability (RR) problem is a problem of testing nonemptiness of intersection of some fixed language (filter) with a regular language. We show that RR problems are universal in the following sense. For any language L there exists an RR problem equivalent to L under disjunctive reductions in nondeterministic log space. From this result, we derive existence of complete problems under polynomial reductions for many complexity classes, including all classes of the polynomial hierarchy.     

P, NP, and the Post Correspondence Problem

We define a variant of the Post Correspondence Problem, the machine-oriented Post Correspondence Problem or MOPCP, especially suitable for complexity considerations. All recursively enumerable sets can be represented in terms of instances of MOPCP and, moreover, deterministic and nondeterministic time and space complexities have their natural counterpart in the representation. This leads to PCP-related complexity classes; for instance, the time complexity classes PCP-P and PCP-NP. Using a bounded delay injectivity condition on one of the morphisms of a PCP instance, we obtain an exact characterization of P. In this characterization, determinism corresponds exactly to the bounded delay condition and no reference is made to computations of any sort. A weaker bounded delay requirement gives rise to an infinite (possibly collapsing) hierarchy between P and NP.     

Learnability and Definability in Trees and Similar Structures

We prove upper bounds for combinatorial parameters of finite relational structures, related to the complexity of learning a definable set. We show that monadic second-order (MSO) formulas with parameters have bounded Vapnik–Chervonenkis dimension over structures of bounded clique-width, and first-order formulas with parameters have bounded Vapnik–Chervonenkis dimension over structures of bounded local clique-width (this includes planar graphs). We also show that MSO formulas of a fixed size have bounded strong consistency dimension over MSO formulas of a fixed larger size, for labeled trees. These bounds imply positive learnability results for the PAC and equivalence query learnability of a definable set over these structures. The proofs are based on bounds for related definability problems for tree automata.     

Complexity theoretic hardness results for query learning

We investigate the complexity of learning for the well-studied model in which the learning algorithm may ask membership and equivalence queries. While complexity theoretic techniques have previously been used to prove hardness results in various learning models, these techniques typically are not strong enough to use when a learning algorithm may make membership queries. We develop a general technique for proving hardness results for learning with membership and equivalence queries (and for more general query models). We apply the technique to show that, assuming , no polynomial-time membership and (proper) equivalence query algorithms exist for exactly learning read-thrice DNF formulas, unions of halfspaces over the Boolean domain, or some other related classes. Our hardness results are representation dependent, and do not preclude the existence of representation independent algorithms.?The general technique introduces the representation problem for a class F of representations (e.g., formulas), which is naturally associated with the learning problem for F. This problem is related to the structural question of how to characterize functions representable by formulas in F, and is a generalization of standard complexity problems such as Satisfiability. While in general the representation problem is in , we present a theorem demonstrating that for "reasonable" classes F, the existence of a polynomial-time membership and equivalence query algorithm for exactly learning F implies that the representation problem for F is in fact in co-NP. The theorem is applied to prove hardness results such as the ones mentioned above, by showing that the representation problem for specific classes of formulas is NP-hard. Received: December 6, 1994     

Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.     

Communication Complexity Method for Measuring Nondeterminism in Finite Automata

While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows:1. Deterministic communication complexity provides lower bounds on the size of nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way.2. There is a family of languages KON_k² with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by B. Ravikumar and O. Ibarra (1989, SIAM J. Comput.18, 1263–1282) and H. Leung (1998, SIAM J. Comput.27, 1073–1082).     

Observations on complete sets between linear time and polynomial time

There is a single set that is complete for a variety of nondeterministic time complexity classes with respect to related versions of m-reducibility. This observation immediately leads to transfer results for determinism versus nondeterminism solutions. Also, an upward transfer of collapses of certain oracle hierarchies, built analogously to the polynomial-time or the linear-time hierarchies, can be shown by means of uniformly constructed sets that are complete for related levels of all these hierarchies. A similar result holds for difference hierarchies over nondeterministic complexity classes. Finally, we give an oracle set relative to which the nondeterministic classes coincide with the deterministic ones, for several sets of time bounds, and we prove that the strictness of the tape-number hierarchy for deterministic linear-time Turing machines does not relativize.     

Approximation preserving reductions for set covering,vertex covering and independent set hierarchies under differential approximationa

The notion of approximability preserving reductions between different problems deserves special attention in approximability theory. These kinds of reductions allow us polynomial time conversion of some already known ‘good’ approximation algorithms for some NP-hard problems into ones for some other NP-hard problems. In this context, we consider reductions for set covering and vertex covering hierarchies. Our results are then extended to hitting set and independent set hierarchies. Here, we adopt the differential approximation ratio that has the natural property to be stable under affine transformations of the objective function of a problem.     

Resource Bounds and Subproblem Independence

There are several reasons why some NP-hard problems can be solved deterministically in 2^{O(n^a)} time for some a, 0 < a < 1. One reason is that the problem can be solved with a nondeterministic procedure which uses only O(n^a) space. A second reason is that each instance of the problem exhibits a high degree of "subproblem independence" (specifically O(n^a) line channelwidth or treewidth). A third is that each instance of the problem can be solved using nondeterministic straight-line programs where the number of variables is only O(n^a). In this paper we show that, after imposing q-linear bounds on the computation time and obliviousness constraints on the nondeterminism, these three reasons are essentially equivalent. (q-Linear functions are similar to functions of the form n (log n)^k.) Specifically, the problem classes associated with these reasons are interchangeable using reductions which are simultaneously polynomial time and q-linear size-bounded. We call these PQ-reductions. The classes of problems solvable by these methods we call NQn^a. Because these classes are defined in a very general way, they include a rich variety of problems. We take this as evidence that these classes have "power index" a (i.e., that 2^{O(n^a)} is also a lower time bound). On the other hand, the easiness of all these problems can be derived from "subproblem independence" considerations, and thus the techniques associated with subproblem independence are seen to be more widely applicable than one might expect.     

Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.     

On the hardness of approximating label-cover

The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724-733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29-40] to Label-Cover showing it NP-hard to approximate to within 2^{(logn)1−o(1)}. This improves upon the best previous hardness of approximation results known for this problem.We also consider the Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307-320]. We show some hardness results for certain levels in this hierarchy, and place Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of Label-Cover in it.     

Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Ruzzo [Tree-size bounded alternation, J. Comput. Syst. Sci. 21] introduced the notion of tree-size for alternating Turing machines (ATMs) and showed that it is a reasonable measure for classification of complexity classes. We establish in this paper that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computations by time and space simultaneously bounded nondeterministic TMs (NTMs).We also show that not every polynomial time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly increased time bound and a slightly decreased space bound simultaneously.     

Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI-circuits

Each (nondeterministic) multilective VLSI-circuit C of area A can be simulated by an oblivious (disjunctive) branching program of width exp(O(A)) which has the same multiplicity of reading as C. That is why exponential lower bounds on the width of (disjunctive) oblivious branching programs of linear depth provide lower bounds of order Ω(n^1–2α), , on the area of (nondeterministic) multilective VLSI-circuits computing explicitly defined one-output Boolean functions, if the multiplicity of reading is bounded by O(log^αn). Lower bounds are derived for the sequence equality problem (SEQ) and the graph accessibility problem (GAP).     

A simple characterization of uniform boundedness for a class of recursions

Detecting bounded recursions is a powerful optimization technique for recursive database query languages, as bounded recursions can be replaced by equivalent nonrecursive definitions. The problem is also of theoretical interest in that varying the class of recursions considered generates problem instances that vary from linearly decidable to NP-hard to undecidable. In this paper we review and clarify the existing definitions of boundedness. We then specify a class of recursions C such that membership in C guarantees that a certain simple condition is necessary and sufficient for boundedness. We use the notion of membership in C to unify and extend previous work on determining decidable classes of bounded recursions.