Complexity of the homomorphism extension problem in the random case
classification
🧮 math.CO
keywords
leastproblemrandomalmostaritycasecomplexityextension
read the original abstract
We prove that if A is a large random relational structure with at least one relation of arity at least 2 then the problem EXT(A) is almost surely NP-complete.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.