检索结果-内蒙古大学图书馆

Linear average-case complexity of algorithmic problems in groups

JOURNAL OF ALGEBRA 2025年 668卷 390-419页

作者： Olshanskii, Alexander Shpilrain, Vladimir Vanderbilt Univ Dept Math Nashville TN 37240 USA CUNY Dept Math New York NY 10031 USA

The worst-case complexity of group-theoretic algorithms has been studied for a long time. Generic-case complexity, or complexity on random inputs, was introduced and studied relatively recently. In this paper, we address the average-case time complexity of the word problem in several classes of groups and show that it is often the case that the average- case complexity is linear with respect to the length of an input word. The classes of groups that we consider include groups of matrices over rationals (in particular, polycyclic groups), some classes of solvable groups, as well as free products. Along the way, we improve several bounds for the worst-case complexity of the word problem in groups of matrices, in particular in nilpotent groups. For free products, we also address the average-case complexity of the subgroup membership problem and show that it is often linear, too. Finally, we discuss complexity of the identity problem that has not been considered before. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： average-case complexity Word problem Nilpotent groups Groups of matrices

来源：评论

学校读者我要写书评

暂无评论

average-case complexity of backtrack search for coloring sparse random graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2013年第8期79卷 1287-1301页

作者： Mann, Zoltan Adam Szajko, Aniko Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory H-1117 Budapest Hungary

We investigate asymptotically the expected number of steps taken by backtrack search for k-coloring random graphs G(n,p(n)) or proving non-k-colorability, where p (n) is an arbitrary sequence tending to 0, and k is constant. Contrary to the case of constant p, where the expected runtime is known to be O(1), we prove that here the expected runtime tends to infinity. We establish how the asymptotic behavior of the expected number of steps depends on the sequence p (n). In particular, for p(n) = d/n, where d is a constant, the runtime is always exponential, but it can be also polynomial if p (n) decreases sufficiently slowly, e.g. for p (n) = 1/ln n. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Graph coloring average-case complexity Search tree Random graphs Backtrack

来源：评论

学校读者我要写书评

暂无评论

average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field

引用

COMBINATORICS PROBABILITY AND COMPUTING 2022年第1期31卷 166-183页

作者： Gimenez, Nardo Matera, Guillermo Perez, Mariana Privitelli, Melina Univ Nacl Gen Sarmiento Inst Desarrollo Humano JM Gutierrez 1150B1613GSX Los Polvorines Buenos Aires Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat Ciudad UnivPabellon 1 RA-1428 Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn CONICET Buenos Aires DF Argentina Univ Nacl Hurlingham Inst Tecnol & Ingn Av Gdor Vergara 2222B1688GEZ Villa Tesei Buenos Aires Argentina Univ Nacl Gen Sarmiento Inst Ciencias JM Gutierrez 1150B1613GSX Los Polvorines Buenos Aires Argentina

We analyse the behaviour of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field $\mathbb{F}_{q}$ of q elements when the highest degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f that are relatively prime with g and for the average degree of $\gcd(g,f)$ . We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.

关键词： Finite fields rational points Euclidean algorithm symmetric functions resultant average-case complexity

来源：评论

学校读者我要写书评

暂无评论

Pseudorandomness and average-case complexity via uniform reductions

引用

COMPUTATIONAL complexity 2007年第4期16卷 331-364页

作者： Trevisan, Luca Vadhan, Salil Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA

Impagliazzo and Wigderson (1998) gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP not equal BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. In this paper: We obtain an optimal worst-case to average-case connection for EXP: if EXP not subset of BPTIME(t(n)), then EXP has problems that cannot be solved on a fraction 1/2 + 1/t'(n) of the inputs by BPTIME(t'(n)) algorithms, for t' = t(Omega(1)). We exhibit a PSPACE-complete self-correctible and downward self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson, which used a #P-complete problem with these properties. We argue that the results of lmpagliazzo and Wigderson, and the ones in this paper, cannot be proved via "black-box" uniform reductions.

关键词： pseudorandomness average-case complexity derandomization instance checkers

来源：评论

学校读者我要写书评

暂无评论

average-case complexity and decision problems in group theory

引用

ADVANCES IN MATHEMATICS 2005年第2期190卷 343-359页

作者： Kapovich, I Myasnikov, A Schupp, P Shpilrain, V Univ Illinois Dept Math Urbana IL 61801 USA CUNY City Coll Dept Math New York NY 10031 USA

We investigate the average-case complexity of decision problems for finitely generated groups, in particular, the word and membership problems. Using our recent results on "generic-case complexity", we show that if a finitely generated group G has word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups B-n all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type. (C) 2003 Elsevier Inc. All rights reserved.

