La langue définie-elle dans les détails de NP-C ou P?

Question

On sait que: $$ \ textrm {clique}={(g, k): \ mbox {g a une clique de taille} k \} $$ est $ \ textrm {np-c} $ , mais si chaque sommet a 2 voisins (tel que défini dans $ \ textrm{2D-Clique} $ )? $$ \ textrm {2d-clique}={(g, k): \ mbox {Chaque sommet de G a exactement 2 $ $ voisins et $ G $ a une clique de taille} k \}. $$

Answer 1

En supposant que chaque sommet de $ g $ a degrés $ 2 $ , aucune clique de $ g $ peut avoir plus que 3 $ $ sommets. Alors $ \ textrm {2d-clique} $ est trivialement dans $ \ textrm {p} $ et, Si $ \ textrm {p} \ neq \ textrm {np} $ , il ne peut pas être $ \ textrm {np} $ -Compléte.

sous l'hypothèse ci-dessus (qui est trivial à vérifier), $ (g, k) \ in \ textrm {2d-clique} $ iff l'une des opérations suivantes Conditions contient:

• $ k= 0 $ ou
• $ k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \} $ et $ g $ n'est pas vide , ou
• $ k= 3 $ et $ g $ a un triangle, qui peut être vérifié dans < SPAN CLASSE="Conteneur mathématique"> $ O (n) $ TIME.