共查询到20条相似文献,搜索用时 437 毫秒
1.
2.
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. 相似文献
3.
4.
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. 相似文献
5.
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. 相似文献
6.
We investigate a periodic version of the Benjamin-Ono (BO) equation associated with a discrete Laplacian. We find some special solutions to this equation, and calculate the values of the first two integrals of motion I1 and I2 corresponding to these solutions. It is found that there exists a strong resemblance between them and the spectra for the Macdonald q-difference operators. To better understand the connection between these classical and quantum integrable systems, we consider the special degenerate case corresponding to q=0 in more detail. Namely, we give general solutions to this degenerate periodic BO, obtain explicit formulas representing all the integrals of motions In (n=1,2,…), and successfully identify it with the eigenvalues of Macdonald operators in the limit q→0, i.e. the limit where Macdonald polynomials tend to the Hall–Littlewood polynomials. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
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. 相似文献
10.
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. 相似文献
11.
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. 相似文献
12.
The replication number of a branching program is the minimum number R such that along every accepting computation at most R variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0 (read-once programs) and the total number n of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn). We improve this to R≤?n for a constant ?>0. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n time branching programs for a constant ?>0. We prove these lower bounds for quadratic functions of Ramanujan graphs. 相似文献
13.
14.
We present algorithmic lower bounds on the size sd of the largest independent sets of vertices in random d-regular graphs, for each fixed d≥3. For instance, for d=3 we prove that, for graphs on n vertices, sd≥0.43475n with probability approaching one as n tends to infinity. 相似文献
15.
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. 相似文献
16.
17.
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. 相似文献
18.
This work is concerned with simulating nondeterministic one-reversal multicounter automata (NCMs) by nondeterministic partially blind multihead finite automata (NFAs). We show that any one-reversal NCM with k counters can be simulated by a partially blind NFA with k blind heads. This provides a nearly complete categorization of the computational power of partially blind automata, showing that the power of a (k+1)-NFA lies between that of a k-NCM and a (k+1)-NCM. 相似文献
19.
20.
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. 相似文献