так что у меня есть два аггмента
L1={G(V,E)| in G exits VC in size upper-bound(|V|/2)}
L2={G(V,E)| in G every VC is in maximum size upper-bound (|E|/2)}
, чтобы классифицировать его в P NP или NP C и доказать это.
В основном я теперь, если мне нужно доказать что это в NP C Мне нужно показать, что проблема может быть проверена за полиномиальное время, которое помещает ее в NP. И тогда мне нужно построить сокращение от произвольной проблемы в NP C до проблемы, которая у меня есть.
Я думаю, что L1 в P.shuffle размером V C [V / 2] и сканировать в списке смежности, если все ребра покрыты. создание ТМ доказывает это?
второй мысли в NP C но я не уверен, плюс у меня нет идеи, как это доказать