Geometric optimization and the polynomial hierarchy

We illustrate two techniques of accurately classifying the optimization version of geometric problems in the polynomial hierarchy. We show that if NP ≠ Co-NP, then there are interesting natural geometric optimization problems (location-allocation problems under minsum) in Δ^P₂ that are in neither NP nor Co-NP. Hence, all these problems are shown to belong properly to Δ^P₂, the second level of the polynomial hierarchy. We also show that there are some interesting geometric optimization problems (location-allocation problems under minmax) complete for a class D^P (which is contained in Δ^P₂ and contains NP ∪ Co-NP).     

Complexity of Weak Bisimilarity and Regularity for BPA and BPP

It is an open problem whether weak bisimilarity is decidable for Basic Process Algebra (BPA) and Basic Parallel Processes (BPP). A PSPACE lower bound for BPA and NP lower bound for BPP have been demonstrated by Stribrna. Mayr achieved recently a result, saying that weak bisimilarity for BPP is Π^p₂-hard. We improve this lower bound to PSPACE, moreover for the restricted class of normed BPP.Weak regularity (finiteness) of BPA and BPP is not known to be decidable either. In the case of BPP there is a Π^p₂-hardness result by Mayr, which we improve to PSPACE. No lower bound has previously been established for BPA. We demonstrate DP-hardness, which in particular implies both NP and co-NP-hardness.In each of the bisimulation/regularity problems we consider also the classes of normed processes.Note: full version of the paper appears as [18].     

Complexity of Weak Bisimilarity and Regularity for BPA and BPP

It is an open problem whether weak bisimilarity is decidable for Basic Process Algebra (BPA) and Basic Parallel Processes (BPP). A PSPACE lower bound for BPA and NP lower bound for BPP have been demonstrated by Stribrna. Mayr achieved recently a result, saying that weak bisimilarity for BPP is Π^p₂-hard. We improve this lower bound to PSPACE, moreover for the restricted class of normed BPP.Weak regularity (finiteness) of BPA and BPP is not known to be decidable either. In the case of BPP there is a Π^p₂-hardness result by Mayr, which we improve to PSPACE. No lower bound has previously been established for BPA. We demonstrate DP-hardness, which in particular implies both NP and co-NP-hardness.In each of the bisimulation/regularity problems we consider also the classes of normed processes.Note: full version of the paper appears as [18].     

Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time

In this paper we consider the problem of deciding bisimulation equivalence of a BPP and a finite-state system. We show that the problem can be solved in polynomial time and we present an algorithm deciding the problem in time O(n⁴). The algorithm also constructs for each state of the finite-state system a ‘symbolic’ semilinear representation of the set of all states of the BPP system which are bisimilar with this state.     

A note on complete problems for complexity classes

We show that every class of recursive sets which is closed under p-Turing equivalence possesses a ⩽_pm-complete set if and only if it possesses a ⩽_pT-complete set. One of the consequences hereof is that the classes Δ_n^p of the polynomial hierarchy possess ⩽_pm-complete problems.     

Arthur and Merlin as Oracles

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) Arthur–Merlin class. Our main results are the following:

Some observations on NP real numbers and P-selective sets

We show that each standard left cut of a real number is a p-selective set. Classification results about NP real numbers and recursively enumerable real numbers follow from similar results about p-selective and semirecursive sets. In particular, it is proved that no left cut can be NP-hard unless the polynomial hierarchy collapses to ?₂^P. This result is surprising because it shows that the McLaughlin-Martin construction of a ?_tt-complete r.e. semirecursive set fails at the polynomial time complexity level.     

A mixed PI/VI design method for nonlinear H∞ Control

