共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
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. 相似文献
3.
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. 相似文献
4.
5.
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. 相似文献
6.
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. 相似文献
7.
Taisuke Izumi Akinori Saitoh Toshimitsu Masuzawa 《Journal of Parallel and Distributed Computing》2007
The Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ (Δ-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ-timed uniform consensus problem in presence of fc crash processes and ft timing-faulty processes, and propose a Δ-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ-timed uniform consensus when at least ft+1 correct processes exist in the system. If the system has less than ft+1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as ft+1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes requires that the system has at least ft+1 correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than ft+1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. 相似文献
8.
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. 相似文献
9.
We develop a new lower bound technique for data structures. We show an optimal Ω(nlglgn/lgn) space lower bounds for storing an index that allows to implement rank and select queries on a bit vector B provided that B is stored explicitly. These results improve upon [Peter Bro Miltersen, Lower bounds on the size of selection and rank indexes, in: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, 2005, pp. 11–12]. We show Ω((m/t)lgt) lower bounds for storing rank/select index in the case where B has m 1-bits in it and the algorithm is allowed to probe t bits of B. We also present an improved data structure that implements both rank and select queries with an index of size (1+o(1))(nlglgn/lgn)+O(n/lgn), that is, compared to existing results we give an explicit constant for storage in the RAM model with word size lgn. An advantage of this data structure is that both rank and select indexes share the most space consuming part of order Θ(nlglgn/lgn) making it more practical for implementation. 相似文献
10.
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. 相似文献
11.
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. 相似文献
12.
We aim at finding the best possible seed values when computing a1/p using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a) in the interval [amin,amax], by building the sequence xn defined by the Newton–Raphson iteration, the natural choice consists in choosing x0 equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between x0 and f(a). And yet, if we perform n iterations, what matters is to minimize the maximum possible distance between xn and f(a). In several examples, the value of the best starting point varies rather significantly with the number of iterations. 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
The augmented weighted Tchebycheff norm was introduced in the context of multicriteria optimization by Steuer and Choo [21] in order to avoid the generation of weakly nondominated points. It augments a weighted l∞-norm with an l1-term, multiplied by a “small” parameter ρ>0. However, the appropriate selection of the parameter ρ remained an open question: A too small value of ρ may cause numerical difficulties, while a too large value of ρ may lead to the oversight of some nondominated points. 相似文献
16.
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. 相似文献
17.
Alix L.H. Chow Leana Golubchik Samir Khuller Yuan Yao 《Journal of Parallel and Distributed Computing》2012
We consider the following basic question: a source node wishes to stream an ordered sequence of packets to a collection of receivers, which are in K clusters. A node may send a packet to another node in its own cluster in one time step and to a node in a different cluster in Tc time steps (Tc>1). Each cluster has two special nodes. We assume that the source and the special nodes in each cluster have a higher capacity and thus can send multiple packets at each step, while all other nodes can both send and receive a packet at each step. We construct two (intra-cluster) data communication schemes, one based on multi-trees (using a collection of d-ary interior-disjoint trees) and the other based on hypercubes. The multi-tree scheme sustains streaming within a cluster with O(dlogN) maximum playback delay and O(dlogN) size buffers, while communicating with O(d) neighbors, where N is the maximum size of any cluster. We also show that this protocol is optimal when d=2 or 3. The hypercube scheme sustains streaming within a cluster, with O(log2(N)) maximum playback delay and O(1) size buffers, while communicating with O(log(N)) neighbors, for arbitrary N. In addition, we extend our multi-tree scheme to work when receivers depart and arrive over time. We also evaluate our dynamic schemes using simulations. 相似文献
18.
19.
Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has a demand d(v)∈Z+ and a cost c(v)∈R+, where Z+ and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G requires finding a set S of vertices minimizing ∑v∈Sc(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v∈V−S. It is known that if there exists a vertex v∈V with d(v)≥4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|4log2|V|) time if d(v)≤3 holds for each vertex v∈V. 相似文献