首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean functionf, by using membership queries only, where min T(f) (max F(f)) denotes the set of minimal true vectors (maximum false vectors) off. Moreover, as the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive functionfofnvariables, decide whetherfis 2-monotonic or not, and iffis 2-monotonic, output both min T(f) and max F(f). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and we show that it usesO(n2m) time andO(n2m) queries, wherem = |min T(f)| + |max F(f)|. This answers affirmatively the conjecture raised in Boroset al.[Lecture Notes in Comput. Sci.557(1991), 104–115], Boroset al.[SIAM J. Comput.26(1997), 93–109], and is an improvement over the two algorithms discussed therein: one usesO(n3m) time andO(n3m) queries, and the other usesO(nm2 + n2m) time andO(nm) queries.  相似文献   

2.
Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)r = λ(n)s, where rs ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.  相似文献   

3.
Let fL w 1 [−1, 1], let r n,m(f) be the best rational L w 1 -approximation for f with respect to real rational functions of degree at most n in the numerator and of degree at most m in the denominator, let m = m(n), and let lim n → ∞ (n-m(n)) = ∞. In this case, we show that the counting measures of certain subsets of sign changes of f-r n,m (f) converge weakly to the equilibrium measure on [−1, 1] as n → ∞. Moreover, we prove estimates for discrepancy between these counting measures and the equilibrium measure. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 2, pp. 283–287, February, 2006.  相似文献   

4.
In this paper, we develop two algorithms for finding a directed path of minimum rank-two monotonic cost between two specified nodes in a network with n nodes and m arcs. Under the condition that one of the vectors characterizing the cost function f is binary, one yields an optimal solution in O(n3) or O(nm log n) time if f is quasiconcave; the other solves any problem in O(nm + n 2 log n) time.  相似文献   

5.
For fC[−1, 1], let Hmn(fx) denote the (0, 1, …,anbsp;m) Hermite–Fejér (HF) interpolation polynomial of f based on the Chebyshev nodes. That is, Hmn(fx) is the polynomial of least degree which interpolates f(x) and has its first m derivatives vanish at each of the zeros of the nth Chebyshev polynomial of the first kind. In this paper a precise pointwise estimate for the approximation error |H2mn(fx)−f(x)| is developed, and an equiconvergence result for Lagrange and (0, 1, …, 2m) HF interpolation on the Chebyshev nodes is obtained. This equiconvergence result is then used to show that a rational interpolatory process, obtained by combining the divergent Lagrange and (0, 1, …, 2m) HF interpolation methods on the Chebyshev nodes, is convergent for all fC[−1, 1].  相似文献   

6.
It is known that the Bernstein polynomials of a function f defined on [0, 1 ] preserve its convexity properties, i.e., if f(n) 0 then for m n, (Bmf)(n) 0. Moreover, if f is n-convex then (Bmf)(n) 0. While the converse is not true, we show that if f is bounded on (a, b) and if for every subinterval [α, β] (a, b) the nth derivative of the mth Bernstein polynomial of f on [α, β] is nonnegative then f is n-convex.  相似文献   

7.
For every a > 1, there is a function f : N20 → R, which is positive semidefinite but not a moment sequence, such that |f(m, n)| ≥ m+ na(m+n) for all (m, n). The constant 1 is the best possible.  相似文献   

8.
Let c n be the Fourier coefficients of L(sym m f, s), and Δρ(x; sym m f) be the error term in the asymptotic formula for ∑ nx c n . In this paper, we study the Riesz means of Δρ(x; sym m f) and obtain a truncated Voronoi-type formula under the hypothesis Nice(m, f).  相似文献   

9.
Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k - 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n2/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).  相似文献   

10.
A Hamiltonian graph G of order n is k-ordered, 2 ≤ kn, if for every sequence v1, v2, …, vk of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v1, v2, …, vk in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2kn ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999  相似文献   

