共查询到20条相似文献,搜索用时 15 毫秒
2.
Let F(x,y) be a polynomial over a field K and m a nonnegative integer. We call a polynomial g over K an m-near solution of F(x,y) if there exists a c∈K such that F(x,g)=cxm, and the number c is called an m-value of F(x,y) corresponding to g. In particular, c can be 0. Hence, by viewing F(x,y)=0 as a polynomial equation over K[x] with variable y, every solution of the equation F(x,y)=0 in K[x] is also an m-near solution. We provide an algorithm that gives all m-near solutions of a given polynomial F(x,y) over K, and this algorithm is polynomial time reducible to solving one variable equations over K. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions. 相似文献
3.
4.
5.
The software package Qcompiler (Chen and Wang 2013) provides a general quantum compilation framework, which maps any given unitary operation into a quantum circuit consisting of a sequential set of elementary quantum gates. In this paper, we present an extended software OptQC , which finds permutation matrices P and Q for a given unitary matrix U such that the number of gates in the quantum circuit of U=QTPTU′PQ is significantly reduced, where U′ is equivalent to U up to a permutation and the quantum circuit implementation of each matrix component is considered separately. We extend further this software package to make use of high-performance computers with a multiprocessor architecture using MPI. We demonstrate its effectiveness in reducing the total number of quantum gates required for various unitary operators. 相似文献
6.
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. 相似文献
7.
8.
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. 相似文献
9.
10.
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn) memory for a list of size n, the i’th back-step from the farthest point reached so far takes O(lgi) time in the worst case, while the overhead per forward step is at most ? for arbitrary small constant ?>0. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k vs. kn1/k and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n1/k-ary, tree that can only be traversed in a pre-order fashion. 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
14.
We study the state complexity of certain simple languages. If A is an alphabet of k letters, then a k-language is a nonempty set of words of length k, that is, a uniform language of length k. We show that the minimal state complexity of a k-language is k+2, and the maximal, (kk−1−1)/(k−1)+2k+1. We prove constructively that, for every i between the minimal and maximal bounds, there is a language of state complexity i. We introduce a class of automata accepting sets of words that are permutations of A; these languages define a complete hierarchy of complexities between k2−k+3 and 2k+1. The languages of another class of automata, based on k-ary trees, define a complete hierarchy of complexities between 2k+1 and (kk−1−1)/(k−1)+2k+1. This provides new examples of uniform languages of maximal complexity. 相似文献
15.
Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial nO(k) time brute force algorithm for finding a k-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅nO(1)) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?, then we can determine in randomized time f(k,?)⋅nO(1) whether there is an independent set that is the union of k blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k-element set in the intersection of ? matroids, or finding k terminals in a network such that each of them can be connected simultaneously to the source by ? disjoint paths. 相似文献
16.
We define a self-map Pal:F2→F2 of the free group on two generators a,b, using automorphisms of F2 that form a group isomorphic to the braid group B3. The map Pal restricts to de Luca’s right iterated palindromic closure on the submonoid generated by a,b. We show that Pal is continuous for the profinite topology on F2; it is the unique continuous extension of de Luca’s right iterated palindromic closure to F2. The values of Pal are palindromes and coincide with the elements g∈F2 such that abg and bag are conjugate. 相似文献
17.
18.
We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set S⊂Rk defined by a weak sign condition involving s polynomials in Z[X1,…,Xk] having degrees at most d, and whose coefficients have bitsizes at most τ. Our bound is an explicit function of s,d,k and τ, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of S (including the unbounded components). While asymptotic bounds of the form 2τdO(k) on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s,d,k and τ. The bounds proved in this paper are of this nature. 相似文献
19.
The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database D, a conjunctive query Q, and a tuple a, tests whether Q(a) holds in D in time bounded by a polynomial in (sn)logk(sn)loglogn and nr, where n is the size of the domain of the database, k is the number of bound variables of the conjunctive query, s is the size of the optimal search-tree, and r is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the nO(k) bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks. 相似文献
20.
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. 相似文献