Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model

LetV be a set inR ⁿ consisting of finitely many hyperplanes. The linear recognition problem given byV is to determine, using ternary comparisons of the form “f(x):0” wheref:R ⁿ →R is a linear function, whether a pointxεR _n is inV. We consider lower bounds on the number of comparisons whenV corresponds to some NP-complete problems. A technique is proposed for proving such bounds. If the tests “f(x):0” are restricted so thatf always defines some hyperplane inV, then some NP-complete problems are shown to have exponential lower bounds inn. Examples of larger classes of linear test functions are found such that the exponential lower bounds are still valid.     

Sequences of composition operators in spaces of functions of bounded Φ-variation

The main results of the paper are contained in Theorems 1 and 2. Theorem 1 presents necessary and sufficient conditions for a sequence of functions h _n : 〈c, d〉 → 〈a, b〉, n = 1, 2, ..., to have bounded sequences of Ψ-variations {V _Ψ (〈c, d〉; f ? h _n )} _n=1 ^∞ evaluated for the compositions of an arbitrary function f: 〈a, b〉 → ? with finite Φ-variation and the functions h _n . In Theorem 2, the same is done for a sequence of functions h _n : ? → ?, n = 1, 2, ..., and the sequence of Ψ-variations {V _Ψ(〈a, b〉; h _n ? f)} _n=1 ^∞ .     

On the expansion with respect to Steklov means of the second differences of functions

We shall prove that every function locally integrable in then-dimensional Euclidean spaceR ⁿ can be expanded into a series whose terms are the Steklov means of the second differences of the given function. In addition, the lengths of the edges of the cubes with respect to which averaging is taken form an infinite decreasing geometric progression. The series obtained in this way converge almost everywhere inR ⁿ . If the function expanded belongs to the Lebesgue spaceL _p on a compact set ofR ⁿ for some 1≤p<∞, then the expansion converges also in the norm of this space.     

On matrix measures and convex Liapunov functions

In this paper, we extend the concept of the measure of a matrix to encompass a measure induced by an arbitrary convex positive definite function. It is shown that this “modified” matrix measure has most of the properties of the usual matrix measure, and that many of the known applications of the usual matrix measure can therefore be carried over to the modified matrix measure. These applications include deriving conditions for a mapping to be a diffeomorphism on Rⁿ, and estimating the solution errors that result when a nonlinear network is approximated by a piecewise linear network. We also develop a connection between matrix measures and Liapunov functions. Specifically, we show that if V is a convex positive definite function and A is a Hurwitz matrix, then μ_V(A) < 0, if and only if V is a Liapunov function for the system $\text{x}\text{?}\text{= Ax}$. This linking up between matrix measures and Liapunov functions leads to some results on the existence of a “common” matrix measure μ_V(·) such that μ_V(A_i) < 0 for each of a given set of matrices A₁,…, A_m. Finally, we also give some results for matrices with nonnegative off-diagonal terms.     

Schrödinger operators on manifolds, essential self-adjointness, and absence of eigenvalues

Suppose thatM ⁿ is a complete, noncompact, Riemannian manifold. If Δ denotes the Laplace operator ofM, one has associated Schrödinger operators ? Δ +V. Conditions onV are formulated, which ensures the essential self-adjointness of ? Δ +V. In particular, ifV ∈ Q_α,loc (M ⁿ), the local Stummel class, andV ≥ ? c outside of a compact set, then ? Δ +V is essentially self-adjoint on C ₀ ^∞ (M ⁿ). In addition, essential self-adjointness is proved for potentials which are strongly singular at a point. The absence of eigenvalues of ?Δ +V is also studied. This relies upon Rellich-type identities. The results on strongly singular potentials make use of a generalization of the classical uncertainty principle, inR ⁿ, to Riemannian manifolds with a pole.     

On pointwise approximation of arbitrary functions by countable families of continuous functions

The following problem is considered. Given a real-valued function f defined on a topological space X, when can one find a countable familyf _n :n∈ω of continuous real-valued functions on X that approximates f on finite subsets of X? That is, for any finite set F?X and every real number ε>0 one can choosen∈ω such that ∥f(x)?f_n(x)∥<ε for everyx∈F. It will be shown that the problem has a positive solution if and only if X splits. A space X is said to split if, for any A?X, there exists a continuous mapf _A:X→R ^ω such that A=f _A ^?1 (A). Splitting spaces will be studied systematically.     

Partitions of the set of natural numbers and their representation functions

For a given set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. In this paper we give a simple proof to two results by Sándor.     

Localization in fine potential theory and uniform approximation by subharmonic functions

It is shown how the cone $\text{l}$(U) of superharmonic functions ?0 on an open set U in $\text{R}$ⁿ, n ? 3, can be recovered from the cone $\text{l}$ of superharmonic functions ?0 on the whole of $\text{R}$ⁿ by a process involving the operator of localization associated with U. Actually we treat the more general case where U is open in the Cartan-Brelot fine topology on $\text{R}$ⁿ. As an application we obtain a new proof of a theorem of J. Bliedtner and W. Hansen on uniform approximation by continuous subharmonic functions in open sets containing a given compact set K in $\text{R}$ⁿ.     

Hermitian decomposition of continuous functions on a fractal surface

