Chicago Journal of Theoretical Computer Science

Volume 2013

Article 9

Published by the Department of Computer Science, The University of Chicago.

Complexity of the homomorphism extension problem in the random case

Alexandr Kazda
Charles University
Prague, Czech Republic
alexak AT atrey DOT karlin DOT mff DOT cuni DOT cz

July 18, 2013


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.

DOI: 10.4086/cjtcs.2013.009

[] Article 8 [] Article 10
[back] Volume 2013 [back] Published articles
[CJCTS home]