共查询到20条相似文献,搜索用时 105 毫秒
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 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.
Question/Answer games (Q/A games for short) are a generalization of the Rényi–Ulam game and they are a model for information extraction in parallel. A Q/A game, G=(D,s,(q1,…,qk)), is played on a directed acyclic graph, D=(V,E), with a distinguished start vertex s. In the ith round, Paul selects a set, Qi⊆V, of at most qi non-terminal vertices. Carole responds by choosing an outgoing edge from each vertex in Qi. At the end of k rounds, Paul wins if Carole’s answers define a unique path from the root to one of the terminal vertices in D. 相似文献
5.
6.
7.
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. 相似文献
8.
9.
10.
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. 相似文献
11.
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. 相似文献
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.
16.
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. 相似文献
17.
18.
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. 相似文献
19.
We study four problems from the geometry of numbers, the shortest vector problem (Svp), the closest vector problem (Cvp), the successive minima problem (Smp), and the shortest independent vectors problem (Sivp). Extending and generalizing results of Ajtai, Kumar, and Sivakumar we present probabilistic single exponential time algorithms for all four problems for all ?p norms. The results on Smp and Sivp are new for all norms. The results on Svp and Cvp generalize previous results of Ajtai et al. for the Euclidean ?2 norm to arbitrary ?p norms. We achieve our results by introducing a new lattice problem, the generalized shortest vector problem (GSvp). 1 We describe a single exponential time algorithm for GSvp. We also describe polynomial time reductions from Svp,Cvp,Smp, and Sivp to GSvp, establishing single exponential time algorithms for the four classical lattice problems. This approach leads to a unified algorithmic treatment of the lattice problems Svp,Cvp,Smp, and Sivp. 相似文献
20.
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. 相似文献