Определяет ли язык в деталях в NP-C или P?

Question

Известно, что: $$ \ textrm {клика}={(g, k): \ mbox {g имеет клику размера} k \} $$ это $ \ textrm {np-c} $ , но что, если у каждой вершины 2 соседей (как определено в $ \ textrm{2D-клика} $ )? $$ \ textrm {2d-Clique}={(g, k): \ mbox {Каждая вершина в g имеет ровно 2 $ соседи и $ G $ имеет клику размера} k \}. $$

Answer 1

Предполагая, что каждая вершина $ G $ имеет степень $ 2 $ , нет клики $ G $ может иметь больше, чем 3 $ $ вершины. Затем $ \ textrm {2D-Clique} $ тривиально в $ \ Textrm {p} $ и, Если $ \ textrm {p} \ neq \ textrm {np} $ , он не может быть $ \ textrm {np} $ --complete.

под вышеуказанным предположением (который тривиален для проверки), $ (g, k) \ \ textrm {2d-Clique} $ IFF Один из следующих Условия удерживаются:

.
• $ k= 0 $ , или
• $ k \ in \ {1,2 \} $ и $ g $ не пустой или
• $ k= 3 $ и $ g $ имеет треугольник, который можно проверить Spaness Class="Математический контейнер"> $ o (n) $ time.