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

Abstract

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.

• The article: PDF (177 KB)
• Source material: ZIP (77 KB)
• BibTeX entry for this article (256 bytes)

Submitted October 30, 2011, revised July 31, 2012 and July 14, 2013; published July 18, 2013.

© 2013 Alexandr Kazda
Licensed under a Creative Commons Attribution License

Article 8

Article 10

Volume 2013

Published articles