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

generic complexity of Presburger Arithmetic

THEORY OF COMPUTING SYSTEMS 2010年第1期46卷 2-8页

作者： Rybalov, Alexander N. RAS SB Inst Math Omsk Branch Omsk 644099 Russia

Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27-41, 1974) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665-694, 2003) a theory of generic-case complexity was developed, where algorithmic problems are studied on "most" inputs instead of set of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic sets).

关键词： generic complexity Presburger Arithmetic

来源：评论

学校读者我要写书评

暂无评论

generic complexity of the Diophantine problem

引用

GROUPS complexity CRYPTOLOGY 2013年第1期5卷 25-30页

作者： Rybalov, Alexander Sobolev Inst Math Novosibirsk 630090 Russia

The generic-case approach to algorithmic problems was suggested by Myasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies the behavior of an algorithm on "most" or "typical" inputs. The remaining inputs form the so-called black hole of the algorithm. In the present paper we consider Hilbert's tenth problem and use arithmetic circuits for the representation of Diophantine equations. We prove that this Diophantine problem is generically hard in the following sense. For every generic polynomial algorithm deciding this problem, there exists a polynomial algorithm for random generation of inputs from the black hole.

关键词： generic complexity Hilbert's tenth problem diophantine equation

来源：评论

学校读者我要写书评

暂无评论

generic complexity of Presburger Arithmetic

Generic Complexity of Presburger Arithmetic

引用

2nd International Computer Science Symposium in Russia (CSR 2007)

作者： Rybalov, Alexander N. RAS SB Inst Math Omsk Branch Omsk 644099 Russia

ISBN: (纸本)9783540745099

关键词： generic complexity Presburger Arithmetic

来源：评论

学校读者我要写书评

暂无评论

Small generic hardcore subsets for the discrete logarithm: Short secret DL-keys

引用

INFORMATION PROCESSING LETTERS 2001年第2期79卷 93-98页

作者： Schnorr, CP Univ Frankfurt Fachbereich Math Informat D-60439 Frankfurt Germany Bell Labs Murray Hill NJ 07974 USA

Let G be a group of prime order q with generator g. We study hardcore subsets H subset of G of the discrete logarithm (DL) log(g) in the model of generic algorithms. In this model we count group operations such as multiplication and division, while computations with non-group data are for free. It is known from Nechaev [Math. Notes 55 (1994) 165] and Shoup [Lecture Notes in Comp. Sci., Vol. 1233, Springer, Berlin, 1997, p. 256] that generic DL-algorithms for the entire group G must perform root 2q generic steps. We show that DL-algorithms for small subsets H subset of G require 1/2m + o(m) generic steps for almost all H of size #H = m with m less than or equal to rootq. Conversely, 1/2m + 1 generic steps are sufficient for all H subset of G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 1/2 log(2) q bits long. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： computational complexity cryptography discrete logarithm (DL) generic algorithms generic complexity hardcore subsets

来源：评论

学校读者我要写书评

暂无评论

An average study of hypergraphs and their minimal transversals

引用

THEORETICAL COMPUTER SCIENCE 2015年 596卷 124-141页

作者： David, Julien Lhote, Loick Mary, Arnaud Rioult, Francois Univ Paris 13 LIPN F-93430 Villetaneuse France CNRS UMR 7030 F-93430 Villetaneuse France CNRS ENSICAEN GREYC Caen France Univ Caen F-14032 Caen France Univ Lyon 1 CNRS LBBE UMR5558 F-69622 Villeurbanne France

In this paper, we study some average properties of hypergraphs and the average complexity of algorithms applied to hypergraphs under different probabilistic models. Our approach is both theoretical and experimental since our goal is to obtain a random model that is able to capture the real-data complexity. Starting from a model that generalizes the Erdos-Renyi model [10,11], we obtain asymptotic estimations on the average number of transversals, irredundants and minimal transversals in a random hypergraph. We use those results to obtain an upper bound on the average complexity of algorithms to generate the minimal transversals of a hypergraph. Then we make our random model more complex in order to bring it closer to real-data and identify cases where the average number of minimal transversals is at most polynomial, quasi-polynomial or exponential. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Hypergraph Minimal transversal Enumeration Probabilistic analysis Average complexity generic complexity

