Complexity of the homomorphism extension problem in the random case
arXiv:1106.0663
Abstract
We prove that if A is a large random relational structure with at least one relation of arity at least 2 then the problem EXT(A) is almost surely NP-complete.
8 pages