Relationships between pushdown automata with counters and complexity classes

In this paper a machine model is defined whose access to the storage cells is controlled by means of address registers. It is shown that every set acceptable by such a machine within time boundcn ^p,p , is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log₂ n. On the other hand every set acceptable by a deterministicp-head two-way pushdown automaton can be accepted by this machine model within time boundcn ^plog₂ n. A result similar to one of the main theorems (theorem 4) of this paper has been proved also by S. A. Cook. Both proofs are based on the same idea but have been found independently.     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Splitting a configuration in a simplex

This paper presents a new method of partition, named-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and let be a sequence of nonnegative integers ₁, ..., n_d+1 satisfying _i=1 ^d+1 ₁=n The-splitter of (T, S) is a pointG inT such thatT(G;i) contains at least _i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting.The existence of a-splitting is shown for any (T, S) and, and two efficient algorithms for finding such a splitting are given. One runs inO(d²n logn + d³n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.     

On reducing the number of states in a PDA

A transformation is presented which converts any pushdown automaton (PDA)M ₀ withn ₀ states andp ₀ stack symbols into an equivalent PDAM withn states and n ₀ /n² p ₀ stack symbols into an equivalent ofn, 1n ₀. This transformation preserves realtime behavior but not derterminism. The transformation is proved to be the best possible one in the following sense: for each choice of the parametersn ₀ + 1 stack symbols for any desired value realtime PDAM ₀ such that any equivalent PDAM (whether realtime or not) havingn states must have at least (n ₀ /n)² p₀ stack symbols. Furthermore, the loss of deterministic behavior cannot be avoided, since for each choice ofn ₀ andp ₀, there is a deterministic PDAM ₀ such that no equivalent PDAM with fewer states can be deterministic.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and MCS76-10076A01.     

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.     

Algorithms for computing the center of area of a convex polygon

The center of area of a convex polygonP is the unique pointp ^* that maximizes the minimum area overlap betweenP and any halfplane that includesp ^*. We show thatp ^* is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n ⁶ log² n). The second is a numerical algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.Research partially supported by the second author's NSF grant CCR-8351468, at Johns Hopkins University and Smith College.     

Applications of the crossing number

LetG be a graph ofn vertices that can be drawn in the plane by straight-line segments so that nok+1 of them are pairwise crossing. We show thatG has at mostc _k nlog^2k–2 n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdós, Kupitz, Perles, and others. We also construct two point sets {p ₁,,p _n }, {q ₁,,q _n } in the plane such that any piecewise linear one-to-one mappingfR ²R ² withf(pi)=qi (1in) is composed of at least (n ²) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.The first author was supported by NSF Grant CCR-91-22103, PSC-CUNY Research Award 663472, and OTKA-4269. An extended abstract of this paper was presented at the 10th Annual ACM Symposium on Computational Geometry, Stony Brook, NY, 1994.     

A universal topological transformation group inL 2 (G × G)

LetG denote an infinite,-compact, locally compact topological group. In this paper a construction is given for a topological transformation groupH _G with the Hilbert spaceL ² (G × G) as a phase space such that any topological transformation group (G, X, ) can be embedded inH _G , providedX is a separable metrizable space and is a bounded action. The class of such topological transformation groups contains all actions ofG on separable, metrizable, locally compact spaces.     

Existence of set-interpolating and energy-minimizing curves

We consider existence of curves which minimize an energy of the form ∫c^(k)p (k=1,2,… , 1<p<∞) under side-conditions of the form G_j(c(t_1,j),…,c^(k−1)(t_k,j))M_j, where G_j is a continuous function, t_i,j[0,1], M_j is some closed set, and the indices j range in some index set J. This includes the problem of finding energy minimizing interpolants restricted to surfaces, and also variational near-interpolating problems. The norm used for vectors does not have to be Euclidean.It is shown that such an energy minimizer exists if there exists a curve satisfying the side conditions at all, and if among the interpolation conditions there are at least k points to be interpolated. In the case k=1, some relations to arc length are shown.     

Optimal design of rigid-plastic annular plates with piecewise constant thickness

