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

Representing Boolean functions as polynomials modulo composite numbers

computational Complexity 1994年第4期4卷 367-382页

作者： Barrington, David A.Mix Beigel, Richard Rudich, Steven Computer Science Department University of Massachusetts Amherst 01003-4610 MA P. O. Box 34610 United States Department of Computer Science Yale University New Haven 06520-8285 CT P.O. Box 208285 United States School of Computer Science Carnegie Mellon University Pittsburgh 15213 PA 5000 Forbes Ave United States

Define the MODm-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments {Mathematical expression}, {Mathematical expression} ... 详细信息

Define the MOD_m-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments {Mathematical expression}, {Mathematical expression} iff {Mathematical expression}. We obtain the unexpected result that the MOD_m-degree of the OR of N variables is {Mathematical expression}, where r is the number of distinct prime factors of m. This is optimal in the case of representation by symmetric polynomials. The MOD_n function is 0 if the number of input ones is a multiple of n and is one otherwise. We show that the MOD_m-degree of both the MOD_n and {Mathematical expression} functions is N^Ω(1) exactly when there is a prime dividing n but not m. The MOD_m-degree of the MOD_m function is 1;we show that the MOD_m-degree of {Mathematical expression} is N^Ω(1) if m is not a power of a prime, O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD_mP classes (such as ⊕P) have this structure: MOD_mP is closed under complementation and union iff m is a prime power, and MOD_nP is a subset of MOD_mP iff all primes dividing n also divide m. © 1994 Birkhäuser Verlag.

关键词： circuit complexity Complexity of finite functions computation by polynomials relativized complexity Subject classifications: 68Q15, 68Q40

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：