Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Acta Informaticaarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Acta Informatica
Article . 1989 . Peer-reviewed
License: Springer Nature TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Through the mincing machine with a Boolean layer cake

Nonstandard computations over Boolean circuits in the lower-bounds-to-circuit-size complexity proving
Authors: Belaga, Edward G.;

Through the mincing machine with a Boolean layer cake

Abstract

The purpose of the present paper is threefold. Firstly, it introduces an abstract theory of straight-line (circuit) Boolean computations and complexity based on a strict separation of the syntax and semantics of Boolean circuits; the usual (standard) way to compute a circuit becomes thus only one of many other (nonstandard) operation modes over the circuit. Secondly, we construct and investigate three particular nonstandard operation modes, of which one, the mincing (M-) mode, is the superposition of two others, the injection and ejection modes respectively. The M-mode uses the circuit as a pipe-lining device, channeling simultaneously through each layer of the circuit (a layer comprises all nodes of a given individual depth) information stored in previous layers and renewing the input- and storing the output- information after every such parallel step; the number of steps is equal to the double depth of the circuit. The function computed by the M-mode is richer as a functional device than the standard functional (S-) representation of a circuit; in particular, it not only detects paths connecting individual inputs and outputs of a circuit, as the S-representation does, but their lengths as well. Thirdly, based on the M-mode, a new (in fact, the first known nontrivial) general lower bound to the relative circuit-size complexity of a Boolean function is presented, in the form of the inequality \(s(f,C')\geq m(f,C')\), which means that the circuit-size (CS-) complexity of a Boolean function \(f\) with respect to a fixed subset \(C'\subseteq C\) of the set \(C\) of all Boolean circuits is at least as big as the mincing complexity of \(f\) with respect to the same subset; choosing appropriate subsets, one arrives at the complete, monotone, synchronous; locally synchronous (and in algebraic computations which can be naturally treated in the same vein, linear, bilinear) or other CS-complexities The corresponding mincing complexity is defined as the minimum, taken over all circuits from \(C'\) standardly computing \(f\), of the Boolean dimension of the function computing by the M-mode; the Boolean dimension of a function is equal by definition to the 2-logarithm of the cardinality of the function's image. The advantage to work with the new lower bound is that it is defined as a minimum taken over a relatively well defined functional subspace associated with \(f\) and \(C'\), and not, as in the CS-complexity case, over a subset of circuits, i.e., a mixed discrete-continuum structure of an obscure nature (the real reason why the lower bound problem is so difficult). To demonstrate how the above inequality works, we prove an \(\Omega(m \log m)\) lower bound to the locally synchronous CS-complexity of the \(m\)-dimensional cyclic convolution. This particular result is important for several reasons: (i) it improves the more than ten-years old nonlinear lower bound to the synchronous CS-complexity of the same function, (ii) it can not be, apparently, proved by previously known methods, (iii) there exist functions (an example will be given in this paper) with the linear locally synchronous and a nonlinear synchronous CS-complexities.

Keywords

syntax and semantics of Boolean circuits, Switching theory, applications of Boolean algebras to circuits and networks, Networks and circuits as models of computation; circuit complexity, Analysis of algorithms and problem complexity, mincing complexity, locally synchronous CS-complexity, m-dimensional cyclic convolution, straight-line Boolean computations, relative circuit-size complexity of a Boolean function

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    1
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
1
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!