11.
The paper deals with the approximation of bounded real functions f on a compact metric space (X, d) by so-called controllable step functions in continuation of [Ri/Ste]. These step functions are connected with controllable coverings, that are finite coverings of compact metric spaces by subsets whose sizes fulfil a uniformity condition depending on the entropy numbers εn(X) of the space X. We show that a strong form of local finiteness holds for these coverings on compact metric subspaces of IRm and Sm. This leads to a Bernstein type theorem if the space is of finite convex information. In this case the corresponding approximation numbers εn(f) have the same asymptotics its ω(f, εn(X)) for f ε C(X). Finally, the results concerning functions f ε M(X) and f ε C(X) are transferred to operators with values in M(X) and C(X), respectively.  相似文献   

12.
Let ν(n) denote the number of distinct prime factors of n. We show that the equation n + ν(n) = m + ν(m) has many solutions with nm. We also show that if ν is replaced by an arbitrary, integer-valued function f with certain properties assumed about its average order, then the equation n + f(n) = m + f(m) has infinitely many solutions with nm.  相似文献   

13.
Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f.  相似文献   

14.
A graph is called H-free if it contains no copy of H. Denote by f n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f n (H) ≤ 2(1+o(1))ex(n,H). This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log2 f n (H) is not known. We prove that f n (K m,m ) ≤ 2 O (n 2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K m,m ) is conjectured to be Θ(n 2−1/m ). Our method also yields a bound on the number of K m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K 3,3-free graphs of order n have more than 1/20·ex(n,K 3,3) edges.  相似文献   

15.
In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f(u) of the real line so that f(u) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f(u) and f(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph Km, n has interval number ?(mn + 1)/(m + n)?.  相似文献   

16.
We investigate the growth and the distribution of zeros of rational uniform approximations with numerator degree ≤n and denominator degree ≤m n for meromorphic functions f on a compact set E of ℂ where m n =o(n/log n) as n→∞. We obtain a Jentzsch–Szegő type result, i.e., the zero distribution converges weakly to the equilibrium distribution of the maximal Green domain E ρ(f) of meromorphy of f if f has a singularity of multivalued character on the boundary of E ρ(f). The paper extends results for polynomial approximation and rational approximation with fixed degree of the denominator. As applications, Padé approximation and real rational best approximants are considered.  相似文献   

17.
Let F be a distribution and let f be a locally summable function. The distribution F(f) is defined as the neutrix limit of the sequence {F n (f)}, where F n (x) = F(x) * δ n (x) and {δ n (x)} is a certain sequence of infinitely differentiable functions converging to the Dirac delta-function δ(x). The composition of the distributions x ?s ln m |x| and x r is proved to exist and be equal to r m x ?rs ln m |x| for r, s, m = 2, 3….  相似文献   

18.
Let Sm denote the m-vertex simple digraph formed by m − 1 edges with a common tail. Let f(m) denote the minimum n such that every n-vertex tournament has a spanning subgraph consisting of n/m disjoint copies of Sm. We prove that m lg mm lg lg mf(m) ≤ 4m2 − 6m for sufficiently large m. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 141–145, 1998  相似文献   

19.
A sequence (f n ) n of functions f n : X → ℝ almost decreases (increases) to a function f: X → ℝ if it pointwise converges to f and for each point xX there is a positive integer n(x) such that f n+1(x) ≤ f n (x) (f n+1(x) ≥ f n (x)) for nn(x). In this article I investigate this convergence in some families of continuous functions.  相似文献   

20.
It is proved that if the differential equations y ( n )=f(x, y, y′, …, y ( n ?1 )) and y ( m )=g(x, y, y′, …, y ( n ?1 )) have the same particular solutions in a suitable region where f and g are continuous real-valued functions with continuous partial derivatives (alternatively, continuous functions satisfying the classical Lipschitz condition), then n?=?m and the functions f and g are equal. This note could find classroom use in a course on differential equations as enrichment material for the unit on the existence and uniqueness theorems for solutions of initial value problems.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号