In this paper the Théodoresco transform is used to show that, under additional assumptions, each Hölder continuous function f defined on the boundary Γ of a fractal domain Ω ? ?²ⁿ can be expressed as f = Ψ⁺ ? Ψ^?, where Ψ^± are Hölder continuous functions on Γ and Hermitian monogenically extendable to Ω and to ?²ⁿ ? (Ω ∪ Γ) respectively.     

Multiobjective programming and penalty functions

This paper generalizes the penalty function method of Zang-will for scalar problems to vector problems. The vector penalty function takes the form $$g(x,\lambda ) = f(x) + \lambda ^{ - 1} P(x)e,$$ wheree ?R ^m, with each component equal to unity;f:R ⁿ →R ^m, represents them objective functions {f ⁱ} defined onX \( \subseteq \) R ⁿ; λ ∈R ¹, λ>0;P:R ⁿ →R ¹ X \( \subseteq \) Z \( \subseteq \) R ⁿ,P(x)≦0, ∨x ∈R ⁿ,P(x) = 0 ?x ∈X. The paper studies properties of {E (Z, λ _r )} for a sequence of positive {λ _r } converging to 0 in relationship toE(X), whereE(Z, λ _r ) is the efficient set ofZ with respect tog(·, λ_r) andE(X) is the efficient set ofX with respect tof. It is seen that some of Zangwill's results do not hold for the vector problem. In addition, some new results are given.     

The lower order of functions of the classB

The class of functions Φ(z, t) defined for z∈ Cⁿ and t ≥0 such that the functions Φ(z, ¦w¦), w∈C, are plurisubharmonic in Cⁿ⁺¹ is called the classD. A typical example of functions of the classB are functions of the form \(\ln M_g (z,t) = \mathop {\ln \sup |}\limits_{|w| = t} g(z,w)|\) where g(z, w), z∈Cⁿ, w∈C, is an entire function in Cⁿ⁺¹. In this note it is proved under certain restrictions on the function Φ(z, t)εB that its lower order relative to the variable t is the same for all z∈Cⁿ except, possibly, for the points z of a set of zero Γ capacity. See [5].     

Estimates for harmonic conjugate functions and Riesz-system

In this paper we generalize a theorem of Hardy and Littlewood concerning the growth of conjugate harmonic functions. Moreover, we obtain an estimate for Riesz systems in the upper half-space R ₊ ⁿ⁺¹ of R ⁿ⁺¹.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

Riemann boundary value problems for some K-regular functions in clifford analysis

In this paper, we study the R_m (m > 0) Riemann boundary value problems for regular functions, harmonic functions and bi-harmonic functions with values in a universal clifford algebra C(V_n,n). By using Plemelj formula, we get the solutions of R_m (m > 0) Riemann boundary value problems for regular functions. Then transforming the Riemann boundary value problems for harmonic functions and bi-harmonic functions into the Riemann boundary value problems for regular functions, we obtain the solutions of R_m (m > 0) Riemann boundary value problems for harmonic functions and bi-harmonic functions.     

Isotone functions,dual cones,and networks

If the collection of all real-valued functions defined on a finite partially ordered set S of n elements is identified in the natural way with Rⁿ, it is obvious that the subset of functions that are isotone or order preserving with respect to the given partial order constitutes a closed, convex, polyhedral cone K in Rⁿ. The dual cone K^* of K is the set of all linear functionals that are nonpositive of K. This article identifies the important geometric properties of K, and characterizes a nonredundant set of defining equations and inequalities for K^* in terms of a special class of partitions of S into upper and lower sets. These defining constraints immediately imply a set of extreme rays spanning K and K^*. One of the characterizations of K^* involves feasibility conditions on flows in a network. These conditions are also used as a tool in analysis.     

The sharp quantitative Sobolev inequality for functions of bounded variation

The classical Sobolev embedding theorem of the space of functions of bounded variation BV(Rn) into Ln^′(Rn) is proved in a sharp quantitative form.     

Linear combinations of frame generators in systems of translates

A finitely generated shift invariant space V   is a closed subspace of L²(R^d)$L^2({\mathbb{R}}^d)$ that can be generated by the integer translates of a finite number of functions. A set of frame generators for V is a set of functions whose integer translates form a frame for V. In this note we give necessary and sufficient conditions in order that a minimal set of frame generators can be obtained by taking linear combinations of the given frame generators. Surprisingly the results are very different from the recently studied case when the property to be a frame is not required.     

On unconditional basis property in the space <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript>(<Emphasis Type="Italic">R</Emphasis>) of a system of Franklin functions with vanishing means

We define a general Franklin system of functions on R with vanishing means, generated by an admissible sequence T. A necessary and sufficient condition on T is found for the corresponding general Franklin system of functions on R with vanishing means to be an unconditional basis in the space H ¹(R).     

Convergence parameter associated with a Markov chain and a family of functions

The proposed definition of convergence parameter R(W) corresponding to a Markov chain X with a measurable state space (E,?) and any nonempty setW of bounded below measurable functions f: E → ? is wider than the well-known definition of convergence parameter R in the sense of Tweedie or Nummelin. Very often, R(W) < ∞, and there exists a set playing the role of the absorbing set inNummelin’s definition ofR. Special attention is paid to the case in whichE is locally compact, X is a Feller chain on E, and W coincides with the family ? ₀ ⁺ of all compactly supported continuous functions f ≥ 0 (f ? 0). In particular, certain conditions for R(? ₀ ⁺ )^?1 to coincide with the norm of an appropriate modification of the chain transition operator are found.