Rigid-plastic stepped annular plates under uniform pressure load are considered. Both plate edges are supported. Four types of boundary conditions are studied. Tresca's yield condition is used. Such plate dimensions are sought for which the plate of constant volume has the maximal load carrying capacity.Notation a, d, R, h ₁, h₂ plate dimensions (Fig. 1) - Q ^* shear force - Q dimensionless shear force - M _r ^* radial bending moment - M ₁ dimensionless radial bending moment - M _t ^* circumferential bending moment - M ₂ dimensionless circumferential bending moment - M _k maximum value of bending moments in the rigid region - p ^* uniform pressure load - p dimensionless uniform pressure load - r radial coordinate - x dimensionless radial coordinate - , , dimensionless parameters for plate (5) - V plate volume - dimensionless plate volume - M ₀ ^* yield moment - ₀ yield stress - p ₀ load carrying capacity - p ₀ ^m maximum value of the load carrying capacity - p ₀ ^u load carrying capacity for uniform plate - ^m, ^m optimal parameters, which correspond to the maximum value ofp ₀ - s _i radius of circle between different plastic stages - () /x     

On ACC

We show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and AND gates of fan-in log ^O(1) n at the leaves, or equivalently, there exist polynomialsp _n (x ₁ ,..., x _n ) overZ of degree log ^O(1) n and with coefficients of magnitude and functionsh _n :Z{0,1} such that for eachn and eachx{0,1} ⁿ ,XL ^(x) =h _n (p _n (x ₁ ,...,x _n )). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985).     

On polynomial-time truth-table reducibility of intractable sets to P-selective sets

The existence of setsnot being _tt ^P -reducible to low sets is investigated for several complexity classes such as UP, NP, the polynomial-time hierarchy, PSPACE, and EXPTIME. The p-selective sets are mainly considered as a class of low sets. Such investigations were done in many earlier works, but almost all of these have dealt withpositive reductions in order to imply the strongest consequence such as P=NP under the assumption that all sets in NP are polynomial-time reducible to low sets. Currently, there seems to be some difficulty in obtaining the same strong results undernonpositive reducibilities. The purpose of this paper is to develop a useful technique to show for many complexity classes that if each set in the class is polynomial-time reducible to a p-selective set via anonpositive reduction, then the class is already contained in P. The following results are shown in this paper.(1) If each set in UP is _tt ^P -reducible to a p-selective set, then P=UP.(2) If each set in NP is _tt ^P -reducible to a p-selective set, then P=FewP and R=NP.(3) If each set in ₂ ^P is _tt ^P -reducible to a p-selective set, then P=NP.(4) If each set in PSPACE is _tt ^P -reducible to a p-selective set, then P=PSPACE.(5) There is a set in EXPTIME that is not _tt ^P -reducible to any p-selective set.It remains open whether P=NP follows from a weaker assumption that each set in NP is _tt ^P -reducible to a p-selective set.     

Maximum induced subgraph of a recursive circulant

The recursive circulant RC(n²,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p₀>p₁>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n²,4). The conclusion shows that, as n-dimensional cube, RC(n²,4) enjoys a linear bisection width.     

On the equivalence and containment problems for context-free languages

