A Study on the Complexity of Negation-Limited Boolean Circuits

负数限制布尔电路的复杂性研究

• 批准号: 21700002
• 负责人: MORIZUMI Hiroki
• 金额: $ 1.41万
• 依托单位: Shimane University (2010-2011)Kyoto University (2009)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21700002/
• 关键词: 計算量理論; 回路計算量; 論理回路; 否定数限定回路; 反転計算量; 論理関数; 論理式

We investigated the complexity of Boolean circuits which consist of AND gates, OR gates and Negation gates for the case that the number of Negation gates is restricted. We mainly obtained results on the inversion complexity, which is the minimum number of Negation gates to compute a Boolean function, for formulas, non-deterministic circuits and probabilistic circuits. In this study, Boolean circuits are considered as a mathematical model of computation, and we studied it from the viewpoint of the computational complexity theory.

本文研究了由与门、或门和非门组成的布尔电路在非门数目有限的情况下的复杂性。主要得到了公式电路、非确定性电路和概率电路的求逆复杂度的结果。求逆复杂度是计算布尔函数所需的最少否定门数。本文将布尔电路作为一种计算的数学模型，从计算复杂性理论的角度对其进行了研究。

项目成果

Negation-Limited Complexity of Parity and Inverters

奇偶校验和反相器的否定有限复杂性

• 发表时间: 2006
• 期刊: Proc. the 17th Annual International Symposium on Algorithms (ISAAC 2006) LNCS 4288
• 作者: K.Iwama;H.Morizumi;J.Tarui
• 通讯作者: J.Tarui

Limiting Negations in Probabilistic Circuits

概率电路中的限制负数

• 发表时间: 2012
• 作者: A.Tanaka;H.Imai;M.Miyakoshi;森住 大樹
• 通讯作者: 森住 大樹

Improved Approximation Algorithms for Minimum AND-Circuits Problem via k-Set Cover

通过 k 集覆盖改进最小与电路问题的近似算法

• DOI: 10.1016/j.ipl.2010.11.019
• 发表时间: 2011
• 期刊: Information Processing Letters
• 影响因子: 0.5
• 作者: Nemoto H;Nakano K;Masuda K;Wada K;Ardin AC;Nomura R;Ooshima T;Hiroki Morizumi
• 通讯作者: Hiroki Morizumi

Negation-Limited Inverters of Linear Size

线性尺寸的负限制反相器

• DOI: 10.1587/transinf.e93.d.257
• 发表时间: 2010
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: Hiroki Morizumi;and Genki Suzuki
• 通讯作者: and Genki Suzuki

Limiting Negations in Formulas

• DOI: 10.1007/978-3-642-02927-1_58
• 发表时间: 2009-07
• 作者: Hiroki Morizumi