On the basis of the positional notation it is proved, that classes P and NP coincide, the software (SW) which practically allows to solve problems from class NP, but with the difficulties inherent already in class P is created. But class NP covers very big circle of problems of discrete mathematics and computer science: from the problems of designing of electronic devices, their optimization and verification and up to game problems; problems of logic, a logic conclusion, graph's, mathematical programming, algebra, the theory of numbers, coding etc.
The problem from set forth above areas without dependence from the origin for the decision with the help of the SW should be submitted as CNF (a conjunctive normal form). Told means that variables X_1, X_2, X_3, …, X_n are binary. From k literals (where k - the whole positive variable between 1 and n) these variables (the literal is a variable or its denying) is under construction disjunctive. One disjunkt is one line of the table. Such disjunkts are under construction m pieces (means in the table are present m lines). It is meant that all disjunkts are connected conjunctive.
So the formulated problem carries the name SATISFIABILITY (SAT).
If there is a set for variables which at substitution in this tabulared form gives 1 it refers to satisfiability, on the contrary - a SAT-problem is unsatisfiability.
It is known that SAT-problem is NP-complete (for check of satisfiability it can be demanded to touch 2 in a degree n sets and to check up everyone on the given table).
SW allows to solve such problem for polynomial time as problem of SAT, i.e. to distinguish its discrepancy or to give out carrying out set in case of its presence.
However with growth of dimension of a problem even ours polynomial algorithm demands a lot of time. The magnificent output from such collision is here again found. It is superreduction.
SW carries out superreduction, i.e. such equivalent transformation of the table at which if SAT-problem is inconsistent - its text degenerates (roughly - the text turns to one empty line) and if it is satisfiability - carrying out set is taken for linear time from dimension of the table.
Means, SW represents new technology of processing of texts of problems which essence - optimum process of changes of structure their contents, i.e. removal from these texts that is not the carrier of the fundamental information.
From told follows that SW should be used already at a stage of statement of SAT-problem for performance of superreduction. At such approach we shall not receive òðóäíîðåøàåìûå a hard-decision problem. Allegorically speaking - a hard-decision problem is a result of unreasonable statement or result of unguided complication.
Reasonable activity demands such approach.
Any complex device consists of parts (units, blocks, modules, …) and for these parts it is necessary to put and superreduction its logic circuit, and then from the supergiven parts to receive the incorporated block above which and to carry out final superreduction.
Simple example. We admit the electronic device consisting of three blocks is designed, each of which contains 50 elements and is connected to the subsequent by means of three general elements. We shall present the given device in a logic kind in the form of SAT-problem.
A SAT-problem consists of following three blocks (CNF) with variables: I the block from 0 up to 49; II block from 47 up to 96; III block from 94 up to 143 (i.e. overlapping is taken into account). In the first and third blocks till 215 lines, in the second 214 lines. A general problem which turns out, has 144 variables and 644 lines.
Superreduction of the general problem (144 variable / 644 lines)
is carried out for 6 mines 45
seconds (Pentium-866). However superreduction of everyone separate
I, II and III blocks accordingly make: 5, 6 and 3 ñåê. Superreduction
final CNF, consisting of three already supergiven blocks,
makes 22 sec. Time for procedure of reduction of four CNF (three
initial and by one general) 36 sec in total is spent and final supergiven
CNF
has 144 variables and 281 line (compare with original: 144 variables and
644 lines).
The full text of the described example is here.
What result of application of superreduction? 1) The size of original CNF was reduced more than in 2 times, so also the size of the most electronic device is reduced. Thus carrying out sets have not changed, i.e. the design plan of the device has not changed. 2) 2) As a result of the executed re-structuring carrying out sets will work in process of receipt of inquiry about them, i.e. time of processing of single or preparatory calculations what would take a place in original variant is completely excluded. And it already will give a repeated gain of speed of work in comparison with original variant.
In end we shall note that the described approach completely issued by the end of the second millenium has no analogue in the world theory and practice. For such conclusion there are all bases: till now the various researchers engaged in SAT-problem publish the examples of so-called criteria (benchmarks) in which there are thousand variables and tens thousand disjunctions or even tens thousand variables and hundred thousand disjunctions for interested persons to try the forces in recognition of satisfiability. Here again approaches for last twenty years essentially have not changed in comparison with that was present on start of the Japanese project of the COMPUTER of the fifth generation (see [8], [9], [15]). Now it is possible to have hopes that in the third millenium a problematics essentially will change.