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.     

A Lie-Group Formulation of Kinematics and Dynamics of Constrained MBS and Its Application to Analytical Mechanics

A Lie-group formulation for the kinematics and dynamics ofholonomic constrained mechanical systems (CMS) is presented. The kinematics ofrigid multibody systems (MBS) is described in terms of the screw system of theMBS. Using Lie-algebraic properties of screw algebra, isomorphicto se(3), allows a purely algebraic derivation of the Lagrangian motion equations. As such the Lie-group SE(3) ... SE(3) (n copies) is theambient space of a MBS consisting of n rigid bodies. Any parameterizationof the ambient space corresponds to a chart on the MBS configuration space ⁿ. The key to combine differential geometric and Lie-algebraic approaches is the existence of kinematic basic functions whichare push forward maps from the tangent bundle Tⁿ to the Lie-algebra of the ambient space.MBS with kinematic loops are CMS subject to holonomic constraints, holonomicCMS. Constraint equations are formulated on the ambient space based on achart on ⁿ. Explicitly considering the Lie-algebraicstructure of se(3) as semidirect sum of the algebra oftranslations and rotations enables to reduce the number of holonomicconstraints for cut joints. It is shown that third order Lie-brackets are sufficient to obtain any subalgebra of se(3).Differential geometric aspects of the kinematics of MBS with open and closedkinematic chains are considered. The distribution in any configuration andthe subalgebra generated by the screw system of a mechanism is the key todetect singularities and to analyze the structure of the set of singularpoints.     

Deriving constraints among argument sizes in logic programs

In a logic program the feasible argument sizes of derivable facts involving ann-ary predicate are viewed as a set of points in the positive orthant of ⁿ . We investigate a method of deriving constraints on the feasible set in the form of a polyhedral convex set in the positive orthant, which we call apolycone. Faces of this polycone represent inequalities proven to hold among the argument sizes. These inequalities are often useful for selecting an evaluation method that is guaranteed to terminate for a given logic procedure. The methods may be applicable to other languages in which the sizes of data structures can be determined syntactically.For any atomic formula (atom, for short) in a rule, we show how to express the vector of its argument sizes as a system of linear equations and inequalities involving sizes of the logical variables that occur in it. This system defines a polycone, which represents the set offeasible argument size vectors. Transformations combine polycones for all atoms in one rule to give the feasible polycone for the entire rule.We introduce ageneralized Tucker representation for systems of linear equations. We prove that every polycone has a uniquenormal form in this representation, and give an algorithm to produce it. This in turn gives a decision procedure for the question of whether two sets of linear equations define the same polycone.When a predicate has several rules, the union of the individual rule's polycones gives the set of feasible argument size vectors for the predicate. Because this set is not necessarily convex, we instead operate with the smallest enclosing polycone, which is the closure of the convex hull of the union. Retaining convexity is one of the key features of our technique.Recursion is handled by finding a polycone that is a fixpoint of a transformation that is derived from both the recursive and nonrecursive rules. Some methods for finding a fixpoint are presented, but there are many unresolved problems in this area.An extended abstract of this paper appeared in9th ACM Symposium on Principles of Database Systems, March 1990.     

The residue of vector sets with applications to decidability problems in Petri nets

Summary A set K of integer vectors is called right-closed, if for any elementmK all vectors mm are also contained in K. In such a case K is a semilinear set of vectors having a minimal generating set res(K), called the residue of K. A general method is given for computing the residue set of a right-closed set, provided it satisfies a certain decidability criterion.Various right-closed sets wich are important for analyzing, constructing, or controlling Petri nets are studied. One such set is the set CONTINUAL(T) of all such markings which have an infinite continuation using each transition infinitely many times. It is shown that the residue set of CONTINUAL(T) can be constructed effectively, solving an open problem of Schroff. The proof also solves problem 24 (iii) in the EATCS-Bulletin. The new methods developed in this paper can also be used to show that it is decidable, whether a signal net is prompt [23] and whether certain -languages of a Petri net are empty or not.It is shown, how the behaviour of a given Petri net can be controlled in a simple way in order to realize its maximal central subbehaviour, thereby solving a problem of Nivat and Arnold, or its maximal live subbehaviour as well. This latter approach is used to give a new solution for the bankers problem described by Dijkstra.Since the restriction imposed on a Petri net by a fact [11] can be formulated as a right closed set, our method also gives a new general approach for implementations of facts.     

On intractability of the classUP

