Polynomial Time Introreducibility

Abstract. We introduce the polynomial time version, in short ≤ ^P _T -introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is ≤ ^P _T -introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities ≤ _r , showing that a set is ≤ _r -introreducible if and only if it belongs to the minimum ≤ _r -degree. It also holds for most unbounded reducibilities like ≤ _m , ≤ _c , ≤ _d , ≤ _p , ≤ _tt , etc., but it does not hold for ≤ _T . A very strong way for a set L to fail being ≤ _r -introreducible is that L is not ≤ _r -reducible to any coinfinite subset of L . We call such sets ≤ _r -introimmune. It is known that ≤ _T -introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities ≤ _r there exist arithmetical ≤ _r -introimmune sets. We show that they exist for the reducibilities ≤ _c and ≤ ^N _m . Finally, we prove separation results between introimmunities.     

Konvergenzordnungen von Ein- und Mehrschrittverfahren bei gewöhnlichen Differentialgleichungen

For one- and multistep methods for numerical integration of ordinary differential equations,y'=f(x, y) (a≤x≤b),y (a)=y _a we prove intermediate convergence estimates of the following type:f ε Lip (α, p; Q) ?y _h=y+0 (h ^α) (0<α≤p) wherey _h denotes the approximate solution. The results extend classical ones.     

Computational experience with an algorithm for discrete L1 approximation

In a recent paper Wolfe [13] proposes and analyses an algorithm for discrete linearL _p approximation with 1≤p<2. In particular he gives a local convergence result for the casep=1. For this case, we discuss the implementation of the method, illustrate its performance on some examples, and draw some comparisons with the linear programming based method of Barrodale and Roberts [3].     

Gewichtsoptimale Quadraturformeln bei analytischen Funktionen

On spaces of analytic functions withL _p -norms, 1≤p≤∞, the norm of the quadrature error functional of rules with special fixed nodes is minimized with respect to the weights. These unique determined optimal weights and the corresponding error norm are evaluated.     

On Steiner minimal trees withL p distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ ?x ₂¦ ^p + ¦y₁ ?y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ? _p to be inf{L _s (P)/L _m (P)¦P?L _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ?₁ = 2/3. Chung and Graham proved ?₂ > 0.842. We prove in this paper that ?{∞} = 2/3 and √(√2/2)?₁?₂ ≤ ?_p ≤ √3/2 for anyp.     

Fehlernormen zur Quadratur analytischer Funktionen

For spaces of analytic functionsf(z) withL _p -norms, 1≤p≤∞, the norm of quadrature error functionals is evaluated. This is done with the aid of a suitable integralrepresentation forf(z) by means of calculation a definite integral which is carried out explicitly in some interesting cases.     

The pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine

The classical problem of scheduling theory that is NP-hard in the strong sense 1|r _j|L _max is considered. New properties of optimal schedules are found. A polynomially resolved case of the problem is selected, when the release times (r _j), the processing time (p _j), and due dates of completion of processing (d _j) of jobs satisfy the constraints d ₁ ≤ ... ≤ d _n and d ₁ ? r ₁ ? p ₁ ≥ ... ≥ d _n ? r _n ? p _n. An algorithm of run time O(n ³logn) finds Pareto-optimal sets of schedules according to the criteria L _max and C _max that contains no more than n variants.     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

The region approach for computing relative neighbourhood graphs in the Lp metric

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v ₁,v ₂, ...,v _n } of distinct points in atwo-dimensional space. The pointv _j is said to be arelative neighbour ofv _i ifd _p (v _i ,v _j )≤max{d _p (v _j ,v _k ),d _p (v _j ,v _k )} for allv _k ∈V, whered _p denotes the distance in theL _p metric, 1≤p≤∞. After dividing the space around the pointv _i into eight sectors (regions) of equal size, a closest point tov _i in some region is called anoctant (region, orgeographic) neighbour ofv _i. For anyL _p metric, a relative neighbour ofv _i is always an octant neighbour in some region atv _i. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointv _i ofV, first search for the octant neighbours ofv _i in each region, and then for each octant neighbourv _j found check whether the pointv _j is also a relative neighbour ofv _i. In theL _p metric, 1<p<∞, the total number of octant neighbours is shown to be θ(n) for any set ofn points; hence, even a straightforward implementation of the above method runs in θn ²) time. In theL ₁ andL _∞ metrics the method can be refined to a θ(n logn+m) algorithm, wherem is the number of relative neighbours in the output,n-1≤m≤n(n-1). TheL ₁ (L _∞) algorithm is optimal within a constant factor.     

