Enumeration Classes Defined by Circuits
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in $\mathbf{DelayP}$, for which a formal way of comparison was not possible to this day.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits
We consider the problem EnumIP of enumerating prime implicants of Boolean functions represented by decision decomposable negation normal form (dec-DNNF) circuits. We study EnumIP from dec-DNNF within the framework of enu…
NegationSome enumerations of binary digital images
The topology of digital images has been studied much in recent years, but no attempt has been made to exhaustively catalog the structure of binary images of small numbers of points. We produce enumerations of several cla…
Data Complexity Measures for Quantum Circuits Architecture Recommendation
Quantum Parametric Circuits are constructed as an alternative to reduce the size of quantum circuits, meaning to decrease the number of quantum gates and, consequently, the depth of these circuits. However, determining t…
PAC Learning, VC Dimension, and the Arithmetic Hierarchy
We compute that the index set of PAC-learnable concept classes is $m$-complete $\Sigma^0_3$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumeratio…
AllPAC learningCategories of Differentiable Polynomial Circuits for Machine Learning
Reverse derivative categories (RDCs) have recently been shown to be a suitable semantic framework for studying machine learning algorithms. Whereas emphasis has been put on training methodologies, less attention has been…
BIG-bench Machine Learning