{'fraction_non_alphanumeric': 0.051560379918588875, 'fraction_numerical': 0.0067842605156037995, 'mean_word_length': 4.857142857142857, '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}}
Csc5160: Combinatorial Optimization and Approximation Algorithms Topic: Introduction to Np-complete Problems

This lecture gives a general introduction of P, NP and NP-complete problems. We will study the definition and some classic examples of NP-complete problems (e.g. SAT, 3-SAT, Vertex Cover). More importantly, we will learn how to show that a problem is not easier than another problem by polynomial-time reduction. Polynomial-time reduction is the general method to prove that a new problem is NP-complete, so that we have an excuse not to find the optimal solution...As we encounter more NP-complete problems, we will learn some general techniques for reductions (e.g. “restriction”, “local replacement” and “component design”).