Published by the Department of Computer Science, The University of Chicago.
Prague, Czech Republic
alexak AT atrey DOT karlin DOT mff DOT cuni DOT cz
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.
Submitted October 30, 2011, revised July 31, 2012 and July 14, 2013; published July 18, 2013.