{'fraction_non_alphanumeric': 0.02346805736636245, 'fraction_numerical': 0.003259452411994785, 'mean_word_length': 4.99609375, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generating Hard but Solvable SAT Formulas

The 3-SAT problem is one of the well-known NP-hard problems that have been extensively studied over the years. Its generalisation, the k-SAT problem, is NP-complete for k > 2. In addition to being interesting from a theoretical viewpoint, 3-SAT also plays a role in industrial applications, such as boolean circuit verification. It is therefore of special interest to develop efficient solvers for reasonable problem sizes. Although 3-SAT is NP-hard in general and all known algorithms for solving it require an exponential runtime in the worst case, it was recently observed that the performance of current state-of-the-art solvers over an ensemble of problem instances (determined by the range of different parameters, such as the ratio of clauses to variables) does not behave uniformly, but changes suddenly at critical parameter values. This sudden change in typical problem difficulty behaves similarly to an effect that is known from physics as phase transition. In order to understand changes in runtime performance that are connected to the structure of the underlying problem, models from physics provided useful information. This seminar paper considers several recent publications that consider the application of spin-glass models to the generation of hard instances for the 3SAT problem. The foundation on a structural model such as spin-glass models, which are well-known from physics, allows the analysis of the hardness of the problem from a statistical mechanics viewpoint.