来源：评论

学校读者我要写书评

暂无评论

On the generic Undecidability of the Halting Problem for Normalized Turing Machines

引用

THEORY OF COMPUTING SYSTEMS 2017年第4期60卷 671-676页

作者： Rybalov, Alexander Omsk State Tech Univ Prospekt Mira 11 Omsk 644050 Russia

Hamkins and Miasnikov presented in (Notre Dame J. Formal Logic 47(4), 515-524, 2006) a generic algorithm deciding the classical Halting Problem for Turing machines with one-way tape on a set of asymptotic probability one (on a so-called generic set). Rybalov (Theor. Comput. Sci. 377, 268-270, 2007) showed that there is no generic algorithm deciding this problem on strongly generic sets of inputs (some subclass of generic sets). In this paper we prove that there is no generic algorithm deciding the Halting Problem for normalized Turing machines on generic sets of inputs. Normalized Turing machines have programs with the following natural restriction: internal states with large indices are not allowed at the beginning of the program. This condition does not reduce the class of computable functions because for every Turing machine there exists a normalized Turing machine which computes the same function. Our proof holds for machines with one-way and two-way tape. It also implies that the Hamkins-Miasnikov algorithm is not generic for normalized Turing machines.

关键词： generic complexity Halting problem

来源：评论

学校读者我要写书评

暂无评论

On the strongly generic undecidability of the Halting Problem

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期377卷 268-270页

作者： Rybalov, Alexander Omsk State Univ Dept Math Logic Omsk 644077 Russia

It has been shown in [J.D. Harnkins, A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47(4) (2006) 515-524] that the classical Halting Problem for Turing machines with one-way tape is decidable on a "large" set of Turing machines (a so-called generic set). However, here we prove that the Halting Problem remains undecidable when restricted to an arbitrary "very large" set of Turing machines (a so-called strongly generic set). Our proof is independent of a Turing machine model. (c) 2007 Elsevier B.V All rights reserved.

关键词： generic complexity Halting Problem

来源：评论

学校读者我要写书评

暂无评论

generic hardness of the Boolean satisfiability problem

引用

GROUPS complexity CRYPTOLOGY 2017年第2期9卷 151-154页

作者： Rybalov, Alexander Omsk State Tech Univ Prospekt Mira 11 Omsk 644050 Russia

It follows from the famous result of Cook about the NP-completeness of the Boolean satisfiability problem that there is no polynomial algorithm for this problem if P not equal NP. In this paper, we prove that the Boolean satisfiability problem remains computationally hard on polynomial strongly generic subsets of formulas provided P not equal NP and P = BPP. Boolean formulas are represented in the natural way by labeled binary trees.

关键词： Boolean satisfiability problem generic complexity probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Average complexity of Moore's and Hoperoft's algorithms

引用

THEORETICAL COMPUTER SCIENCE 2012年 417卷 50-65页

作者： David, Julien Univ Paris 13 CNRS LIPN UMR 7030 F-93430 Villetaneuse France

In this paper we prove that for the uniform distribution on complete deterministic automata, the average time complexity of Moore's state minimization algorithm is theta(n log log n), where n is the number of states in the input automata and the number of letters in the alphabet is fixed. Then, an unusual family of implementations of Hoperoft's algorithm is characterized, for which the algorithm will be proved to be always faster than Moore's algorithm. Finally, we present experimental results on the usual implementations of Hoperoft's algorithm. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Finite automata Minimization algorithm Moore Hoperoft Average complexity generic complexity

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Density and Computability

引用

RUSSIAN MATHEMATICS 2021年第10期65卷 1-9页

作者： Batyrshin, I. I. Kazan Fed Univ 18 Kremlyovskaya Str Kazan 420008 Russia

We prove that a set is bi-immune if and only if its images under computable permutations are not generically computable or effectively densely computable sets. An example of a coarsely computable bi-immune set is constructed. It is also proved that for any set there is a permutation from the same Turing degree such that its image under this permutation is an effectively densely computable set. Upper densities of weakly 1-generic sets are studied.

关键词： asymptotic density generic complexity bi-immune set Turing degrees weakly 1-generic set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：