Related Experiment Video
Updated: Jul 13, 2026
11:09
RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
Published on: July 17, 2021
Phase diagram of the 1-in-3 satisfiability problem
Jack Raymond1, Andrea Sportiello, Lenka Zdeborová
1NCRG, Aston University, Aston Triangle, Birmingham B4 7EJ, United Kingdom.
Summary
This study explores the 1-in-3 satisfiability problem, revealing a transition from easily solvable to computationally hard instances. Findings aid in understanding the phase diagram of Boolean satisfiability problems.
Area of Science:
- Computational Complexity
- Statistical Physics
- Discrete Mathematics
Background:
- The 1-in-3 satisfiability problem is a variant of the Boolean satisfiability problem where each clause must be satisfied by exactly one literal.
- Understanding the phase transitions in random Boolean satisfiability problems is crucial for theoretical computer science and artificial intelligence.
Purpose of the Study:
- To investigate the typical case properties of an enlarged random ensemble for the 1-in-3 satisfiability problem.
- To map the phase diagram, identifying regions of polynomial-time solvability and computational hardness.
- To analyze the transition between satisfiable and unsatisfiable phases.
Main Methods:
- Development of an enlarged random ensemble parametrized by average connectivity and negation probability.
- Derivation of rigorous results in the computationally tractable region.
- Application of a one-step replica-symmetry-breaking cavity analysis for the hard region.
Main Results:
- Identification of a transition point where the problem shifts from being typically satisfiable in polynomial time to becoming computationally hard.
- Characterization of the phase diagram, including the boundary between satisfiable and unsatisfiable instances.
- Insights into the structural properties of the problem ensemble.
Conclusions:
- The study provides a comprehensive analysis of the 1-in-3 satisfiability problem's complexity landscape.
- Cavity method results offer predictions for phase transitions and problem structure.
- This research contributes to the understanding of hard problems in computational complexity theory.
Related Concept Videos
01:28Phase Diagrams of Ternary Systems
Consider a ternary system, which is composed of three components: water (W), ethanoic acid (E), and trichloromethane (T). Here, Ethanoic acid (E) is fully miscible with both water (W) and trichloromethane (T), meaning it can mix entirely with either of them. However, water and trichloromethane have partial miscibility, meaning they can only mix to a certain extent, beyond which two separate phases will form.The phase diagram of a ternary system is represented as an equilateral triangle, where...
01:19Phase Diagram
The phase of a given substance depends on the pressure and temperature. Thus, plots of pressure versus temperature showing the phase in each region provide considerable insights into the thermal properties of substances. Such plots are known as phase diagrams. For instance, in the phase diagram for water (Figure 1), the solid curve boundaries between the phases indicate phase transitions (i.e., temperatures and pressures at which the phases coexist).
01:24Phase Diagram
A phase diagram is a graphical representation of the physical states of a substance under different conditions of temperature and pressure. It shows the boundaries between solid, liquid, and gas phases and the conditions at which these phases coexist in equilibrium. An area in a phase diagram represents a single phase, whereas lines or phase boundaries represent the equilibrium between two phases.In the phase diagram of water, the boundary line between the solid and liquid states illustrates...
01:24Solid–Solid Solutions
The temperature-composition phase diagram of two solids, A and B, which are immiscible in the solid phase but form miscible liquids, shows that when the temperature is low, these two exist as separate, pure solids (A and B). As the temperature increases, they transition into a single-phase liquid solution where A and B coexist. Moving from point a1 to a2 in the phase diagram, the composition changes such that solid B begins to separate from the solution, enriching the remaining liquid with A.
01:07Ladder Diagrams: Complexation Equilibria
Ladder diagrams are useful for evaluating equilibria involving metal-ligand complexes. The vertical scale of the ladder diagram represents the concentration of unreacted or free ligand, pL. The horizontal lines on the scale depict the log of stepwise formation constants for metal-ligand complexes and indicate the dominant species in all the regions.
The formation constant, K1, for the formation of Cd(NH3)2+ complex from cadmium and ammonia is 3.55 × 102. Log K1 (i.e. pNH3) is 2.55, and...
The formation constant, K1, for the formation of Cd(NH3)2+ complex from cadmium and ammonia is 3.55 × 102. Log K1 (i.e. pNH3) is 2.55, and...
02:39Phase Diagrams
A phase diagram combines plots of pressure versus temperature for the liquid-gas, solid-liquid, and solid-gas phase-transition equilibria of a substance. These diagrams indicate the physical states that exist under specific conditions of pressure and temperature and also provide the pressure dependence of the phase-transition temperatures (melting points, sublimation points, boiling points). Regions or areas labeled solid, liquid, and gas represent single phases, while lines or curves represent...