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

COMMUNICATIONS OF THE ACM 1977年第9期20卷 625-633页

作者： RABIN, MO HEBREW UNIV JERUSALEM DEPT MATHJERUSALEM 91000ISRAEL

Examines the framework for research in the theory of complexity of computations. Emphasis on the interrelation between seemingly diverse problems and methods; Evaluation of an algebraic expression; Cost functions of a... 详细信息

关键词： algebraic complexity complexity of computations intractable problems probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

A DUALITY BETWEEN BOOLEAN FUNCTIONS

引用

JOURNAL OF THE INSTITUTE OF MATHEMATICS OF JUSSIEU 2010年第3期9卷 633-652页

作者： Poizat, Bruno Univ Lyon 1 Inst Camille Jordan F-69622 Villeurbanne France

Since any function f(x1, … , xm) from {0, 1}m in a finite field k can be uniquely written as a multilinear polynomial, we associate to it its inverse dual f*(x1, … , xm) expressing the coefficients of this canonical polynomial. We show that the unlikely hypothesis that the class P(k) of sequences of functions of polynomial complexity be closed by duality is equivalent to the well-known hypothesis P = #pP, where p is the characteristic of *** a first section we expose the result in the frame of classical Boolean calculus, that is, when k = ℤ/2ℤ. In a second section we treat the general case, introducing a notion of transformation whose duality is a special case; the transformations form a group isomorphic to GL2(k); among them, we distinguish the benign transformations, which have a weak effect on the complexity of functions; we show that, in this respect, all the non-benign transformations have the same power of *** the third section we consider functions from km into k, and in the last, after introducing #P = P to the landscape, we compare our results with those of Guillaume Malod, concerning the closure by ‘coefficient-function’ of various classes of complexity of sequences of polynomial defined in Valiant's *** k est un corps fini, toute fonction f(x1, … , xm) de {0, 1}m dans k s'écrit de manière unique comme un polynôme, à coefficients dans k, de degré un ou zéro en chacune de ses variables ; on peut donc lui associer une fonction f*(x1, … , xm), sa duale inverse, qui exprime les coefficients de son polynôme canonique. Nous considérons l'improbable hypothèse que la classe P(k), formée des suites de fonctions calculables en un nombre d'opérations (additions et multiplications) de croissance polynomialement bornée, soit close par dualité ; nous montrons qu'elle équivaut à une hypothèse bien connue en Théorie de la Complexité sous le nom de P = #pP, où p est la caractéristique de *** une première section, nous exposons ce résultat lorsque k = ℤ/2ℤ

关键词： complexité des calculs circuits et termes arithmétiques parallélisation réduction parcimonieuse Valiant Malod complexity of computations arithmetic circuits and terms parallelization parsimonious reduction Valiant Malod

来源：评论

学校读者我要写书评

暂无评论

ON MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL

引用

SIAM JOURNAL ON COMPUTING 1980年第2期9卷 225-229页

作者： WINOGRAD, S

The multiplicative complexity of the direct product of algebras $A_p $ of polynomials modulo a polynomial P is studied. In particular, we show that if P and Q are irreducible polynomials then the multiplicative complexity of $A_{\text{P}} \times A_{\text{Q}} $ is $2\deg ({\text{P}})\deg ({\text{Q}}) - {\text{k}}$, where k is the number of factors of P in the field extended by a root of ${\text{Q}}$.

关键词： complexity of computations multiplicative complexity product of polynomials

来源：评论

学校读者我要写书评

暂无评论

Inversion operations in algebraic structures

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2023年第4期12卷 315-322页

作者： Alaev, Pavel Sobolev Inst Math Pr Koptuga 4 Novosibirks 630090 Russia

We consider a wide series of classes of algorithmic complexity. We fix such a class and investigate the complexity of the inversion operation in classical algebraic structures, like groups or fields. In addition, we a... 详细信息

关键词： Computability polynomial computability complexity of computations algebraic classes inversion operation

来源：评论

学校读者我要写书评

暂无评论

Almost Context-Free Languages

引用

Fundamenta Informaticae 1986年第3期9卷 283-321页

作者： Chytil, Michal P. Charles University Malostranské nám. 25 118 00 Praha 1 – Malá Strana Czechoslovakia

We define a superclass of the class of context-free languages, denoted ACFL (almost context-free languages) and construct an infinite sequence of non-context-free languages of decreasing complexity, belonging to ACFL. The languages in ACFL share many important properties of context-free *** example, a slight generalization of pumping lemma for context-free languages holds also for languages in ACFL. Similarly, some of the questions decidable for context-free languages are decidable in ACFL and start to be undecidable immediately outside the class. ACFL is a full AFL and contains an infinite strictly decreasing chain of full AFLs.

关键词： Almost context-free language context-free language one-way auxiliary pushdown automaton pumping lemma abstract family of languages complexity of computations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：