论文标题
计算单调电路中满足分配的最佳案例能量复杂性
Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits
论文作者
论文摘要
通常分析电路复杂性的度量，以确保以经济和效率计算布尔功能。这些措施之一是能量复杂性，这与在电路中输出true的门数有关。能量复杂性背后的想法来自自然神经网络中“射击”神经元的计数。最初的模型基于阈值电路，但最近的作品也分析了传统布尔电路的能量复杂性。在这项工作中，我们讨论了计算单调布尔电路的满足作业中最佳能量复杂性所需的时间复杂性，我们称之为Minec $^+_ m $的问题。在Minec $^+_ m $问题中，我们获得了单调布尔电路$ c $，一个正整数$ k $，并要求确定是否有令人满意的任务$ x $，$ c $，以便$ ec（c，x）\ leq k $，$ ec（c，c，x）$ c $ c $ c $ x $ x $ x $ x $ x $ x $ x $ c。我们证明，即使输入单调电路是平面，Minec $^+_ m $也是NP填充。此外，我们表明问题是W [1] -HARD，但当通过解决方案的大小进行参数时，在XP中。相比之下，我们表明，当解决方案的大小和输入电路的属是聚合参数时，Minec $^+_ m $问题就变成了固定参数。
Measures of circuit complexity are usually analyzed to ensure the computation of Boolean functions with economy and efficiency. One of these measures is energy complexity, which is related to the number of gates that output true in a circuit for an assignment. The idea behind energy complexity comes from the counting of `firing' neurons in a natural neural network. The initial model is based on threshold circuits, but recent works also have analyzed the energy complexity of traditional Boolean circuits. In this work, we discuss the time complexity needed to compute the best-case energy complexity among satisfying assignments of a monotone Boolean circuit, and we call such a problem as MinEC$^+_M$. In the MinEC$^+_M$ problem, we are given a monotone Boolean circuit $C$, a positive integer $k$ and asked to determine whether there is a satisfying assignment $X$ for $C$ such that $EC(C,X) \leq k$, where $EC(C,X)$ is the number of gates that output true in $C$ according to the assignment $X$. We prove that MinEC$^+_M$ is NP-complete even when the input monotone circuit is planar. Besides, we show that the problem is W[1]-hard but in XP when parameterized by the size of the solution. In contrast, we show that when the size of the solution and the genus of the input circuit are aggregated parameters, the MinEC$^+_M$ problem becomes fixed-parameter tractable.
