Homomorphieproblem

Das Problem H-Hom fragt:

• Eingabe: Endliche Struktur $G$ und Struktur $H$.
• Frage: Gibt es einen Homomorphismus von $G$ nach $H$?
  Beispiel: Ein Graph $G$ ist genau dann 3-färbbar, wenn es einen Homomorphismus von $G$ in den vollständigen Graphen $K_3$ (ein Dreieck) gibt.