homomorphism_problem (282B)
1 # Homomorphism problem 2 3 The [decision_problem], given two [relational_structures] G and H, of deciding whether there is a [homomorphism] from G to H 4 5 This is in [NP], and [NP_hard] even if H is a fixed graph 6 - e.g., can code [k_colorability] 7 8 Up: [decision_problem], [homomorphism]