ABSTRACT

The concept of computability is defined more exactly and illustrated as an example of Boolean functions and cryptanalysis. To define a Boolean function is not necessary to record its formula. To do that the reduced (compact) description of values is determined in the truth table or in the statement of the problem. We obtain estimates of computation time, the volume of a compact descriptions and the range of variables under which it takes the value 0 or 1, depending polynomially on the number of arguments.

1. Introduction

The universal model of computation will be proposed in the article, which essence firstly is explained at first on the example of Boolean functions and the calculation of the range of variables values, under which it takes the value 0 or 1 (specifying the area satisfiability—SAS). Then conclusions about the possibility of the solution of the problem of cryptanalysis are done.

The values of a Boolean function can be considered as 0 or 1 with a convex neighborhood, painted in different colors (0—is white, 1—is black—two sets of convex disconnected components). Definition of a Boolean function can be reduced to the separation of values equal to 0, the values are equal to 1 in the Boolean n-dimensional space (this requires the construction of the table containing the rows or a logical formula which length is proportional to a polynomial). We can assume that the Boolean space is a subset of real n-dimensional unit hypercube. In the research [1] we obtained polynomial appraisals for the separability of infinite bounded sets that are valid for our particular case too.

All necessary theorems were formulated in [2].

2. Boolean Functions

Boolean functions are given by the truth table on which the formula is built. Instead of the formula a compact description of the binary feature space (Table 1) is proposed to use. As in the case of the formulas, the truth table is unnecessary.

A formal proof of the theorem is based on estimates obtained in [1], and involves finding a Boolean function that separates the two classes of white and black points. Unlike the standard approach the ordering of space with the lexicographic order, or a binary tree are used.

The sequence of relationships can be defined by a binary tree, the number of coordinates and its value is situated in its nodes. The true value corresponds to one branch, while the false correspond to the other. The leaves have the function value (the number of class 0 or 1). This is so-called compact description (Figure 1) of the functions specified. Function identically equal to 0 or 1, determines the root of the tree.

In essence, a compact description of the function specifies a set of domains of different functions (similar to each other) in which they take the values 0 or 1.

Table 1. The truth table on which the formula is built.

Similar to each other functions differ only in the truth table rows with identical values of the function, and they are described by a single tree (domain).

The advantage of a compact description is the lack of dummy variables. Dummy variable if the function does not depend on it, means the presence of the values 0, 0 or 1, 1 in the leaves of a node. You can remove this node to leaf 0 or 1, respectively, or vice versa add to perform logical operations and bring to a tree topology. Identical functions with dummy variables, defined in such tree, are included in a class of similar functions.

The value of one coordinate n-dimensional Boolean space divides the Boolean space or a truth table into two parts (each of them, if possible, is divided into two, etc.).

Theorem 1. To define a class of similar Boolean functions of the n-arguments it is sufficient to determine the values of these functions on a sequence consisting of the  argument values which are located in internal nodes (non-leaf nodes) of a binary tree.

Proof. Any Boolean function is uniquely defined in the n-dimensional Boolean space with the corresponding coloring. For the separability of the two bounded sets in the real n-space the following maximum estimate of the number of partitions were obtained [1]:

Separability is possible with a positive distance between two bounded sets A and B:

is chosen arbitrarily. Changes in the in the neighborhood of 0 have little effect on the number M. For a Boolean space with a finite set of elements we choose.

—the maximum number of surfaces for the separation of the two sets. The upper limit was obtained for a “overlapping sets” (water and sand does not exist in the Boolean space), with a value. For a Boolean space the value is, so the maximum should be divided into,. Finally, we obtain

QED Assertion 1. To define a class of similar Boolean functions of the n-arguments is sufficient to determine the values of these functions on a full tree with a single relation, all n of these internal nodes, except the last, have a leaf.

In support of this assertion the fact is evidenced that for n divisions of the truth table, we clearly identify a single line of it. The principle of dividing the feature space is maintained at each step of the algorithm of the second type, which is uniquely defined by at least one class (Theorem 3 [1,2]).

Any function supposes the free order of the arguments and is proposed by topology of the tree. All others keep some order of the arguments, and to work with such trees is not easy.

As the relationship, the truth that you want to check— the equality of the argument, the value is 1. Such tree can be leveled at the introduction of the branch with true relationship inequality to 1, which increases the number of used relations.

An alternative way of defining relationships—is equality or inequality of the arguments to each other. We can add or not add the ratio equals 0 or 1. In such case, the four relations are used. For example, the ratio can be rewritten in any option in the binary and/or unary, including this one , which allows not to indicate the number of the first argument (determined by the place).

Logical formulas are written in the truth table. Before it appears, the problem must be determined on a content level. It is possible to bypass the step of creating a truth table and go to the task of the logical functions of the meaningful statement of problem. You can define as many coordinate relations as necessary in the statement of problem, in which the hierarchy may be present, and you can choose a tree that will fit it. The transition from one representation to another (rebuilding the tree) will not cause algorithmic difficulties.

The theorem and the assertion exist because of the truth of Theorem 3 in [1,2]. We choose the best result— an assertion 1.

