4clique_hypothesis (455B)
1 # 4-clique hypothesis 2 3 [bringmann2022unbalanced] Definition 2.5: you cannot determine in O(n^3) whether a [graph] contains a [4_clique] (the [clique_problem] for [4_cliques]) 4 5 also in [gutenberg2020new] and in [carmeli2019enumeration] 6 7 this is a special case of the [k_clique_hypothesis] from [lincoln2020tight] 8 9 Up: [computational_hypothesis], [4_clique] 10 11 See also: [hyperclique_hypothesis], [triangle_detection_conjecture] 12 13 Aliases: 4 clique hypothesis