{'fraction_non_alphanumeric': 0.01794453507340946, 'fraction_numerical': 0.0, 'mean_word_length': 4.847619047619047, '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}}
Some NP-Complete Problems Similar to Graph Isomorphism

The GRAPH ISOMORPHISM problem has so far resisted attempts at determining its complexity status—it has not been shown to be NP-complete nor in P. In this paper several altered or generalized versions of the ISOMORPHISM problem are presented and shown to be NP-complete. One of these is the problem of determining whether a given graph has a fixed-point-free automorphism. Some speculation is made on the possible implications of these results on deciding the complexity status of ISOMORPHISM. Various classes and hierarchies of problems in NP are discussed.