The total length of the stored data to a Boolean function in bits (L) consists of values, the number of leafs of a binary tree (you cannot assume the last leaf, its value is opposite to the next leaf, if the tree has no dummy variables –, the number of required number of coordinates (the length of the coordinate numbers—)..

There is also the first and the third type of algorithms.

For the first type of algorithms:

The function reaches a maximum at a value. Then to the Boolean function it is necessary to determine the values  of the following number:.

We can expect that with the transition from finite to infinite sets the lower bound will be too high, as in the case with the assessment

The upper limit is determined by the principle of its operation in the Boolean space for the worst case. One of the coordinates is divided by half-and-half, for the remaining two halves the bisection of the other coordinate takes place, etc. (In accordance with this algorithm and the second approach, we can talk about the balanced tree with the depth n).

You can also define the upper limit for the third type of algorithms. After the division of space in the cell is uniquely determined the membership of each cube 0 or 1. But we keep a minimal description of the two. The worst case is obtained in case of equality, and the best one—for one cube.

In contrast to the algorithms of the second type, the first and third do not need to store the number of coordinates (determined by the place), so a series of relationships are defined by the ratio of the lexicographic order. The total length of the bit sequence is –.

3. Area of the Satisfiability and the Computation Time

Theorem 2. For one class of similar Boolean functions of the n arguments there is an area of satisfiability (SAS) or its negation, defined on nothing more than the argument values.

Proof. Formally, to solve the satisfiability problem it is necessary to index binary tree (back to the reduced table description), which contains values, to define belonging for each index to a class 0 or 1, and calculate the number for each class. In the future we use the minimal description. Example: Suppose class 1 (0) has the smallest number of indices (we have defined its minimal description), then any point of the Boolean space, either gets into this area, and then the value will be equal to 1 (0) or does not get, and the value will be 0 (1). For each index, you must extend the definition of value. It becomes apparent total number of QED.

In the area of the satisfiability there are two approaches to the above listed algorithms or without them.

In the first approach for each of the new values, if possible, the first algorithm should be used to the already calculated values (like the second, it allows us to solve optimization problems). And then the third algorithm determines a minimal description of the area of satisfiability or its negation. Its lack is using of the truth table as initial data. The advantage is the index is sorted, by using the algorithms of the first type—the computation time of the logical functions.

The second approach does not have this lack, the tree, built on the meaningful statement of problem, and does not require the mentioned types of algorithms. We have a complete binary tree with n leaves and n internal nodes. They define the complexity of the problem while writing out the coordinates on all paths from the root to 0 or 1, depending on what is less. After determining a way, all non-listed coordinates are varying from 0 to 1. The complexity of the problem is (the second proof of Theorem 2). After sorting such table computing time of logical functions is –.

Without specifying the area of satisfiability the computation time of the logical function is.

4. Model of Computation

From the separability of bounded sets the obvious mathematical statement implies.

Assertion [2, p. 1800]. Any finite many-valued real piecewise-continuous function can be approximated by a step function at least to accuracy.

A more precise formulation describing the approximating function is given in [2].

Finite function is defined for a bounded area of space, and hence has a finite number of jump discontinuities, infinite discontinuities (only one of the two one-sided limits exists or is infinite), there it has finite values. It can be normalized to a unit hypercube, which allows not only to give a comparative estimate of the number of steps (for which the normalization is not important), but also for different functions.

Thus, we know exactly what to do when solving any problem, namely, to build from the assertion,  in the future simply separating the two classes, and the solutions and non-solutions, possibly consisting of a single point and we can estimate its complexity by the number of steps (or move it the next phase “how”).

The question how to do that is being discussed [1]. Alternative approaches—[3,4]. In the first approach we prove the existence of three types of computational learning algorithms, one of which requires a memory polynomially depending on the dimension of space. The memory is filled once with a fixed number of operations, and then the time is also polynomially. All this proves the following theorem.

The theorem of computability. Every is computable by a universal computing device, with a given accuracy in n-dimensional infinite bounded real space. The complexity of computation (memory and time) depends on its dimensions polynomially.

This statement is well suited for human-robot (like a computer), analog computations (analog computers, quantum computers), analog signal processing, analog electronics, neural networks, control theory built on differential equations and continuous dynamical systems [5, 6].

The real space is not a limitation. An ordered alphabet can be viewed as a number line. The words in the alphabet—are the n-dimensional space. Moreover, we can calculate the distance to the character, not only on the real line, but also in the n-dimensional space for the written, spoken…

This approach effectively overrides the prior use of the term fuzziness, replacing it by the difference between the actual position and the boundary described in the memory (between objects or the object itself), which is continuously changing in time, on the real line or in a n-dimensional space.

For cryptosystems, after normalization of the space to the unit hypercube (interval), where the K is the length of the key (one-dimensional space).

The revised approach to the computability was illustrated by the logic functions and cryptosystems. Regarding the latter, the futility of any development of algorithms became clear.

5. Conclusions

1) a) It is no place for intuitions in more precise theorem of computability.

b) The process of finding a suitable algorithm is quite formal and can be performed automatically. Its ease of use for Boolean functions and cryptanalysis justify its use in other subject areas.

2) For Boolean functions is to choose the one of two variants.

a) With the area of satisfiability storing the value , with the computation time calculating the logical function. SAS problem is trivial, since it is already solved.

b) Keeping only the binary tree with nodes which is able to participate in logical operations. The computation time is. The problem of SAS is .

3) If you wish you can generate a truth table by compact description but it is not necessary.

4) Lukasiewicz three-valued logic does not change anything in the proposed theory, making the description more natural and understandable. For the cybernetic systems the four-value logic with the addition of uncertain value can be used. You can increase the n-value with the degree of similarity to 0, 1, indefinitely, or go to the real interval [0, 1] (blurring makes it possible to use a 5th point of conclusion).

5) Using the proposed theory, we can estimate the speed, acceleration, the degree of approximation to the solution, non-solution, or a state of uncertainty, and make the appropriate changes to the space features.

REFERENCES