共查询到20条相似文献,搜索用时 15 毫秒
1.
We prove that a polynomial f∈R[x,y] with t non-zero terms, restricted to a real line y=ax+b, either has at most 6t−4 zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y−ax−b∈K[x,y] divides a lacunary polynomial f∈K[x,y], where K is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f, in the logarithm of the degree of f, in the degree of the extension K/Q and in the logarithmic height of a, b and f. 相似文献
2.
The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f and g, with domain sizes N and M(N≤M), respectively, and the same range, the goal of the problem is to find x and y such that f(x)=g(y). This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k functions for any constant integer k>1, where the domain sizes of the functions may be different. 相似文献
3.
A real x is called h-bounded computable , for some function h:N→N, if there is a computable sequence (xs) of rational numbers which converges to x such that, for any n∈N, at most h(n) non-overlapping pairs of its members are separated by a distance larger than 2-n. In this paper we discuss properties of h-bounded computable reals for various functions h. We will show a simple sufficient condition for a class of functions h such that the corresponding h-bounded computable reals form an algebraic field. A hierarchy theorem for h-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h-bounded computability for special functions h. 相似文献
4.
We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element that is near a recently accessed element. More precisely, if w(y) distinct elements have been accessed since the last access to element y, and d(x,y) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is O(minylog[w(y)+d(x,y)+2]). This property generalizes the working-set and dynamic-finger properties of splay trees. 相似文献
5.
6.
7.
Andrej Muchnik Alexander Shen Mikhail Ustinov Nikolai Vereshchagin Michael Vyugin 《Theoretical computer science》2007
Assume that a program p on input a outputs b. We are looking for a shorter program q having the same property (q(a)=b). In addition, we want q to be simple conditional to p (this means that the conditional Kolmogorov complexity K(q|p) is negligible). In the present paper, we prove that sometimes there is no such program q, even in the case when the complexity of p is much bigger than K(b|a). We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively. 相似文献
8.
9.
Motivated by the famous 3n+1 conjecture, we call a mapping from Z to Zresidue-class-wise affine if there is a positive integer m such that it is affine on residue classes (mod m). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings. 相似文献
10.
11.
Let D=K[X] be a ring of Ore polynomials over a field K and let a partition of the set of indeterminates into p disjoint subsets be fixed. Considering D as a filtered ring with the natural p-dimensional filtration, we introduce a special type of reduction in a free D-module and develop the corresponding Gröbner basis technique (in particular, we obtain a generalization of the Buchberger Algorithm). Using such a modification of the Gröbner basis method, we prove the existence of a Hilbert-type dimension polynomial in p variables associated with a finitely generated filtered D-module, give a method of computation and describe invariants of such a polynomial. The results obtained are applied in differential algebra where the classical theorems on differential dimension polynomials are generalized to the case of differential structures with several basic sets of derivation operators. 相似文献
12.
We consider a two-edge connected, undirected graph G=(V,E), with n nodes and m non-negatively real weighted edges, and a single source shortest paths tree (SPT) T of G rooted at an arbitrary node r. If an edge in T is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog2n) time and O(m) space algorithm to find a best swap edge for every edge of T, thus improving for m=o(n2/log2n) the previously known O(n2) time and space complexity algorithm. 相似文献
13.
14.
A. Abouelaoualim K.Ch. Das L. Faria Y. Manoussakis C. Martinhon R. Saad 《Theoretical computer science》2008
This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s and t in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s and t for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k pairwise vertex/edge disjoint properly edge-colored s−t paths/trails in a c-edge-colored graph Gc is NP-complete even for k=2 and c=Ω(n2), where n denotes the number of vertices in Gc. Moreover, we prove that these problems remain NP-complete for c-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n). We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs. 相似文献
15.
16.
Some time ago, Shpilrain and Yu reported an algorithm for deciding whether or not a polynomial p∈K[x,y] is a coordinate, or, equivalently, whether or not a plane curve p(x,y)=0 is isomorphic to a line. Here K is any constructible field of characteristic 0. In this paper, we show that their algorithm requires O(n2) field operations, where n is the degree of a given polynomial. We also show how their algorithm can be used to find a polynomial parametrization of a plane curve p(x,y)=0 which is isomorphic to a line. This requires O(n2log2n) field operations. 相似文献
17.
We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O,?), where O is the set of abstract origamis and ? is a binary relation on O, that models fold . An abstract origami is a structure (Π,∽,?), where Π is a set of faces constituting an origami, and ∽ and ? are binary relations on Π, each representing adjacency and superposition relations between the faces. 相似文献
18.
This paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most δ, i.e., the tree-length δ graphs. For such graphs we construct additive 2δ-spanners with O(δn+nlogn) edges, and additive 4δ-spanners with O(δn) edges. This provides new upper bounds for chordal graphs for which δ=1. We also show a lower bound, and prove that there are graphs of tree-length δ for which every multiplicative δ-spanner (and thus every additive (δ−1)-spanner) requires Ω(n1+1/Θ(δ)) edges. 相似文献
19.
The most effective way to maximize the lifetime of a wireless sensor network (WSN) is to allocate initial energy to sensors such that they exhaust their energy at the same time. The lifetime of a WSN as well as an optimal initial energy allocation are determined by a network design. The main contribution of the paper is to show that the lifetime of a WSN can be maximized by an optimal network design. We represent the network lifetime as a function of the number m of annuli and show that m has significant impact on network lifetime. We prove that if the energy consumed by data transmission is proportional to dα+c, where d is the distance of data transmission and α and c are some constants, then for a circular area of interest with radius R, the optimal number of annuli that maximizes the network lifetime is m=R((α−1)/c)1/α for an arbitrary sensor density function. 相似文献
20.
We consider the problem of solving a linear system Ax=b over a cyclotomic field. Cyclotomic fields are special in that we can easily find a prime p for which the minimal polynomial m(z) for the field factors into a product of distinct linear factors. This makes it possible to develop fast modular algorithms. 相似文献