关键词： average-case complexity generic-case complexity decision problems finitely presented groups

来源：评论

学校读者我要写书评

暂无评论

average-case complexity of the Whitehead problem for free groups

引用

COMMUNICATIONS IN ALGEBRA 2023年第2期51卷 799-806页

作者： Shpilrain, Vladimir CUNY City Coll Dept Math New York NY 10031 USA

The worst-case complexity of group-theoretic algorithms has been studied for a long time. Generic-case complexity, or complexity on random inputs, was introduced and studied relatively recently. In this paper, we address the average-case complexity (i.e., the expected runtime) of algorithms that solve a well-known problem, the Whitehead problem in a free group, which is: given two elements of a free group, find out whether there is an automorphism that takes one element to the other. First we address a special case of the Whitehead problem, namely deciding if a given element of a free group is part of a free basis. We show that there is an algorithm that, on a cyclically reduced input word, solves this problem and has constant (with respect to the length of the input) average-case complexity. For the general Whitehead problem, we show that the classical Whitehead algorithm has linear average-case complexity if the rank of the free group is 2. We argue that the same should be true in a free group of any rank but point out obstacles to establishing this general result.

关键词： Free group automorphisms Whitehead problem average-case complexity

来源：评论

学校读者我要写书评

暂无评论

average-case complexity of partial Boolean functions

引用

2nd International Symposium on Stochastic Algorithms

作者： Chashkin, A Moscow MV Lomonosov State Univ Fac Mech & Math Moscow 119992 Russia

The average-case complexity of partial Boolean functions is considered. For almost all functions it is shown that, up to a multiplicative constant, the average-case complexity does not depend on the size of the functi... 详细信息

ISBN: (纸本)3540201033

关键词： partial Boolean function average-case complexity straight-line program randomized straight-line program

来源：评论

学校读者我要写书评

暂无评论

On derandomization and average-case complexity of monotone functions

引用

THEORETICAL COMPUTER SCIENCE 2012年 434卷 35-44页

作者： Karakostas, George Kinne, Jeff van Melkebeek, Dieter Indiana State Univ Terre Haute IN 47809 USA McMaster Univ Hamilton ON L8S 4L8 Canada Univ Wisconsin Madison WI 53706 USA

We investigate whether circuit lower bounds for monotone circuits can be used to derandomize randomized monotone circuits. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized computations, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions - that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Derandomization Monotone circuits Monotone functions Randomized algorithm Pseudorandom generators average-case complexity

来源：评论

学校读者我要写书评

暂无评论

A lower bound on the average-case complexity of shellsort

引用

JOURNAL OF THE ACM 2000年第5期47卷 905-911页

作者： Jiang, T Li, M Vitányi, P Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA CWI NL-1098 SJ Amsterdam Netherlands

We demonstrate an Omega (pn(1+1/p)) lower bound on the average-case running time (uniform distribution) of p-pass Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.

关键词： algorithms performance theory average-case complexity computational complexity Kolmogorov complexity shellsort sorting

来源：评论

学校读者我要写书评

暂无评论

New and improved search algorithms and precise analysis of their average-case complexity

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2019年 95卷 743-753页

作者： Amrahov, Sahin Emrah Mohammed, Adnan Saher Celebi, Fatih V. Ankara Univ Comp Engn Dept TR-06830 Ankara Turkey Al Kitab Univ Dept Comp Engn Technol Coll Engn Tech Kirkuk Iraq Ankara Yildirim Beyazit Univ Comp Engn Dept Fac Engn & Nat Sci Ankara Turkey

In this paper, we consider the searching problem over ordered sequences. It is well known that Binary Search (BS) algorithm solves this problem with very efficient complexity, namely with the complexity theta(log(2)n). The developments of the BS algorithm, such as Ternary Search (TS) algorithm do not improve the efficiency. The rapid increase in the amount of data has made the search problem more important than in the past. And this made it important to reduce average number of comparisons in cases where the asymptotic improvement is not achieved. In this paper, we identify and analyze an implementation issue of BS. Depending on the location of the conditional operators, we classify two different implementations for BS which are widely used in the literature. We call these two implementations weak and correct implementations. We calculate precise number of comparisons in average case for both implementations. Moreover, we transform the TS algorithm into an improved ternary search (ITS) algorithm. We also propose a new Binary-Quaternary Search (BQS) algorithm by using a novel dividing strategy. We prove that an average number of comparisons for both presented algorithms ITS and BQS is less than for the case of correct implementation of the BS algorithm. We also provide the experimental results. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Binary search Ternary search Searching algorithm average-case complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：