The classUP [V] is the class of sets accepted by polynomial-time nondeterministic Turing machines which have at most one accepting path for every input. The complexity of this class closely relates to that of computing inverses ofone-way functions, where a one-way function is a one-to-one, length-increasing, and polynomial-time computable function whose inverse cannot be computed within polynomial time. It is known [GS], [K] that there exists a one-way function if and only ifP UP. In this paper the intractability of sets inUP is investigated in terms of polynomial-time reducibility to a sparse set. It is shown thatUP has a set that is _m ^P -reducible to no sparse set ifP UP. We interpret this structural property in the relation with approximation algorithms: it is shown that ifP UP, thenUP has a set with no 1-APT approximation and, furthermore,UP has a set that is not _m ^P -reducible to any set with a 1-APT approximation. The implication of this result in the study of one-way functions is also discussed. In order to prove the main theorem, we introduce a variation of tree-pruning methods.This paper was written while the author visited the Department of Mathematics, University of California, Santa Barbara. This research was supported in part by the National Science Foundation under Grant CCR-8611980.     

Lower bounds for set intersection queries

We consider the followingset intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence ofn updates (insertions into and deletions from individual sets) andq queries (reporting the intersection of two sets). We cast this problem in thearithmetic model of computation of Fredman [F1] and Yao [Ya2] and show that any algorithm that fits in this model must take time (q+nq) to process a sequence ofn updates andq queries, ignoring factors that are polynomial in logn. We also show that this bound is tight in this model of computation, again to within a polynomial in logn factor, improving upon a result of Yellin [Ye]. Furthermore, we consider the caseq=O(n) with an additional space restriction. We only allow the use ofm memory locations, wherem n^3/2. We show a tight bound of (n²/m^1/3) for a sequence ofn operations, again ignoring the polynomial in logn factors.     

Interval propagation to reason about sets: Definition and implementation of a practical language

Local consistency techniques have been introduced in logic programming in order to extend the application domain of logic programming languages. The existing languages based on these techniques consider arithmetic constraints applied to variables ranging over finite integer domains. This makes difficult a natural and concise modelling as well as an efficient solving of a class of NP-complete combinatorial search problems dealing with sets. To overcome these problems, we propose a solution which consists in extending the notion of integer domains to that of set domains (sets of sets). We specify a set domain by an interval whose lower and upper bounds are known sets, ordered by set inclusion. We define the formal and practical framework of a new constraint logic programming language over set domains, called Conjunto. Conjunto comprises the usual set operation symbols (, , \), and the set inclusion relation (% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeaacaGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!37EA!\[ \subseteq \]). Set expressions built using the operation symbols are interpreted as relations (s s ₁ = s ₂, ...). In addition, Conjunto provides us with a set of constraints called graduated constraints (e.g. the set cardinality) which map sets onto arithmetic terms. This allows us to handle optimization problems by applying a cost function to the quantifiable, i.e., arithmetic, terms which are associated to set terms. The constraint solving in Conjunto is based on local consistency techniques using interval reasoning which are extended to handle set constraints. The main contribution of this paper concerns the formal definition of the language and its design and implementation as a practical language.     

On being incoherent without being very hard

Trakhtenbrot calls a setA autoreducible ifA is Turing-reducible toA via an oracle Turing machine that never queries the oracle about the input string. Yao considers sets that are autoreducible via probabilistic, polynomial-time oracle Turing machines, and he calls such setscoherent. We continue the study of autoreducible sets, including those that are autoreducible via a family of polynomial-sized circuits, which we callweakly coherent. Sets that are not weakly coherent are calledstrongly incoherent. We show

Universal dynamical systems

This paper is concerned with the problem of finding a universal dynamical system for all dynamical systems on separable metric spaces. Special care is given to exhibit a universal dynamical system which was used to motivate the definition of a dynamical system. We establish that this class of dynamical systems is topologically as narrow as a system describable by a first-order partial differential equation. We find that a classical solution space of this partial differential equation will serve as the phase space of a universal system for dynamical systems on locally compact separable metric spaces. In fact, the functions in this solution space areC and vanish at infinity. For the remaining dynamical systems on separable metric spaces we find a universal system similar to the shift system exhibited by Bebutov. The marked difference is that there is no restriction on the set of rest points. Further comments concerning the history of this problem follow some basic definitions given in the introduction.     

Polynomial-time compression

This paper studies the class ofinfinite sets that have minimal perfect hash functions—one-to-one onto maps between the sets and ^*-computable in polynomial time. We will call such sets P-compressible. We show that all standard NP-complete sets are P-compressible, and give a structural condition,E = ₂ ^E , sufficient to ensure thatall infinite NP sets are P-compressible. On the other hand, we present evidence that some infinite NP sets, and indeed some infinite P sets, are not P-compressible: if an infinite NP setA is P-compressible, thenA has an infinite sparse NP subset, yet we construct a relativized world in which some infinite NP sets lack infinite sparse NP subsets. This world is built upon a result that is of interest in its own right; we determine optimally—with respect to any relativizable proof technique—the complexity of the easiest infinite sparse subsets that infinite P sets are guaranteed to have.     

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.     

Relativized isomorphisms of NP-complete sets

