. . "11320" . . "http://cjtcs.cs.uchicago.edu/" . "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."@en . . . "extension; homomorphism; Complexity"@en . "09" . . "Chicago Journal of Theoretical Computer Science" . . "1073-0486" . . "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." . "Complexity of the homomorphism extension problem in random case" . . "RIV/00216208:11320/13:10174144!RIV14-GA0-11320___" . "Complexity of the homomorphism extension problem in random case" . "1"^^ . . "Complexity of the homomorphism extension problem in random case"@en . "10.4086/cjtcs.2013.009" . "1"^^ . "Kazda, Alexandr" . . "66487" . "Complexity of the homomorphism extension problem in random case"@en . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . "P(GA13-01832S), S" . . "[1F6732A199DD]" . . "6"^^ . "RIV/00216208:11320/13:10174144" . . . .