Optimization of subexponential complexity algorithm for SAT problem solution
Journal Title: Інформаційно-керуючі системи на залізничному транспорті - Year 2018, Vol 23, Issue 3
Abstract
During the modernization and creation of modern control systems on railway transport, new modern optoelectronic analogues of electromagnetic relays are being created. When constructing them, it becomes necessary to model the interaction of nodes. To this end, Boolean functions of algebra-logic are constructed, which can be of a high degree of complexity and contain a large number of clauses. Further, there arises the need to solve the Boolean satisfiability problem in real time (SAT task), and in the case of the feasibility of the task it is additionally necessary to specify all the sets of variables for which it is true. The algorithms described in the literature at the present time have an exponential dependence of complexity on the number of changes and complexity of the function, and accordingly the execution time increases exponentially with the complexity of the function. In this paper, a subexponential complexity algorithm for the SAT task, which determines whether a function is feasible is proposed, and also a procedure that allows you to enumerate all sets of variables under which the Boolean function being analyzed can be realized for subexponential time. This makes it possible to achieve a significant gain in time with Boolean functions with a large number of changes and clauses.
Authors and Affiliations
A. Boinik, V. Butenko, O. Golovko, M. Ushakov
Keywords
Related Articles
- EP ID EP498408
- DOI 10.18664/ikszt.v0i3.140329
- Views 144
- Downloads 0
Estimated complex for assessing the efficiency of using resource-saving technologies for cleaning diesel and diesel locomotive systems
The necessity of redirecting enterprises of locomotive economy to increase economic efficiency due to the transition to market conditions of management, which should be based on the new system concept of resource saving,...
Analysis of the features of models of optical transport networks
Features of construction of models of optical transport networks are considered. It is noted that the models have common features: a hierarchical level structure, where each level has an independent set of functions, whi...
Investigation of electromagnetic transients in a frequency controlled electric drive of switching devices of traction substation transformers
The study proposes the boundary conditions for selecting the capacitance of the converter to ensure the exclusion of the mode of self-oscillation and dangerous overvoltages in controlling the frequency of rotation of the...
Research of the possibility of using neural networks in the tests of locomotive hydraulic transmissions
The possibility of developing a self-diagnostics system of the diesel locomotives hydraulic transmissions information-measuring test system is researched. The use of neural networks and fuzzy logic for the development of...
The main advantages of separable programming for multidimensional problems
An essential component of innovative technologies in the theory of information measuring systems (IMS) and in their computer-aided design systems should be the result of solving problems of improving efficiency, optimizi...