In this paper, we present several results about collapsing and non-collapsing degrees ofNP-complete sets. The first, a relativized collapsing result, is interesting because it is the strongest known constructive approximation to a relativization of Berman and Hartmanis' 1977 conjecture that all _m ^P -complete sets forNP arep-isomorphic. In addition, the collapsing result explores new territory in oracle construction, particularly in combining overlapping and apparently incompatible coding and diagonalizing techniques. We also present non-collapsing results, which are notable for their technical simplicity, and which rely on no unproven assumptions such as one-way functions. The basic technique developed in these non-collapsing constructions is surprisingly robust, and can be combined with many different oracle constructions.     

Optimal Control of the Sphere S n Rolling on E n

This paper investigates the optimal control problem concerning the sphere Sⁿ rolling without slipping on n-dimensional Euclidean space Eⁿ, n2. The differential equations governing the behaviour of the sphere constitute a sub-Riemannian distribution on the Lie group G=ⁿ×SO_n+1. Minimizing over the lengths of paths traced by the point of contact of the sphere yields an optimal control problem which is exploited using Noethers Theorem to derive a family of integrals of motion for the system. This family is then employed to prove that all optimizing trajectories are projections of normal extremals. The Lax form of the extremal equations gives rise to an additional family of integrals which is reminiscent of the Manakov integrals of motion for the free rigid body problem. Both families are required to show complete integrability if n=4.     

Linear Transformation Groups and Shape Space

The problem of modelling variabilities of ensembles of objects leads to the study of the shape of point sets and of transformations between point sets. Linear models are only able to amply describe variabilities between shapes that are sufficiently close and require the computation of a mean configuration. Olsen and Nielsen (2000) introduced a Lie group model based on linear vector fields and showed that this model could describe a wider range of variabilities than linear models. The purpose of this paper is to investigate the mathematics of this Lie group model further and determine its expressibility. This is a necessary foundation for any future work on inference techniques in this model.Let ^k _m denote Kendall's shape space of sets of k points in m-dimensional Euclidean space (k > m): this consists of point sets up to equivalence under rotation, scaling and translation. Not all linear transformations on point sets give well-defined transformations of shapes. However, we show that a subgroup of transformations determined by invertible real matrices of size k – 1 does act on ^k _m. For m > 2, this group is maximal, whereas for m = 2, the maximal group consists of the invertible complex matrices. It is proved that these groups are able to transform any generic shape to any other. Moreover, we establish that for k > m + 1 this may be done via one-parameter subgroups. Each one-parameter subgroup is given by exponentiation of an arbitrary (k – 1) × (k – 1) matrix. Shape variabilities may thus be modelled by elements of a (k – 1)²-dimensional vector space.     

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.     

Migration Processes I: The Continuous Case

In this paper the general concept of a migration process (MP) is introduced; it involves iterative displacement of each point in a set as function of a neighborhood of the point, and is applicable to arbitrary sets with arbitrary topologies. After a brief analysis of this relatively general class of iterative processes and of constraints on such processes, we restrict our attention to processes in which each point in a set is iteratively displaced to the average (centroid) of its equigeodesic neighborhood. We show that MPs of this special class can be approximated by reaction-diffusion-type PDEs, which have received extensive attention recently in the contour evolution literature. Although we show that MPs constitute a special class of these evolution models, our analysis of migrating sets does not require the machinery of differential geometry. In Part I of the paper we characterize the migration of closed curves and extend our analysis to arbitrary connected sets in the continuous domain (R^m) using the frequency analysis of closed polygons, which has been rediscovered recently in the literature. We show that migrating sets shrink, and also derive other geometric properties of MPs. In Part II we will reformulate the concept of migration in a discrete representation (Z^m).     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

Optimal Point-Wise Error Estimate of a Compact Difference Scheme for the Coupled Gross–Pitaevskii Equations in One Dimension

The coupled Gross–Pitaevskii (CGP) equation studied in this paper is an important mathematical model describing two-component Bose–Einstein condensate with an internal atomic Josephson junction. We here analyze a compact finite difference scheme which conserves the total mass and energy in the discrete level for the CGP equation. In general, due to the difficulty caused by compact difference on nonlinear terms, optimal point-wise error estimates without any restrictions on the grid ratios of compact difference schemes for nonlinear partial differential equations are very hard to be established. To overcome the difficulty caused by the compact difference operator, we introduce a new norm and an interesting transformation by which the difference scheme is transformed into a special equivalent vector form, we then use the energy method and some important lemmas on the equivalent system to obtain the optimal convergent rate, without any restrictions on the grid ratio, at the order of $O(h^{4}+\tau ^2)$ in the maximum norm with time step $\tau $ and mesh size $h$ . Finally, numerical results are reported to test the theoretical results and simulate the dynamics of the CGP equation.     

Towards separating nondeterminism from determinism

The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) ^1/k ). This implies, for example that for any positive integer,l,l k, there is a language accepted by an ^l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n ^l ) andO((logn) ^l ) respectively for anyl. Such a result is not provable by direct diagonalization because we do not have time to simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.Supported by NSF Grant No. MCS-8105557