Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits

2025-04-27 0 0 4.83MB 28 页 10玖币

侵权投诉

Computing the Best Case Energy Complexity

of Satisfying Assignments in Monotone

Circuits

Janio Carlos Nascimento Silva1and U´everton S. Souza2,5

1Instituto Federal do Tocantins, Campus Porto Nacional, Porto Nacional, Brazil

2Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics,

University of Warsaw, Warsaw, Poland

5Instituto de Computa¸c˜ao, Universidade Federal Fluminense, Niter´oi, Brasil

October 14, 2022

Abstract

Measures of circuit complexity are usually analyzed to ensure the

computation of Boolean functions with economy and eﬃciency. One

of these measures is the 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 ‘ﬁring’

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 complex-

ity among satisfying assignments of a monotone Boolean circuit, and

we call such a problem as MinEC+

M. In the MinEC+

Mproblem, we are

given a monotone Boolean circuit C, a positive integer kand asked to

determine whether there is a satisfying assignment Xfor Csuch that

EC(C, X)≤k, where EC(C, X) is the number of gates that output

true in Caccording to the assignment X. We prove that MinEC+

Mis

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 param-

eters, the MinEC+

Mproblem becomes ﬁxed-parameter tractable.

Keywords: energy complexity, monotone circuit, planar, genus, FPT.

arXiv:2210.06739v1 [cs.CC] 13 Oct 2022

1 Introduction

Circuit Complexity is a research ﬁeld that aims to study bounds for measures

(such as size and depth) of circuits that compute Boolean functions. The size

of a circuit is its number of logic gates, and its depth is the largest path from

any input to the output gate. A circuit complexity analysis can provide

lower/upper bounds on circuits classes that represent classic decision prob-

lems besides the possibility to identify eﬃcient Boolean circuits according

to speciﬁc properties (see [14, 19, 30]). In addition, some important bounds

are described to deal with diﬀerent deﬁnitions of size [1]. From a combina-

torial point of view, several optimization problems address the minimization

of measures in some circuits classes, such as the notorious Weighted Cir-

cuit Satisfiability problem, where the weight measures the amount of

true values assigned to the input variables.

Despite this ‘zoo of measures’, optimizing properties like size and depth

does not always guarantee an ‘eﬃcient’ design of a speciﬁc circuit class.

Depending on the purpose, a circuit with small size (either considering gates

or wires) or depth can be inappropriate; such a situation was identiﬁed in [27].

When faced with threshold circuits used as an artiﬁcial neural network, it

is possible to observe a contrast with neurons of the human brain. The

authors in [27] (based in neuroscience literature) argue that the activation of

neurons in a human brain happens sparsely. It was shown in [17] that the

metabolic cost of a single spike in cortical computation is very high in a way

that approximately 1% of the neurons can be activated simultaneously. This

phenomenon happens due to the asymmetric energy cost between neurons

activated and non-activated in natural cases. From the other side, digital

circuits, when satisﬁed (outputting true), on average activate 50% of the

gates.

Under diﬀerent perspectives, ‘energy’ (or ‘power’) of a circuit is a measure

that has a lot of attention in the literature. Due to multiple models (from

biology, electronics, or purely theoretical), several works address diﬀerent

ways of analyzing the energy of a circuit. In [16], the energy consumption of

a circuit considers the switching energy consumed by wires (edges) and gates

of VLSI circuits. In [4] and [5], it is analyzed the voltage-to-energy consumed

by the gates, taking into consideration the failure-to-energy. Other diﬀerent

models are explored in [23] and [6], such works try to explore concepts of

energy too intrinsic to the design of practical circuits on electronics.

In this paper, we deal with a circuit complexity measure called energy

complexity (EC). The idea behind this measure is to evaluate the number

of gates in a circuit that returns true for an assignment. A similar concept

called ‘power of circuit’ was studied by [28]. The term energy complexity

was introduced in [27] as an alternative to the dilemma artiﬁcial vs natural

described above. In [27], the authors prove that the minimization of circuit

energy complexity obtains a diﬀerent structure from the minimization of

classical circuit complexity measures and potentially closer to the structure of

neural networks in the human brain. The authors proved initial lower bounds

for energy complexity and other circuit complexity measure called entropy.

For an analysis more focused on circuit complexity and recent bounds for

energy complexity of Boolean functions we refer to [10].

With a diﬀerent perspective, this work dedicates attention to optimiza-

tion and decision problems related to computing the energy complexity of

a circuit. More precisely, we consider the problem of determining the satis-

fying assignment with minimum energy consumption in monotone circuits,

i.e., the best case energy complexity of a satisfying assignment in the class

of monotone circuits, called MinEC+

M. Our focus is on time (parameterized)

complexity of the MinEC+

Mproblem.

The paper’s sequence has some preliminaries and the problem deﬁnition,

a discussion of its NP-completeness on planar circuits, a W[1]-hardness proof

and an XP algorithm for the case where the number of gates to be activated is

