共查询到20条相似文献,搜索用时 267 毫秒
1.
I. P. Chukhrov 《Journal of Applied and Industrial Mathematics》2012,6(1):42-55
Studying the extreme kernel face complexes of a given dimension, we obtain some lower estimates of the number of shortest
face complexes in the n-dimensional unit cube. The number of shortest complexes of k-dimensional faces is shown to be of the same logarithm order as the number of complexes consisting of at most 2
n−1 different k-dimensional faces if 1 ≤ k ≤ c · n and c < 0.5. This implies similar lower bounds for the maximum length of the kernel DNFs and the number of the shortest DNFs of
Boolean functions. 相似文献
2.
A. A. Voronenko 《Computational Mathematics and Modeling》2007,18(1):55-65
Two classical problems are considered: recognizing the properties of a Boolean function given a column of its values and constructing
a diagnostic test. The problems are investigated for nonrepeating functions in an arbitrary basis B. For the first problem, the decomposition method is applied to prove linear complexity of the corresponding sequential circuits;
for the second problem we derive the order of the Shannon functions for a number of bases, in particular, for the basis of
all functions of four variables.
__________
Translated from Prikladnaya Matematika i Informatika, No. 23, pp. 67–84, 2006. 相似文献
3.
Jürg Ganz 《Finite Fields and Their Applications》1996,2(4):348-368
Binary representations of finite fields are defined as an injective mapping from a finite field tol-tuples with components in {0, 1} where 0 and 1 are elements of the field itself. This permits one to study the algebraic complexity of a particular binary representation, i.e., the minimum number of additions and multiplications in the field needed to compute the binary representation. The two-way complexity of a binary representation is defined as the sum of the algebraic complexities of the binary representation and of its inverse mapping. Two particular binary representations are studied: the standard representation and the logarithmic representation. A method of surrogate computation is developed and used to deduce relationships between the algebraic complexities of certain functions. The standard representation of a finite field is shown to be among the two-way easiest representations of this field. In particular, the standard representation of a finite field with characteristicpis two-way easy wheneverp− 1 has only small prime factors. For any finite field having a two-way easy binary representation, the algebraic complexity in this field is shown to be essentially equivalent to Boolean circuit complexity. For any finite field, the Boolean circuit complexity of Zech's (or Jacobi's) logarithm is shown to be closely related to the Boolean circuit complexity of the discrete logarithm problem that is used in public-key cryptography. 相似文献
4.
This paper contains a review of the authors’ results in the theory of algorithm complexity. The results described concern
methods for obtaining lower bounds (containing almost all exponential lower bounds on monotone complexity of monotone functions),
synthesis of asymptotically optimal functional networks, minimization of Boolean functions, and the problem of solving Boolean
equations. 相似文献
5.
Usually, local search methods are considered to be slow. In our paper, we present a simulated annealing-based local search algorithm for the approximation of Boolean functions with a proven time complexity that behaves relatively fast on randomly generated functions. The functions are represented by disjunctive normal forms (DNFs). Given a set of m uniformly distributed positive and negative examples of length n generated by a target function F(x
1,...,x
n), where the DNF consists of conjunctions with at most literals only, the algorithm computes with high probability a hypothesis H of length m · such that the error is zero on all examples. Our algorithm can be implemented easily and we obtained a relatively high percentage of correct classifications on test examples that were not presented in the learning phase. For example, for randomly generated F with n = 64 variables and a training set of m = 16384 examples, the error on the same number of test examples was about 19% on positive and 29% on negative examples, respectively. The proven complexity bound provides the basis for further studies on the average case complexity. 相似文献
6.
Harold Abelson Andrzej Ehrenfeucht James Fickett Jan Mycielski 《Discrete Applied Mathematics》1982,4(1):1-10
We define two measures, γ and c, of complexity for Boolean functions. These measures are related to issues of functional decomposition which (for continuous functions) were studied by Arnol'd, Kolmogorov, Vitu?kin and others in connection with Hilbert's 13th Problem. This perspective was first applied to Boolean functions in [1]. Our complexity measures differ from those which were considered earlier [3, 5, 6, 9, 10] and which were used by Ehrenfeucht and others to demonstrate the great complexity of most decision procedures. In contrast to other measures, both γ and c (which range between 0 and 1) have a more combinatorial flavor and it is easy to show that both of them are close to 0 for literally all “meaningful” Boolean functions of many variables. It is not trivial to prove that there exist functions for which c is close to 1, and for γ the same question is still open. The same problem for all traditional measures of complexity is easily resolved by statistical considerations. 相似文献
7.
Upper complexity estimates are proved for implementation of Boolean functions by formulas in bases consisting of a finite number of continuous real functions and a continuum of constants. For some bases upper complexity estimates coincide with lower ones. 相似文献
8.
E. V. Djukova R. M. Sotnezov 《Computational Mathematics and Mathematical Physics》2012,52(10):1472-1481
The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form. 相似文献
9.
In this paper we study the neighbourhood of 15-variable Patterson-Wiedemann (PW) functions, i.e., the functions that differ by a small Hamming distance from the PW functions in terms of truth table representation. We exploit the idempotent structure of the PW functions and interpret them as Rotation Symmetric Boolean Functions (RSBFs). We present techniques to modify these RSBFs to introduce zeros in the Walsh spectra of the modified functions with minimum reduction in nonlinearity. Our technique demonstrates 15-variable balanced and 1-resilient functions with currently best known nonlinearities 16272 and 16264 respectively. In the process, we find functions for which the autocorrelation spectra and algebraic immunity parameters are best known till date. 相似文献
10.
Summary The paper describes the implementation of a globally convergent iterative algorithm for determining all the real zeros of certain classes of functions in any given interval. The algorithm is developed in terms of Ostrowski's square root formula and in the case of polynomials the relation with Laguerre's formula is obtained. A device is incorporated for overcoming the problem of numerical instability together with a number of associated devices for ensuring that no zeros have been missed. Application of the method is illustrated by two examples having clustered zeros. 相似文献
11.
Level structure of Zhegalkin polynomials,properties of test sets,and an annihilator search algorithm
K. N. Koryagin 《Computational Mathematics and Mathematical Physics》2010,50(7):1267-1273
Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin
polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding
all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology.
In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations.
Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm
makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does
not reduce the asymptotic complexity of solving systems of linear Boolean equations. 相似文献
12.
N. P. Red’kin 《Moscow University Mathematics Bulletin》2010,65(3):107-110
A method for obtaining new lower estimates for the implementation complexity of individual Boolean functions is presented
in the paper. The method is based on the transition from some considered basis to another one possessing already known good
lower estimates for the complexity of those functions. The effective use of this method is illustrated by the example of obtaining
the asymptotic value for the implementation complexity of threshold functions by self-correcting circuits composed of multiple-input
elements. 相似文献
13.
V. V. Zhukov 《Moscow University Computational Mathematics and Cybernetics》2017,41(3):134-141
A model of limited-depth recursive schemes for the functions of Boolean algebra (Boolean functions), constructed from multi-output functional elements, is considered. A lower estimate of the Shannon function for the complexity of schemes of this class is derived. Upper estimates for the complexity of some specific functions and systems of functions in this class of schemes are obtained. A method is proposed for synthesizing schemes of this class for arbitrary functions that allow us (using the derived lower estimate) to determine the asymptotics of the Shannon function for their complexity. 相似文献
14.
Andre Gronemeier 《Discrete Applied Mathematics》2007,155(2):194-209
In learning theory and genetic programming, OBDDs are used to represent approximations of Boolean functions. This motivates the investigation of the OBDD complexity of approximating Boolean functions with respect to given distributions on the inputs. We present a new type of reduction for one-round communication problems that is suitable for approximations. Using this new type of reduction, we improve a known lower bound on the size of OBDD approximations of the hidden weighted bit function for uniformly distributed inputs to an asymptotically tight bound and prove new results about OBDD approximations of integer multiplication and squaring for uniformly distributed inputs. 相似文献
15.
D. V. Trushchin 《Moscow University Mathematics Bulletin》2009,64(2):87-90
A problem of realization of Boolean functions by α-formulas is considered. These formulas are such that each subformula contains not more than one nontrivial principal subformula. The depth is considered as a complexity measure of a formula. Upper and lower polynomial estimates of Shannon functions for α-completions of finite systems of Boolean functions are obtained. 相似文献
16.
The notions of binary string and binary symmetric function are introduced and basic results presented. Boolean algorithms are given for binary addition and multiplication. An analysis of the redundancies involved is straightforward. The examination of carry propagation which arises in the Boolean analysis of functions may lead to a new interpretation of the notion of computational complexity. 相似文献
17.
The knapsack problem with Boolean variables and a single constraint is considered. Combinatorial formulas for calculating and estimating the cardinality of the set of feasible solutions and the values of the functional in various cases depending on given parameters of the problem are derived. The coefficients of the objective function and of the constraint vector and the knapsack size are used as parameters. The baseline technique is the classical method of generating functions. The results obtained can be used to estimate the complexity of enumeration and decomposition methods for solving the problem and can also be used as auxiliary procedures in developing such methods. 相似文献
18.
The article considers the problem of constructing a conditional diagnostic test (the exact identification problem) on the
set of all read-once functions essentially dependent on the specified variables in an arbitrary hereditary basis. We use standard
queries on function values at points and also parity queries on the number of ones in subfunctions obtained by substituting
constants for variables (subcube parity queries return the modulo-2 sum of the function values on a subcube of the Boolean
cube). For the elementary basis consisting of conjunction, disjunction, and negation, we prove the existence of a conditional
diagnostic test with a quadratic (in the number of variables) number of queries. For bases that allow read-once expression
of all elementary-basis functions (containing at least one nonmonotone and at least one nonlinear function) and are essentially
different from the elementary basis, we prove the necessity of using an exponential (in the number of variables) number of
queries in the worst case. Our analysis thus establishes the boundary between polynomial and exponential complexity problems. 相似文献
19.
We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity
of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of
a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number
of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients
of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial
of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing
the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower
bound in Bach [1]. 相似文献
20.
Sugata Gangopadhyay 《Discrete Mathematics》2006,306(14):1540-1556
In 1983, Patterson and Wiedemann constructed Boolean functions on n=15 input variables having nonlinearity strictly greater than 2n-1-2(n-1)/2. Construction of Boolean functions on odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for n=15,21. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all GF(2)-linear transformations of GF(2ab) which acts on PG(2,2a). 相似文献