This paper proposes a new mixed policy iteration and value iteration (PI/VI) design method for nonlinear H_∞ control based on the theories of polynomial optimization and Lasserre's hierarchy. The design of a mixed PI/VI controller can be carried out in four steps: firstly, initialize design parameters and expand nonlinear system matrices; secondly, obtain a polynomial matrix inequality for policy improvement; thirdly, obtain the Lasserre's hierarchy of a global polynomial optimization problem for value improvement; fourthly, perform the mixed PI/VI algorithm to approximate the optimal nonlinear H_∞ control law. The novelty of this work lies in that the problem of designing a nonlinear H_∞ controller is translated into a polynomial global optimization problem, which can be solved by Lasserre's hierarchy directly, and then, the mixed PI/VI algorithm is presented to approximate the optimal nonlinear H_∞ control law by updating global optimizers iteratively. The main results of this paper consist of the mixed PI/VI algorithm and the related three theorems, which guarantee robust stability and performance of the closed‐loop nonlinear system. Numerical simulations show that the mixed PI/VI algorithm converges very fast and achieves good robust stability and performance in transient behavior, disturbance rejection, and enlarging the domain of attraction of the close‐loop system.     

A relationship between difference hierarchies and relativized polynomial hierarchies

Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over ₂ ^p . We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P _(k–1) ^NP )^NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has _m ^p -complete sets and is closed under _conj ^p -and _m ^NP -reductions (alternatively, closed under _disj ^p -and _m ^co-NP -reductions), if the difference hierarchy overC collapses to levelk, then PH ^C = (P _(k–1)–tt ^NP ) ^C . Then we show that the exact counting class C_P is closed under _disj ^p - and _m ^co-NP -reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PH^PP(= PH^C_P) is equal to (P _(k–1)–tt ^NP )^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P _k–tt ^NP : the restricted relativization P _k–tt ^{NP C} and the full relativization (P _k–tt ^NP ) ^C . IfC is NP-hard, then we show that the two relativizations are different unless PH ^C collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan.     

On counting problems and the polynomial-time hierarchy

