{'fraction_non_alphanumeric': 0.022525597269624574, 'fraction_numerical': 0.0020477815699658703, 'mean_word_length': 4.983673469387755, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, '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}}
Exponential Time Complexity of SAT and Related Problems

Our results are contributions to the exponential time complexity of NP-hard problems. We consider in particular the exponential time complexity of the Boolean Satisfiability problem (SAT) and variants of it. To study the exponential time complexity of a problem, we fix a parameter of the problem: The number of variables n for SAT. We are interested in the constant c in the exponential factor 2 of a time bound of an algorithm for SAT. The smallest such constant captures the exponential time complexity of SAT. Our results: (1) There is a problem that has higher exponential time complexity than SAT and comparable problems, assuming the Exponential Time Hypothesis (ETH). This problem is the Constraint Satisfaction Problem (CSP). The reason is a dependency of the complexity of CSP on the number of values a variable can take. (2) Approximate counting of satisfying assignments has exactly the same exponential time complexity as finding a satisfying assignment. In the proof of this theorem we analyze a concrete algorithm for approximate counting. A similar algorithm, for which no mathematical analysis of the approximation guarantee was known, has been already successful in practice. These results are meant to improve our understanding of the exponential time complexity of NP-hard problems. Besides the mentioned results, the main contributions of this work, we discuss a couple of other results.