Volume 2013

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

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)