خوارزمية التحقق satisfiability

Question

من أجل إثبات أن جلس في NP لقد تحتاج إلى الخروج مع وقت متعدد الحدود verfier (خوارزمية).الطهاة ليفين نظرية الاستخدامات غير القطعية آلة تورينج ولكن هذا ليس ما أنا أبحث عنه.

فكرة الخوارزمية يمكن أن نضع في القيم وحساب الجواب.ثم علينا التحقق ما إذا كان الجواب هو 1 أو لا.ولكن أنا غير قادر على فهم كيف يمكن كتابة psuedocode ل 'وضع في القيم' جزءا ثم تبين أنه متعدد الحدود بالتأكيد.

if x = 1:
 accept
else:
 reject

هذا يمكن أن يكون في O(1).ولكن ماذا عن الباقين ؟

Answer 1

هنا هو كيف نفعل ذلك:

Algo: المدقق مقابل DNF-جلس المشكلة إعطاء مجموعة من الإغلاق و من الممكن رسم خرائط حرفية إلى القيم المنطقية
الإدخال:
مجموعة من الإغلاق:[$C_1$,$C_2$,...,$C_m$]
حيث $C_j \subseteq \{x_1,...,x_n, eg x_1, ... eg x_n\}$
(شهادة) مجموعة $م$ حيث $M_i$ هو قيمة منطقية من حرفية $x_i$
الإخراج: صحيحة أو خاطئة

for $i = 1$ to $م$:
  value = true
  for literal in $C_i$:
    if literal == $x_i$:
      value = value or $M[i]$:
    else if literal == $
eg x_i$:
      value = value or (not $M[i]$)
  if not value:
    return false
return true 

ملاحظة:الرياضيات التدوين هو بادئة تستخدم عادة في شبة الكود للأسف cs stackexchange لا يعتمد عليه