A Time-Optimal Multiple Search Algorithm on Enhanced Meshes,with Applications

Given a sorted sequence A = a₁, a₂, ..., a_n of items from a totally ordered universe, along with an arbitrary sequence Q = q₁, q₂, ..., q_m (1 ≤ m ≤ n) of queries, the multiple search problem involves computing for every q_j (1 ≤ j ≤ m) the unique a_i for which a_i−1 ≤ q_j < a_i. In this paper we propose a time-optimal algorithm to solve the multiple search problem on meshes with multiple broadcasting. More specifically, on a [formula] × [formula] mesh with multiple broadcasting, our algorithm runs in [formula] time which is shown to be time-optimal. We also present some surprising applications of the multiple search algorithm to computer graphics, image processing, robotics, and computational geometry.     

Efficient and Scalable PRAM Algorithms for Discrete-Event Simulation of Bounded Degree Networks

We describe two new parallel algorithms, one conservative and another optimistic, for discrete-event simulation on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). The target physical systems are bounded degree networks which are represented by logic circuits. Employing p processors, our conservative algorithm can simulate up to O(p) independent messages of a system with n logical processes in O(log n) time. The number of processors, p, can be optimally varied in the range 1 ≤ p ≤ n. To identify independent messages, this algorithm also introduces a novel scheme based on a variable size time window. Our optimistic algorithm is designed to reduce the rollback frequency and the memory requirement to save past states and messages. The optimistic algorithm also simulates O(p) earliest messages on a p-processor computer in O(log n) time. To our knowledge, such a theoretical efficiency in parallel simulation algorithms, conservative or optimistic, has been achieved for the first time.     

Zur Konvergenz der Ableitungen von Interpolationspolynomen

Letp _n denote the polynomial of degreen or less that interpolates a given smooth functionf at the ?eby?ev nodest _j ⁿ =cos(jπ/n), 0≤j≤n, and let ‖·‖ be the maximum norm inC[?1, 1]. It is proved that fork-th derivatives (2≤k≤n) estimates of the following type hold $$\parallel f^{(k)} - p_n^{(k)} \parallel \leqslant c_k n^{k - 1} \inf \{ \parallel f^{(k)} - q\parallel :q \in \Pi _{n - k} \} .$$ In this relationc _k only depends onk andΠ _n?k denotes the space of polynomials up to degreen?k.     

A simple approach to the problem of 3-D reconstruction

A relatively simple mathematical procedure for the reconstruction of the 3-dimensional (3D) image of the left ventricle (LV) of the heart is presented. The method is based on the assumption that every ray whoch emanates from the midpoint of the long axis of the 3D body crosses the surface boundary of the ventricle at one and only one point. The coordinates r_i, φ_i, θ_i of the data points on, say, the outer boundary, (i.e., the epicardium) are calculated in a spherical coordinate system having its origin in the midpoint of the long axis. The problem of defining the coordinates of a prescribed grid point on the boundary is treated as an interpolation problem for the function r = r(φ, θ), defined in the rectangle 0 ≤ φ ≤ 2π; 0 ≤ θ ≤ π with r_i given in the points (φ_i, θ_i).     

Moment inequalities for random variables in computational geometry

