Related Experiment Video
Updated: Nov 10, 2025
09:27
Using Eye Movements Recorded in the Visual World Paradigm to Explore the Online Processing of Spoken Language
Published on: October 13, 2018
10.4K
A Structural Entropy Measurement Principle of Propositional Formulas in Conjunctive Normal Form
Zaijun Zhang1,2, Daoyun Xu1, Jincheng Zhou2
1College of Computer Science and Technology, Guizhou University, Guiyang 550025, China.
Entropy (Basel, Switzerland)
|April 3, 2021
Summary
Structural entropy quantifies formula complexity in the satisfiability (SAT) problem. Lower entropy indicates harder problems, and this study proposes an approximation strategy and improves SAT solver performance.
Area of Science:
- Computer Science
- Artificial Intelligence
- Computational Complexity
Background:
- The satisfiability (SAT) problem is fundamental in computer science, with varying solver performance attributed to formula structure.
- Industrial SAT instances are generally easier for solvers than random instances, suggesting structural differences are key.
- Understanding these structural properties is crucial for advancing SAT solving capabilities.
Purpose of the Study:
- To investigate the structural properties of propositional formulas in conjunctive normal form (CNF) using structural entropy.
- To establish a relationship between a formula's structural entropy and its solving difficulty.
- To develop methods for approximating structural entropy and enhancing SAT solver performance.
Main Methods:
- Utilized structural entropy to measure the complexity of SAT formulas.
- Developed a λ-approximation strategy for estimating the structural entropy of large formulas.
- Analyzed variable selection and flipping probabilities in local search SAT solvers based on structural properties.
Main Results:
- A formula's structural entropy correlates with its solving difficulty; lower entropy implies greater difficulty.
- The λ-approximation strategy accurately estimates structural entropy with over 92% approximation ratio.
- Local search SAT solvers exhibit community-based variable selection, influenced by variable structural entropy.
Conclusions:
- Structural entropy provides a valuable metric for understanding SAT problem complexity.
- The proposed approximation strategy offers an efficient way to assess large formula structures.
- A novel initial candidate solution generation strategy, informed by structural analysis, significantly boosts SAT solver performance.
Related Concept Videos
02:39Entropy
32.8K
Salt particles that have dissolved in water never spontaneously come back together in solution to reform solid particles. Moreover, a gas that has expanded in a vacuum remains dispersed and never spontaneously reassembles. The unidirectional nature of these phenomena is the result of a thermodynamic state function called entropy (S). Entropy is the measure of the extent to which the energy is dispersed throughout a system, or in other words, it is proportional to the degree of disorder of a...
32.8K
01:18Entropy
3.1K
The first law of thermodynamics is quantitatively formulated via an equation relating the internal energy of a system, the heat exchanged by it, and the work done on it. A quantitative formulation of the second law of thermodynamics leads to defining a state function, the entropy.
When an ideal gas expands isothermally, the disorder in the gas increases. From the molecular perspective, the gas molecules have more volume to move around in.
Consider an infinitesimal step in the expansion, which...
When an ideal gas expands isothermally, the disorder in the gas increases. From the molecular perspective, the gas molecules have more volume to move around in.
Consider an infinitesimal step in the expansion, which...
3.1K
02:38Third Law of Thermodynamics
20.6K
A pure, perfectly crystalline solid possessing no kinetic energy (that is, at a temperature of absolute zero, 0 K) may be described by a single microstate, as its purity, perfect crystallinity,and complete lack of motion means there is but one possible location for each identical atom or molecule comprising the crystal (W = 1). According to the Boltzmann equation, the entropy of this system is zero.
20.6K
01:20Entropy and the Second Law of Thermodynamics
3.6K
The second law of thermodynamics can be stated quantitatively using the concept of entropy. Entropy is the measure of disorder of the system.
The relation between entropy and disorder can be illustrated with the example of the phase change of ice to water. In ice, the molecules are located at specific sites giving a solid state, whereas, in a liquid form, these molecules are much freer to move. The molecular arrangement has therefore become more randomized. Although the change in average...
The relation between entropy and disorder can be illustrated with the example of the phase change of ice to water. In ice, the molecules are located at specific sites giving a solid state, whereas, in a liquid form, these molecules are much freer to move. The molecular arrangement has therefore become more randomized. Although the change in average...
3.6K
01:26Constraints and Statical Determinacy
809
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
809
02:49Second Law of Thermodynamics
25.5K
In the quest to identify a property that may reliably predict the spontaneity of a process, a promising candidate has been identified: entropy. Processes that involve an increase in entropy of the system (ΔS > 0) are very often spontaneous; however, examples to the contrary are plentiful. By expanding consideration of entropy changes to include the surroundings, a significant conclusion regarding the relation between this property and spontaneity may be reached. In thermodynamic models, the...
25.5K