Uniform computational complexity of the derivatives of C∞-functions

We discuss the uniform computational complexity of the derivatives of C^∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C^∞[−1,1] such that the sequence $\text{{|g}{}^{\mathrm{(n)}}\text{(0)|}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is not bounded by any recursive function. On the other hand, we show that if f∈C^∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f⁽ⁿ⁾(x)| is bounded by 2^p(n) for all x∈[−1,1] for some polynomial p, then the sequence $\text{{f}{}^{\mathrm{(n)}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is uniformly polynomial time computable.     

Knowledge versus search: A quantitative analysis using A1

This paper analyzes the average number of nodes expanded by $\text{A1}$ as a function of the accuracy of its heuristic estimates, by treating the errors h1 - h as random variables whose distribution may vary over the nodes in the graph. The search model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root.The main result states that if the typical error grows like φ(h1) then the mean complexity of $\text{A1}$ grows approximately like G(N)exp[cφ(N)], where c is a positive constant and G(N) is O(N²). Thus, a necessary and sufficient condition for maintaining polynomial search complexity is that $\text{A1}$ be guided by heuristics with logarithmic precision, e.g. φ(N) = (log N)^k. $\text{A1}$ is shown to make much greater use of its heuristic knowledge than a backtracking procedure would under similar conditions.     

Random functions with given time correlation

First, on any sequence of real numbers (x_λ), $\text{λ ? [? Λ}{}_1\text{+ Λ] ?}\text{Z}$, the pseudo probability Pr(x, x′) of the event x_λ?[x, x′[ is defined to be the limit when Λ → ∞ of the ratio of the number of x_λ?[x, x′[ to the total number of x_λ. The a.d.f. (asymptotic distribution function) of the sequence is then defined by F(x) = Pr(? ∞, x); it possesses the properties of a d.f. (distribution function). Consequently, what is said below applies equally to a sequence of r.v. (random variables) or to a sequence of p.r.v. (pseudorandom variables) consisting of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.A weyl's polynomial ?_n(λ) is a polynomial such that one of its coefficieints other than ?(0) is irrational. Then any sequence, the fractional part of ?_n(λ), $\text{λ ? [? Λ, + Λ] ?}\text{Z}$, is asymptotically equidistributed on [0, 1].A property is given which permits the construction of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of pseudostochastically independent sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.It is known that setting Y_n = F^{(? 1)}(X_n), it is possible to transform any sequence of r.v. X_n     

Sorting using networks of deques

The number of required deques for sorting all sequences of n items in a parallel or series network of deques is considered. It is shown that the optimal number of required deques is $\text{O(n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ for a parallel network, while it is O(log n) for a series network. These orders, $\text{O(n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ and O(log n), also remain valid for the networks of restricted deques.     

Determination of a general economic location constant by monte carlo simulation

The problem of estimating the number of markets (or plants) to serve a set of sources in a given geographical area was considered. Markets were located so as to minimize total assembly cost which was considered a linear function of the weighted Euclidean distances between sources and markets. The following predictive function C_m was proposed for estimating the minimum total assembly cost for a given number of markets: $\text{C}{}_{\mathrm{m}}\text{= C}{}_1\text{?(}\text{m?1}\text{m}\text{)}{}^{\mathrm{k}}\text{(}\text{M}\text{M ? 1}\text{)}{}^{\mathrm{k}}\text{(C}{}_1\text{? C}{}_{\mathrm{M}}\text{),m = 1, 2, 3, …, M}$ where m = number of markets being located. M = maximum number of potential market sites. C₁ = minimum assembly cost when only one market is located. C_M = minimum assembly cost when all M markets are located. k = an undetermined constant which specifies the shape of the function.The validity of the C_m function and the range of the k constant were determined by computer Monte Carlo experimentation. The constant k, to a sufficient degree of approximation and ordinary use, was found independent of the number of sources and their distribution. A general economic location co     

Utilize 100% redundancy to offer higher-level multiple fault restoration in WDM networks without wavelength conversion

This study addresses the problem of achieving higher-level multi-fault restoration in wavelength division multiplexing (WDM) networks with no wavelength conversion capability. A heuristic scheme, designated as the Directional Cycle Decomposition Algorithm (DCDA), is developed to maximize the number of tolerable faults utilizing only 100% redundancy in WDM networks without wavelength conversion. The redundancy is calculated as the required spare capacity over the given working capacity. The process of identifying the maximum number of tolerable faults is modeled as a constrained ring cover set problem. DCDA decomposes this problem into three steps and has an overall computational complexity of O(∣E∣∣V∣(C + 1) + ∣E∣(C² + 1)), where ∣V∣, ∣E∣ and C represent the number of vertices, the number of edges in the graph and the number of cycles in the cycle cover, respectively. The evaluation results reveal that the average number of tolerable simultaneous faults increases considerably under DCDA and the maximum number of tolerable simultaneous faults approaches the optimal solution provided by the brute-force method. DCDA facilitates an improved best-effort multi-fault restorability for a variety of planar and non-planar network topologies. An analytical method is proposed to facilitate a rapid estimation of the multi-fault restorability in a network using DCDA without the need for experimental evaluations. In addition, an approximation method is developed to obtain an estimate of the multi-fault restorability directly from DCDA without the requirement for a detailed knowledge of the network topology and restoration routes. The results show that the average errors in the approximated restorability values obtained using this method range from 0.12% (New Jersey) to 1.58% (Cost 239).     

Asymptotic properties of minimax trees and game-searching procedures

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P₀ and 1 ? P₀, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P₀ is higher or lower than some fixed-point probability $\text{P1(d)}$. When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value $\text{v1}$, which is the $\text{(1 ? P1)-}\text{fractile}$ of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions if positions if $\text{P}{}_0\text{≠ P1}$ and $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions if $\text{P}{}_0\text{= P1}$, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.     

On a fourth-order unconditionally stable scheme for damped second-order systems

We consider the damped second-order system $\text{M}\text{u}\text{?}\text{+ C/.u + Ku = F(t)}$ (M, C, K symmetric, positive definite n × n matrices) by conversion to an equivalent first-order system

$\text{I}\text{O}\text{O}\text{M}\text{d}\text{d}\text{t}\text{O}\text{?K}\text{I}\text{?C}\text{u}\text{u}\text{?}\text{+}\text{o}\text{F(t)}$

We demonstrate that an algorithm proposed by Fairweather for the implementation of the (2, 2) Padé approximation of the exponential matrix for approximating the solution of homogeneous first-order systems extends advantageously to this case, yielding an unconditionally stable fourth-order scheme with the feature that the approximating equations decouple. As a result we are required only to solve one symmetric complex n × n system of linear algebraic equations at each time step, with a fixed matrix which may be decomposed into triangular factors at the outset. We also consider iterative schemes involving only real, positive definite, symmetric n × n matrices. Numerical results are included.     

On time versus space II

Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a bounded machine, where n is the length of the input. A class $\text{E}$ of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in $\text{E}$ can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine.     

Optimal utilization of fixed-capacity channels in feedback control

The performance limitations on the linear control of a linear plant, due to the presence of a feedback channel with finite information capacity, are considered in this paper. This situation may arise in such diverse applications as (a) the remote control of a plant, using a digital data link for feedback, (b) where quantization errors and bit errors of a digital controller may be modelled as occurring in a noisy digital channel in cascade with an ideal controller, and (c) in human-operator modelling, where the sensory feedback channels are characterized by fixed information capacity due to neural noise. The principle result obtained is that, given the state-dimension n of the plant and the channel capacity ?, reliability function E(R), and block encoding time $\text{T> >}\text{1}\text{C}$, the optimum data-rate R satisfies the equation 2R=nE(R). This rate provides the optimum tradeoff between the effects of quantization errors and message errors. It is seen that R_opt→C as n becomes large, but that good channel performance is retained provided that $\text{> >}\text{n}\text{T}$.     

Texture classification using features derived from random field models

This paper presents a new feature extraction method for classifying a texture image into one of the l possible classes C_i, i=1,…,l. It is assumed that the given M × M image characterized by a set of intensity levels, {y(s₁,S₂), 0≤s_s,s₂≤M?1}, is a realization of an underlying random field model, known as the Simultaneous Autoregressive Model (SAR). This model is characterized by a set of parameters φ whose probability density function p_i(φ), depends on the class to which the image belongs. First it is shown that the maximum likelihood estimate (M.L.E.) $\text{φ}{}^1$, of φ is an appropriate feature vector for classification purposes. The optimum Bayes classifier which minimizes the average probability of classification error, is then designed using $\text{φ}{}^1$. Finally the efficiency of the feature vector is demonstrated through experimental results obtained with some natural texture data and a simpler quadratic mean classifier.     

An HP-67/97 network analyser for EE students

This paper describes an a.c. network analysis program designed for R/g_m/C networks which contain up to 4 nodes, including the reference (ground) node. It gives the transfer function $\text{A(f) =}\text{V}{}_{\mathrm{out}}\text{V}{}_{\mathrm{in}}$ for specified frequency f. either as single-frequency points or as multiple-frequency sweep. It also gives the band-edge (3 dB) frequencies and poles zeros of the transfer function. The network is specified by entering component values and node numbers associated with each component. The program is segmented in two parts, each of 224 HP-67/97 program steps: part 1 deals with internal computation of the polynomial coefficients of the network, while part 2 computes and displays the output parameters. The program is of interest to Electrical Engineering students, particularly those who are studying the basics of linear circuit analysis and design.     

Qualitative relativizations of complexity classes

The principal result of this paper is a “positive relativization” of the open question “P = ?$\text{NP ? co-NP}$.” That is, the nondeterministic polynomial time-bounded oracle Turing machine endowed with designated accepting states and with designated rejecting states is considered, and suitable restrictions R of this device are developed such that $\text{P = NP ? co-NP}$ if and only if for every oracle D, P(D) = NP_R(D), where NP_R(D) is the class of languages L?NP(D) that are accepted by oracle machines operating with restrictions R. Positive relativizations are obtained for the P = ? $\text{U}$ ? co - $\text{U}$ and $\text{U}$ = ? NP questions also, where $\text{U}$ is the class of languages L in NP accepted by nondeterministic machines that operate in polynomial time and that have for each input at most one accepting computation. The restrictions developed here are “qualitative” in the sense that they restrict the form and pattern of access to the oracle. In contrast, a previous paper [3] developed quantitative relativizations-the number of distinct queries to the oracle is restricted-but no quantitative positive relativization of $\text{P = ? NP ? co-NP}$ is known.     

Selection and sorting with limited storage

When selecting from, or sorting, a file stored on a read-only tape and the internal storage is rather limited, several passes of the input tape may be required. We study the relation between the amount of internal storage available and the number of passes required to select the Kth highest of N inputs. We show, for example, that to find the median in two passes requires at least $\text{ω(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ and at most $\text{O(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log N)}$ internal storage. For probabilistic methods, $\text{θ(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ internal storage is necessary and sufficient for a single pass method which finds the median with arbitrarily high probability.     

An upper bound on the mean-square error in the sampling expansion for non-band-limited processes

An upper bound is obtained on the mean-square error involved when a real-valued non-band-limited nonstationary random process x(t) is approximated by the sampling expansion

$\text{∑}\text{n=?∞}\text{∞}\text{x(nT)}\text{sin}\text{π(t?nT)/T}\text{π(t?nT)/T}$

for some T > 0. When the process x(t) is band-limited over [$\text{?}\text{1}\text{2T}\text{,}\text{1}\text{2T}$], this error bound reduces to zero.     

One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.