considered as parameter. Finally, we present an FPT algorithm for MinEC+

when parameterized either by the treewidth of the input circuit or by the

genus of the input plus the size of the solution.

An extended abstract of this paper has been presented in AAIM 2021

[22].

Preliminaries

ABoolean circuit is a model that computes a Boolean function g:{0,1}n→

{0,1}over a basis of operators (e.g. {AND,OR,NOT, ...}). In terms of Graph

Theory, a Boolean circuit is a directed acyclic graph C(V, E) where the set

of vertices V= (I, G, {vout}) is partitioned into: (i) a set of inputs I=

{i1, i2, . . . }composed by the vertices of in-degree 0; (ii) a set of gates G=

{g1, g2, . . . }, which are vertices labeled with Boolean operators; (iii) and the

single output (sink) vertex vout with out-degree equal to 0 and also labeled

with a Boolean operator (see Fig. 1). The input vertices represent Boolean

variables that can take values from {0,1}({true,false}, depending on the

conventions), and the label/operator of a gate or output vertex wis given by

f(w). A monotone circuit is a Boolean circuit where the Boolean operators

allowed are in {AND,OR}. An assignment of C is a vector X= [x1, x2, . . . , x|I|]

of values for the set of inputs I, where for each j,xj∈ {0,1}is the value

assigned to input ij. We say that Xis a satisfying assignment if the circuit

Cevaluates to 1 (true) when Xis given as input.

(a) Graph representation of circuit C.(b) Cunder a satisfying assignment.

Figure 1: Graph representation and a satisfying assignment.

Given a Boolean circuit Cand an assignment X, the Energy Complexity

of Xinto C,EC(C, X), is deﬁned as the number of gates that output true

in Caccording to the assignment X. The (Worst-Case) Energy Complexity

of C(denoted by EC(C)) is the maximum EC(C, X) among all possible

assignments X(See [10]). Analogously, the Best-Case Energy Complexity of

C(denoted by MinEC(C)) is the minimum EC(C, X) among all possible

assignments X.

In [2, 3], a measure called certiﬁcation-width was described, which is the

size of a minimum subset of edges that are enough to certiﬁcate a satisfying

assignment. Such edges form a structure called succinct certiﬁcate that can

be seen as a minimal map of edges to be followed in order to activate the

output gate. Similar structures, denoted by accepting subtree, positive proof,

or solution subgraph, can also be found in [29, 11, 24, 25, 18].

Note that there are similarities between certiﬁcation-width and energy

complexity. Both measures indicate saturation levels of circuits, but while

certiﬁcation-width focuses on edges, energy complexity is about the activa-

tion of gates. However, energy complexity presents two additional challenges:

(i) EC ignores the ‘ﬁring’ of input gates; (ii) EC counts activated gates even

if its signal does not reach the output gate (due to unsatisﬁed gates – see

Fig. 2 ). These two issues forbid rushed conclusions about EC based on

what we know about certiﬁcation-width. Nevertheless, the study in [2] also

motivates the study of the complexity of computing the best case energy

complexity of satisfying assignments in monotone circuits.

Note that in energy complexity problems in addition to working with

the gates needed to satisfy the circuit, it is still necessary to handle gates

that assignments may collaterally activate. Such behavior makes working

Figure 2: Anomalous behavior in certiﬁcates for MinEC+

M. Note that the

edge (i4, g2) produces a ‘leak’ of the assignment, i.e. g2output true (increas-

ing the energy complexity), but its signal is not relevant to satisfy vout.

with energy complexity problems more challenging than typical satisfying

problems where the focus is only on the minimal set of inputs, gates, or

wires/edges suﬃcient to satisfy the circuit.

While computing the worst-case energy complexity of satisfying assign-

ments in monotone circuits is trivial (just activate all inputs), the problem of

computing the best-case energy complexity among all satisfying assignments

in monotone circuits seems a challenge. Therefore, in this work, we address

this particular case where the circuit is monotone, focusing on the following

decision problem:

Best-Case Energy Complexity of Satisfying Assignments in

Monotone Circuits – MinEC+

Instance: A monotone Boolean circuit Cand a positive integer k.

Question: Is there a satisfying assignment Xfor Csuch that

EC(C, X)≤k?

Besides, we denote by k-MinEC+

Mthe parameterized version of MinEC+

where kis taking as the parameter.

2 Computational complexity analysis

In this section, we present our (parameterized) complexity results regarding

MinEC+

M. Since planarity is a notion with signiﬁcant relevance in the ﬁeld

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ComputingtheBestCaseEnergyComplexityofSatisfyingAssignmentsinMonotoneCircuitsJanioCarlosNascimentoSilva1andUevertonS.Souza2,51InstitutoFederaldoTocantins,CampusPortoNacional,PortoNacional,Brazil2InstituteofInformatics,FacultyofMathematics,InformaticsandMechanics,UniversityofWarsaw,Warsaw,Poland5Ins...

展开>> 收起<<

Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits.pdf

共28页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: