English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Measures of circuit complexity are usually analyzed to ensure the computationof Boolean functions with economy and efficiency. One of these measures isenergy complexity, which is related to the number of gates that output true ina circuit for an assignment. The idea behind energy complexity comes from thecounting of `firing' neurons in a natural neural network. The initial model isbased on threshold circuits, but recent works also have analyzed the energycomplexity of traditional Boolean circuits. In this work, we discuss the timecomplexity needed to compute the best-case energy complexity among satisfyingassignments of a monotone Boolean circuit, and we call such a problem asMinEC$^+_M$. In the MinEC$^+_M$ problem, we are given a monotone Booleancircuit $C$, a positive integer $k$ and asked to determine whether there is asatisfying 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 circuitis planar. Besides, we show that the problem is W[1]-hard but in XP whenparameterized by the size of the solution. In contrast, we show that when thesize of the solution and the genus of the input circuit are aggregatedparameters, the MinEC$^+_M$ problem becomes fixed-parameter tractable.

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