مواجهة الوقت متعدد الحدود من حلول التعبير 2SAT مع الحرف اليدوي الخالص

Question

حسب العنوان، هل هناك أي خوارزمية وقت متعدد الحدود لحساب عدد الحجج المرضية للتعبير 2SAT مع الحرف اليدوي الخالص؟حالة ضحلة إضافية: هل هناك أي عداد من هذا القبيل عندما تكون الحرفية في التعبير إما إيجابية، أو كل ذلك سلبي؟

Answer 1

عد عدد التخصيصات المرضية في صيغة 2SAT إيجابية هي نفس العد عدد أغطية الرأس في الرسم البياني المقابل (بعد إزالة بنود Singleton).العد من المعروف أن عدد أغلفة قمة الرأس معروف $ \ mathsf {\ # p} $ -complete.انظر أيضا هذا السؤال حول CSTHORY.