LetX ₁,...,X _n be independent identically distributedR ^d -valued random vectors, and letA _n =A(X ₁,...,X _n ) be a subset of {X ₁,...,X _n }, invariant under permutations of the data, and possessing the inclusion property (X ₁ ∈A _n impliesX ₁ ∈A _i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these conditions. LetN _n be the cardinality ofA _n . We show that for allp≥1, there exists a universal constantC _p >0 such thatE(N _n ^p )≤C _p max (1,E ^p ) where . This complements Jensen's lower bound for thep-th moment:E(N _n ^p )≥E ^p (N _n ). The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N _n ) for linear expected time behaviour of divide-and-conquer methods for findingA _n .     

Global attractivity for a nonlinear difference equation with variable delay

In this paper, we give sufficient conditions under which every solution of the nonlinear difference equation with variable delay x(n + 1) − x(n) + p_nf(x(g(n))) = 0, n = 0, 1, 2, … tends to zero as n → ∞. Here, p_n is a nonnegative sequence, f : R → R is a continuous function with xf(x) > 0 if x ≠ 0, and g : N → Z is nondecreasing and satisfies g(n) ≤ n for n ≥ 0 and lim_n→∞ g(n) = ∞.     

Parallel Heap Operations on an EREW PRAM

We consider parallel heap operations on the exclusive-read exclusive-write parallel random-access machine. We first present an O(n/p + log p) time parallel algorithm to construct a heap of n elements using p processors, which is optimal for p θ(n/log n). We then propose a parallel root deletion algorithm. In a preparatory step, a data structure for dynamic processor allocation is constructed using O((n/log n)^{1 − 1/k}) processors in O(log k) time for some constant k, 1 ≤ k ≤ ⌈log(n/log n)⌉. A sequence of root deletions can then be performed, each of which takes O((log n)/p + log p + log log n) time using p processors. Finally, we discuss a parallel algorithm running in O((log n)/p + log p) time for inserting an element into a heap, which is optimal for p = θ((log n)/log log n). Both deletion and insertion algorithms run in O(log log n) time when p = θ((log n)/log log n).     

Some remarks on congruences obtained from the L-fuzzy Nakano hyperoperation

In this paper we study relations which are congruences with respect to ∧ and ?_p, where ?_p is the p-cut of the L-fuzzy hyperoperation ?. The main idea is to start from an equivalence relation R₁ which is a congruence with respect to ∧ and ?₁ and, for each p ∈ X, construct an equivalence relation R_p which is a congruence with respect to ∧ and ?_p. Furthermore, for each x ∈ R_p we construct a quotient hyperoperation ?_p and we show that the hyperalgebra (X/R_p, ?_p) is a join space and the hyperalgebra (X/R_p, ?_p, ∧_p) is a hyperlattice.     

Sensitivity minimization in an H ∞ norm: parametrization of all suboptimal solutions

A number of problems in the control of linear feedback systems can be reduced to the following: we are given three stable rational matrix functions K, ?, ψ of sizes p ₁ x q ₁, p ₁ x q ₂ and p ₂ x q ₁ respectively, and seek a stable rational q ₂ x p ₂ matrix function S so as to minimize ¦K + ?Sψ¦_∞. We assume that p ₁ ≥ q ₂, p ₂≤q ₁ and that ? and ψ have maximal rank (q ₂ and p ₂ respectively) on the jω-axis. Given a tolerance level μ sufficiently large, we obtain a linear fractional map G → F = [0 ₁₁ G + 0 ₁₂, 0 ₁₃][0 ₂₁ G + 0 ₂₂, 0 ₂₃]^?1 such that F = K + ?Sψ with S stable and ¦F _∞ ≤ μ if and only if G is a stable q ₂ x p ₂ matrix function with ¦G¦_∞ ≤ 1. The computation of 0 = [0 _ij ] (1 ≤ i ≤ 2, 1 ≤ j ≤ 3) reduces to solving a pair of symmetric Wiener–Hopf factorization problems. For the special case where ? = [I _q2, 0]^T, ψ = [I _p2, 0] (and K not necessarily stable) to which the general case can be reduced, we provide explicit state-space formulae for 0 in terms of a state-space realization of K and the solutions of some related Riccati equations. The approach is a natural extension of that of Ball–Helton and Ball–Ran for the case p ₁ = q ₂ and p ₂ = q ₁.     

Optimale Approximation mit Nebenbedingungen an lineare Funktionale auf H2 (Eϱ) und L2 (Eϱ)

For any bounded linear functional on the Hilbert space of analytic functionsH ²(E _?) (respectivelyL ²(E _?)) numerical approximations are considered. Forn ∈ ? special fixed nodes the approximation having a minimal error norm in the class of those approximations which are exact for all polynomials up to a degreei, 0≤i≤n?1, is given explicitly.