首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
We reconsider some classical natural semantics of integers (namely iterators of functions, cardinals of sets, index of equivalence relations) in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self‐enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations (cf. [6]). This contrasts with the well‐known fact that usual Kolmogorov complexity does not depend (up to a constant) on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)  相似文献   

3.
In this paper, two direct algorithms for solving the two‐sided obstacle problem with an M‐matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd.  相似文献   

4.
A direct algorithm for the solution to the affine two‐sided obstacle problem with an M‐matrix is presented. The algorithm has the polynomial bounded computational complexity O(n3) and is more efficient than those in (Numer. Linear Algebra Appl. 2006; 13 :543–551). Copyright © 2010 John Wiley & Sons, Ltd.  相似文献   

5.
6.
A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal’tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 655–686, November–December, 2006.  相似文献   

7.
It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.  相似文献   

8.
Arman Darbinyan 《代数通讯》2013,41(11):4923-4935
We show that every countable group H with solvable word problem can be subnormally embedded into a 2-generated group G which also has solvable word problem. Moreover, the membership problem for H < G is also solvable. We also give estimates of time and space complexity of the word problem in G and of the membership problem for H < G.  相似文献   

9.
The word problem for discrete groups is well known to be undecidable by a Turing Machine; more precisely, it is reducible both to and from and thus equivalent to the discrete Halting Problem. The present work introduces and studies a real extension of the word problem for a certain class of groups which are presented as quotient groups of a free group and a normal subgroup. As a main difference to discrete groups these groups may be generated by uncountably many generators with index running over certain sets of real numbers. We study the word problem for such groups within the Blum–Shub–Smale (BSS) model of real number computation. The main result establishes the word problem to be computationally equivalent to the Halting Problem for such machines. It thus gives the first non-trivial example of a problem complete, that is, computationally universal for this model. M. Ziegler supported by (project Zi1009/1-2).  相似文献   

10.
11.
LetF be a free group with at most countable system of free generators, letR be its normal subgroup recursively enumerable with respect to , and let be a variety of groups that differs from and for which the corresponding verbal subgroupV of the free group of countable rank is recursive. It is proved that the word problem inF/V(R) is solvable if and only if this problem is solvable inF/R, and if , then there exists anR such, that the conjugacy problem inF/R is solvable, but this problem is unsolvable inF/V(R) for any Abelian variety (all algorithmic problems are regarded with respect to the images of under the corresponding natural epimorphisms). Translated fromMatematicheskie Zametki, Vol. 61, No. 1, pp. 3–9, January, 1997. Translated by M. I. Anokhin  相似文献   

