课题基金 / 基金详情

A Study on the Complexity of Negation-Limited Boolean Circuits

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/
关键词：
計算量理論回路計算量論理回路否定数限定回路反転計算量論理関数論理式

项目摘要

项目成果

MORIZUMI Hiroki的其他基金

相似基金

相关文献

中文摘要
翻译
在求反门数目受限的情况下，研究了由AND门、OR门和求反门组成的布尔电路的复杂性。对于公式、不确定电路和概率电路，我们主要得到了求逆复杂度的结果，求反门是计算布尔函数的最小求反门数目。本研究将布尔电路视为计算的数学模型，并从计算复杂性理论的角度对其进行了研究。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Negation-Limited Complexity of Parity and Inverters
奇偶校验和反相器的否定有限复杂性
DOI： --
发表时间： 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
概率电路中的限制负数
DOI： --
发表时间： 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
共 6 条
    A Study on the Complexity of Bounded Width Boolean Circuits
    • 批准号：
      23700020
    • 项目类别：
      Grant-in-Aid for Young Scientists (B)
    • 资助金额：
      $2.08万
    • 财政年份：
      2011
    • 负责人：
      MORIZUMI Hiroki
    • 依托单位：
      Shimane University
    海外基金