We consider the relation between the relativized polynomial time hierarchy and relativizations of Gill's class PP of sets recognizable in polynomial time by probabilistic Turing machines and of Valiant's class D≠P of sets polynomial time Turing reducible to functions that give the number of accepting computations of nondeterministic polynomial-time bounded Turing machines. The main result is that there exists an oracle set A such that PP^A ?(Π₂^P,A ∪ σ₂^P,A) ≠ ?, with the corollary that also D ≠P^A ? (Π₂^P,A ∪ σ₂^P,A ≠ ?. The proof is an application of Baker and Selman's technique for showing that σ₂^P,A ? σ₃^P,A for some oracle set A.     

Partially-commutative context-free processes: Expressibility and tractability

Bisimulation equivalence is decidable in polynomial time for both sequential and commutative normed context-free processes, known as BPA and BPP, respectively. Despite apparent similarity between the two classes, different algorithmic techniques were used in each case. We provide one polynomial-time algorithm that works in a superclass of both normed BPA and BPP. It is derived in the setting of partially-commutative context-free processes, a new process class introduced in the paper. It subsumes both BPA and BPP and seems to be of independent interest. Expressibility issue of the new class, in comparison with the normed PA class, is also tackled in the paper.     

On γ-reducibility versus polynomial time many-one reducibility

We prove that each element of a class of functions (denoted by NPC_t^P), whose graphs can be accepted in nondeterministic polynomial time, can be evaluated in deterministic polynomial time if and only if γ-reducibility is equivalent to polynomial time many-one reducibility. We also modify the proof technique used to obtain part of this result to obtain the stronger result that if every γ-reduction can be replaced by a polynomial time Turing reduction, then every function in NPC_t^P can be evaluated in deterministic polynomial time.     

Polynomial closure and unambiguous product

This article is a contribution to the algebraic theory of automata, but it also contains an application to Büchi’s sequential calculus. The polynomial closure of a class of languagesC is the set of languages that are finite unions of languages of the formL ₀ a ₁ L ₁ ···a _nL_n, where thea _i’s are letters and theL _i’s are elements ofC. Our main result is an algebraic characterization, via the syntactic monoid, of the polynomial closure of a variety of languages. We show that the algebraic operation corresponding to the polynomial closure is a certain Mal’cev product of varieties. This result has several consequences. We first study the concatenation hierarchies similar to the dot-depth hierarchy, obtained by counting the number of alternations between boolean operations and concatenation. For instance, we show that level 3/2 of the Straubing hierarchy is decidable and we give a simplified proof of the partial result of Cowan on level 2. We propose a general conjecture for these hierarchies. We also show that if a language and its complement are in the polynomial closure of a variety of languages, then this language can be written as a disjoint union of marked unambiguous products of languages of the variety. This allows us to extend the results of Thomas on quantifier hierarchies of first-order logic.     

On closure properties of bounded two-sided error complexity classes

We show that if a complexity classC is closed downward under polynomial-time majority truth-table reductions ( _mtt ^p ), then practically every other polynomial closure property it enjoys is inherited by the corresponding bounded two-sided error class BP[C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practically every closure property of NP. Our main lemma shows that, for any relativizable classD which meets two fairly transparent technical conditions, we haveC ^BP[C] BP[D ^C]. Among our applications, we simplify the proof by Toda [Tol], [To2] that the polynomial hierarchy PH is contained in BP[P]. We also show that relative to a random oracleR, PH ^R is properly contained in P ^R .The first author was supported in part by NSF Grant CCR-9011248 and the second author was supported in part by NSF Grant CCR-89011154.     

Classes of Timed Automata and the Undecidability of Universality

Universality for deterministic Timed Automata (TA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TA is Π₁¹-hard and it is still open whether it is π₁¹-complete. It is interesting to note that the entire arithmetical hierarchy is contained in this computability gap between determinism and nondeterminism. In this paper we consider three types of syntactical restrictions to nondeterministic TA, which may contribute to a better understanding of the universality problem for TA. For the first two types, which are of independent interest, the universality problem is shown to be Π₁¹-complete. For the third one, universality is Π₁⁰-complete, which is the same as saying that the complementary problem is complete in the recursively enumerable class. We also show that all the restrictions define proper subclasses of the class of timed languages defined by nondeterministic TA; and establish the relationships between the classes.     

Allowable coefficient perturbations with preserved stability of a Hurwitz polynomial†

Given a polynomial P(s) = a_nsⁿ + a_n?11S^n?1 + … -+ a₁s + a₀ which satisfies the Routh-Hurwitz criterion, a procedure is given for finding non-conservative upper bounds on the allowable variations of the coefficients such that the perturbed polynomial maintains the stability property.     

On the Power of DNA-Computing

Adleman used biological manipulations with DNA strings to solve some instances of the Directed Hamiltonian Path Problem. Lipton showed how to extend this idea to solve any NP problem. We prove that exactly the problems in P^NP=Δ^p₂can be solved in polynomial time using Lipton's model. Various modifications of Lipton's model, based on other DNA manipulations, are investigated systematically, and it is proved that their computational power in polynomial time can be characterized by one of the complexity classes P,Δ^p₂, orΔ^p₃.     

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

We show that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or even nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i) (ii) Permanent is not computable by polynomial-size arithmetic circuits. We also prove a (partial) converse: If Permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic circuit of polynomially bounded degree computes an identically zero polynomial.Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If then NEXP is not computable by polynomial-size arithmetic circuits. Thus establishing that RP = coRP or BPP = P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits. We also show that any derandomization of RNC would yield new circuit lower bounds for a language in NEXP.We also prove unconditionally that NEXP^RP does not have polynomial-size Boolean or arithmetic circuits. Finally, we show that if both BPP = P and low-degree testing is in P; here low-degree testing is the problem of checking whether a given Boolean circuit computes a function that is close to some low-degree polynomial over a finite field.