12.
We continue the study of generalized tractability initiated in our previous paper “Generalized tractability for multivariate problems, Part I: Linear tensor product problems and linear information”, J. Complex. 23:262–295, 2007. We study linear tensor product problems for which we can compute linear information which is given by arbitrary continuous linear functionals. We want to approximate an operator S d given as the d-fold tensor product of a compact linear operator S 1 for d=1,2,…, with ‖S 1‖=1 and S 1 having at least two positive singular values. Let n(ε,S d ) be the minimal number of information evaluations needed to approximate S d to within ε∈[0,1]. We study generalized tractability by verifying when n(ε,S d ) can be bounded by a multiple of a power of T(ε −1,d) for all (ε −1,d)∈Ω⊆[1,∞)×ℕ. Here, T is a tractability function which is non-decreasing in both variables and grows slower than exponentially to infinity. We study the exponent of tractability which is the smallest power of T(ε −1,d) whose multiple bounds n(ε,S d ). We also study weak tractability, i.e., when . In our previous paper, we studied generalized tractability for proper subsets Ω of [1,∞)×ℕ, whereas in this paper we take the unrestricted domain Ω unr=[1,∞)×ℕ. We consider the three cases for which we have only finitely many positive singular values of S 1, or they decay exponentially or polynomially fast. Weak tractability holds for these three cases, and for all linear tensor product problems for which the singular values of S 1 decay slightly faster than logarithmically. We provide necessary and sufficient conditions on the function T such that generalized tractability holds. These conditions are obtained in terms of the singular values of S 1 and mostly asymptotic properties of T. The tractability conditions tell us how fast T must go to infinity. It is known that T must go to infinity faster than polynomially. We show that generalized tractability is obtained for T(x,y)=x 1+ln y . We also study tractability functions T of product form, T(x,y)=f 1(x)f 2(x). Assume that a i =lim inf  x→∞(ln ln f i (x))/(ln ln x) is finite for i=1,2. Then generalized tractability takes place iff
and if (a 1−1)(a 2−1)=1 then we need to assume one more condition given in the paper. If (a 1−1)(a 2−1)>1 then the exponent of tractability is zero, and if (a 1−1)(a 2−1)=1 then the exponent of tractability is finite. It is interesting to add that for T being of the product form, the tractability conditions as well as the exponent of tractability depend only on the second singular eigenvalue of S 1 and they do not depend on the rate of their decay. Finally, we compare the results obtained in this paper for the unrestricted domain Ω unr with the results from our previous paper obtained for the restricted domain Ω res=[1,∞)×{1,2,…,d *}∪[1,ε 0−1)×ℕ with d *≥1 and ε 0∈(0,1). In general, the tractability results are quite different. We may have generalized tractability for the restricted domain and no generalized tractability for the unrestricted domain which is the case, for instance, for polynomial tractability T(x,y)=xy. We may also have generalized tractability for both domains with different or with the same exponents of tractability.   相似文献   

13.
Every 3‐connected planar, cubic, triangle‐free graph with n vertices has a bipartite subgraph with at least 29n/24 ? 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Examples show that the constant 29/24 = 1.2083… cannot be raised to more than 47/38 = 1.2368…. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 261–269, 2006  相似文献   

14.
《Optimization》2012,61(4):597-611
A single server, limited capacity queueing system with Poisson arrivals and exponential service is studied. The joint probability distribution of the number of times the system reaches its capacity in time interval (0t] and the number of customers in the system at time i has been obtained. From, the joint probability, the probability that the system has reached its capacity m times in time interval (0t] has been determined and the expectation and variance have been found explicitly. A criterion for the system to be optimum is established and is illustrated numerically.  相似文献   

15.
We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,np}n) time. This improves the previously known complexity O(min{p,np}2n).This research has been supported by the Spanish Science and Technology Ministry and FEDER Grant No. BFM2002-04525-C02-02.Received: October 2002 / Accepted: September 2003  相似文献   

16.
We present a method for estimating the complexity of an image based on Bennett's concept of logical depth. Bennett identified logical depth as the appropriate measure of organized complexity, and hence as being better suited to the evaluation of the complexity of objects in the physical world. Its use results in a different, and in some sense a finer characterization than is obtained through the application of the concept of Kolmogorov complexity alone. We use this measure to classify images by their information content. The method provides a means for classifying and evaluating the complexity of objects by way of their visual representations. To the authors' knowledge, the method and application inspired by the concept of logical depth presented herein are being proposed and implemented for the first time. © 2011 Wiley Periodicals, Inc. Complexity, 2011  相似文献   

17.
We determine exact values for the k-error linear complexity L k over the finite field of the Legendre sequence of period p and the Sidelnikov sequence of period p m  − 1. The results are
for 1 ≤ k ≤ (p m  − 3)/2 and for k≥ (p m  − 1)/2. In particular, we prove
  相似文献   

18.
Recently the first author presented exact formulas for the number of 2 n -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 n -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p n -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p n -periodic sequences over .   相似文献   

19.
We consider the standard linear complementarity problem (LCP): Find (x, y) R 2n such that y = M x + q, (x, y) 0 and x i y i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P 0 LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号