LetG andG ₀ be context-free grammars. Necessary and sufficient conditions onG ₀ are obtained for the decidability ofL(G ₀) L((G) It is also shown that it is undecidable for whichG ₀,L(G) is decidable. Furthermore, given thatL(G) is decidable for a fixedG ₀, there is no effective procedure to determine the algorithm which decidesL(G) IfL(G ₀) is a regular set,L(G) = L(G ₀) is decidable if and only ifL(G ₀) is bounded. However, there exist non-regular, unboundedL(G ₀) for whichL(G) = L(G ₀) is decidable.     

Propositional truth maintenance systems: Classification and complexity analysis

Truth maintenance (TM) has been an active area of artificial intelligence (AI) research in recent years. In particular, truth maintenance systems (TMSs) in many variant types have become popular mechanisms for implementing nonmonotonic inference systems. Knowledge about the computational foundations of a TMS is indispensable for their use. We present a classification of computational complexity of tasks performed by basic existing TMS types. Our results include the proof ₂ ^p -completeness of the clause maintenance system's computation task. This is the first problem in AI proved to be ₂ ^p -complete. It is likely to provide a basis for proving ₂ ^p -completeness of other problems in logic and AI. As part of the proof, we prove the ₂ ^p -completeness of the generalized node deletion problem, one of the first natural graph problems to be complete for any one of the classes _i ^p , forp>1. We also prove the polynomial equivalence of Boolean Constraint Propagation-based (logic-based) approaches (LTMSs) and justification-based approaches (JTMSs) to TM, and exhibit efficient algorithms for transforming an LTMS into a JTMS and vice versa.     

Existence and efficient construction of fast Fourier transforms on supersolvable groups

The linear complexityL _K(A) of a matrixA over a fieldK is defined as the minimal number of additions, subtractions and scalar multiplications sufficient to evaluateA at a generic input vector. IfG is a finite group andK a field containing a primitive exp(G)-th root of unity,L _K(G):= min{L _K(A)|A a Fourier transform forKG} is called theK-linear complexity ofG. We show that every supersolvable groupG has amonomial Fourier Transform adapted to a chief series ofG. The proof is constructive and gives rise to an efficient algorithm with running timeO(|G|²log|G|). Moreover, we prove that these Fourier transforms are efficient to evaluate:L _K(G)8.5|G|log|G| for any supersolvable groupG andL _K(G)1.5|G|log|G| for any 2-groupG.     

Stabilizability of linear systems defined overC *-algebras

LetF andG be elements of aC ^*-algebraA. Assume that, for each irreducible^*-representation ofA on a Hilbert space210B; , there is a bounded linear operatorL B( ) such that the spectrum of(F) –(G)L is contained in the open left half plane. We prove that there is then an elementL A such that the spectrum ofF — GL is contained in the open left half plane. That is, if the system (F, G) is locally stabilizable, then it is stabilizable. We also consider the analogous problem with the open left half plane replaced by the open unit disk.This paper was supported in part by the National Science Foundation under Grant NSF-MCS-8002138.     

Optimum design of Beck's column with a constraint on the static buckling load

The paper is concerned with optimization of a damped column subjected to a follower load. The aim is to determine the colum of least volume which has the same critical load as a uniform reference column. The stability analysis is based on the finite element method. The optimization problem is solved by sequential linear programming. By only including a constraint on the flutter load in the volume minimization, a very large volume reduction is possible but the static buckling load (by a pure conservative loading) becomes very small.In applications, it may be important that the optimal column also is capable of supporting a conservative load. Consequently, the volume is minimized with constraints on both the flutter load and the static buckling load. The constraint on the buckling loadp _b has the formp _b ^opt cp _b ⁰ , 0c1, where the upper index opt refers to the optimal design while the upper index 0 refers to the uniform initial design. It is found that, as the constantc approaches 1, the optimal column approaches the optimal Euler column of Tadjbakhsh and Keller (1962).Notation c slack parameter on the constraint on the static buckling load; defined by (9) - c _int,c _ext dimensionless internal and external damping parameters defined by (3) - d _j eigenvalue margin defined by (9) - d vector of time-independent nodal displacements and rotations - _e length of thee-th finite element - L total length of the column - vector of element lengths defined by (11) - m, m(x) mass distribution function - m _i design variables; the mass distribution function evaluated at the nodal points - upper and lower bounds on the design parameters - m design vector with elementsm _i - M mass matrix - N _e the number of finite elements used - p load parameter - Q load matrix - S stiffness matrix - t time - x distance along the column, measured from the clamped end - y lateral deflection of the column - y vector of nodal displacements and rotations - complex eigenvalue - b refers to buckling (static instability by conservative loading) - d refers to divergence (static instability by nonconservative loading) - f refers to flutter (dynamic instability by nonconservative loading)     

Reduction of Permutation-Invariant Polynomials: A Noncommutative Case Study

Let R be a commutative ring with 1, let RX₁,…,X_n/I be the polynomial algebra in the n≥4 noncommuting variables X₁,…,X_n over R modulo the set of commutator relations I={(X₁+···+X_n)*X_i=X_i*(X₁+···+X_n)|1≤i≤n}. Furthermore, let G be an arbitrary group of permutations operating on the indeterminates X₁,…,X_n, and let RX₁,…,X_n/I^G be the R-algebra of G-invariant polynomials in RX₁,…,X_n/I. The first part of this paper is about an algorithm, which computes a representation for any fRX₁,…,X_n/I^G as a polynomial in multilinear G-invariant polynomials, i.e., the maximal variable degree of the generators of RX₁,…,X_n/I^G is at most 1. The algorithm works for any ring R and for any permutation group G. In addition, we present a bound for the number of necessary generators for the representation of all G-invariant polynomials in RX₁,…,X_n/I^G with a total degree of at most d. The second part contains a first but promising analysis of G-invariant polynomials of solvable polynomial rings.     

On the Schröder-Bernstein problem for abelian lattice ordered groups and for <Emphasis Type="Italic">MV</Emphasis>-algebras

In this note we deal with abelian lattice ordered groups G having direct summands G₁ and G₂ such that GG₁G₂, G is isomorphic to G₂ but not to G₁. Further, we investigate an analogous condition for MV-algebras.Supported by grant VEGA 1/9056/22