加载中…
2011-06-03
Complexity of the homomorphism extension problem in the random case
Alexandr Kazda
文献摘要
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.
讨论
0讲解博客
生成讲解博客的中文版本
AI智能校验
生成AI智能校验的中文版本