هل اللغة المحددة في التفاصيل في NP-C أو P؟

Question

من المعروف أن: $$ \ Textrm {clique}={(g، k): \ mbox {g لديه زمرة من الحجم} k \} $ هو $ \ textrm {np-c} $ ، ولكن ماذا لو كان لدى كل قسط 2 جيران (كما هو محدد في $ \ textrm{2D-clique} $ )؟ $$ \ Textrm {2D-clique}={(g، k): \ mbobbox {كل قمة في 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) \ in \ textrm {2D-clique} $ iff One of التالي الحالات تحمل:

• $ k= 0 $ ، أو
• $ k \ in \ {1،2 \} $ and $ g $ غير فارغ ، أو
• $ k= 3 $ و لديه مثلث، والتي يمكن التحقق منها < Span Class="حاوية الرياضيات"> $ O (n) $ الوقت.