Complexity of the homomorphism extension problem in random case

Abstrakt

We prove that if A is a large random relational structure ( with at least one relation of arity at least 2) then the homomorphism extension problem EXT (A) is almost surely NP-complete.

Klíčová slova

• Complexity
• homomorphism
• extension