Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk ∘ MAJk. We observe that the minimum value of k for which there exists a MAJk ∘ MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk ∘ MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3 + o(1). We show a worst case lower bound: if a MAJk ∘ MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19 + o(1).
The problem of multi-valued functions realization by circuits over special basis is inverstigated. The basis consis of Post negation and all monotone functions.
The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is finite.
In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system F is established. It equals ⌈logu(d(F)+1)⌉−O(1). Here d(F) is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system F; u is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.
Problem of multi-valued function realization by logic circuits in special bases is investigated. These bases consist of all monotone functions with zero weight and finite number of non-monotone functions with unit weight.
In this paper we consider the complexity of realization of k-valued logic functions by logic circuits over an infinite complete basis of special type. This basis contain all monotone functions with zero weight and non-monotone functions with non-zero weight. The problem of the complexity of a Boolean functions realization over basis containing all monotone functions and negation function has been completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates that is enough to realize any Boolean function f (the inversion complexity of the function f) equals log2(d(f)+1)[. Here d(f) is the maximum number of the function f values changes from grater to smaller over all increasing chains of tuples of variables values. In this paper the result of Markov is extended to the case of a k-valued logic function realization. We show that the minimum number of Post negations (i.e. functions of the form x+1 mod k) that is enough to realize an arbitrary function of k-valued logic equals ]log2(d(f)+1)[ and the minimum number of Lukasiewicz negation (i.e. functions of the form k-1-x) that is enough to realize an arbitrary k-valued logic function equals ]logk(d(f)+1)[. In addition, another classical result of Markov dealt with inversion complexity of a system of Boolean functions has been also extended to the k-valued logic functions case.
Some classical and contemporary treatments of justice in sociology, interrelations of the concepts of social justice, on the one hand, and of legitimacy, recognition, majority and minority, on the other hand.
The problem of the effective realization of Boolean functions and multi-valued logic functions by circuits in some infinite bases is considered. The bases consist of all monotone functions and finite number of non-monotone functions. The measure of the realization efficiency is non-monotone complexity. That is the number of non-monotone elements in the circuit (we assume that all monotone elements are «free»). The case of Boolean basis that consists of all monotone functions and negation function was considered by Markov. He established the exact value of the non-monotone complexity (it is also named «inversion complexity» in that case). This paper include survey of Markov theorem generalizations and several new estimations of the non-monotone complexity.