wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

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]