ক্লাস NP ও ভেরিফায়ার

১ · NP — ভেরিফায়ার সংজ্ঞা

একটি ল্যাঙ্গুয়েজ $L$ NPNondeterministic Polynomial time-তে থাকে যদি একটি পলিনমিয়াল-টাইম ভেরিফায়ার $V$ ও একটি পলিনমিয়াল বাউন্ড $p(n)$ থাকে, যাতে —

$$w \in L \iff \exists \text{ certificate } c \text{ with } |c| \leq p(|w|) \text{ such that } V(w, c) \text{ accepts}$$

অর্থাৎ, NP-এর ল্যাঙ্গুয়েজগুলো এমন — যদি উত্তর "হ্যাঁ" হয়, তাহলে একটি সংক্ষিপ্ত (পলিনমিয়াল-length) "প্রমাণ"/সার্টিফিকেট আছে যা দ্রুত চেক করা যায় — এমনকি যদি সেই সার্টিফিকেট খুঁজে বের করা কঠিন হয়। এটিই NP-এর সবচেয়ে গুরুত্বপূর্ণ, ব্যবহারিক অন্তর্দৃষ্টি — "খুঁজে বের করা কঠিন, যাচাই করা সহজ।"

২ · NP — নন-ডিটারমিনিস্টিক TM সংজ্ঞা ও সমতুল্যতা

সমতুল্যভাবে (M8/L36-এর NTM ধারণার সরাসরি পুনর্ব্যবহার): $L \in \mathrm{NP}$ যদি কোনো নন-ডিটারমিনিস্টিক TM $L$-কে পলিনমিয়াল সময়ে ডিসাইড করে — এখানে "নন-ডিটারমিনিস্টিক সময়" মানে সবচেয়ে দীর্ঘ accepting শাখার length (L36-এর branching-tree ফ্রেমিং-এর সরাসরি পুনর্ব্যবহার)।

দুই সংজ্ঞার সমতুল্যতার স্বজ্ঞা (intuition) সংক্ষেপে — একটি NTM-এর accepting শাখা (যে নির্দিষ্ট নন-ডিটারমিনিস্টিক পছন্দের সিকোয়েন্স accept-এ নিয়ে যায়) ঠিক একটি সার্টিফিকেট; উল্টোদিকে, একটি সার্টিফিকেট নন-ডিটারমিনিস্টিকভাবে "গেস" করে তারপর ডিটারমিনিস্টিকভাবে ভেরিফাই করলেই একটি NTM পাওয়া যায়।

৩ · উদাহরণ — SAT NP-তে

SATBoolean Satisfiabilityএকটি বুলিয়ান ফর্মুলার ভেরিয়েবলগুলোতে TRUE/FALSE বসিয়ে ফর্মুলাটিকে TRUE করা যায় কি না (বুলিয়ান স্যাটিসফায়াবিলিটি) — একটি প্রদত্ত বুলিয়ান ফর্মুলার ভেরিয়েবলগুলোতে এমন কোনো TRUE/FALSE অ্যাসাইনমেন্ট আছে কি না যা পুরো ফর্মুলাকে TRUE করে? SAT NP-তে, কারণ সার্টিফিকেট হলো একটি প্রস্তাবিত অ্যাসাইনমেন্ট (পলিনমিয়াল length — প্রতি ভেরিয়েবলে এক বিট), আর সেটি যাচাই করা (ফর্মুলায় বসিয়ে মূল্যায়ন করা) মাত্র পলিনমিয়াল সময়ে সম্ভব — যদিও সার্টিফিকেট হাতে না পেয়ে একটি সন্তোষজনক অ্যাসাইনমেন্ট খুঁজে বের করা অনেক বেশি কঠিন বলে বিশ্বাস করা হয় (L46-এর কুক-লেভিন থিওরেমের সরাসরি foreshadowing, যা দেখাবে SAT শুধু NP-তে নয়, বরং একটি সুনির্দিষ্ট অর্থে NP-এর সবচেয়ে কঠিন সমস্যাগুলোর একটি)।

৪ · P ⊆ NP

একটি সহজ কিন্তু গুরুত্বপূর্ণ পর্যবেক্ষণ — প্রতিটি পলিনমিয়াল-সময়ে-ডিসাইডেবল ল্যাঙ্গুয়েজ ($\mathrm{P}$-তে) একইসাথে পলিনমিয়াল-সময়ে-যাচাইযোগ্যও ($\mathrm{NP}$-তে) — সার্টিফিকেটকে সম্পূর্ণ উপেক্ষা করে সরাসরি P-এর অ্যালগরিদম চালালেই হয়। তাই $\mathrm{P} \subseteq \mathrm{NP}$। এই containment স্ট্রিক্ট ($\mathrm{P} \subsetneq \mathrm{NP}$) নাকি আসলে সমতা ($\mathrm{P} = \mathrm{NP}$) — এটিই L49-এর বিখ্যাত, এখনও-অমীমাংসিত প্রশ্ন, কম্পিউটার সায়েন্সের একক সবচেয়ে বিখ্যাত খোলা সমস্যা।

# SAT ভেরিফায়ার (পলিনমিয়াল-টাইম, eval()/exec()/re ছাড়াই -- সরাসরি nested-tuple structure মূল্যায়ন)

def eval_formula(node, assignment):
    if isinstance(node, str):
        return assignment[node]          # একটি ভেরিয়েবলের নাম
    op = node[0]
    if op == 'not':
        return not eval_formula(node[1], assignment)
    if op == 'and':
        return eval_formula(node[1], assignment) and eval_formula(node[2], assignment)
    if op == 'or':
        return eval_formula(node[1], assignment) or eval_formula(node[2], assignment)
    raise ValueError(f"অজানা অপারেটর: {op}")

def verify_sat(formula, assignment):
    # সার্টিফিকেট (assignment) দেওয়া থাকলে, ফর্মুলাটি সন্তুষ্ট হয় কি না -- লিনিয়ার সময়ে যাচাই
    return eval_formula(formula, assignment)

# formula = x3 AND (x1 OR NOT x2)
formula = ('and', ('or', 'x1', ('not', 'x2')), 'x3')

satisfying_assignment = {'x1': True, 'x2': True, 'x3': True}
unsatisfying_assignment = {'x1': True, 'x2': True, 'x3': False}

print("সন্তোষজনক অ্যাসাইনমেন্ট:", satisfying_assignment)
print("verify_sat ফলাফল:", verify_sat(formula, satisfying_assignment), "(প্রত্যাশিত: True)")
print()
print("অসন্তোষজনক অ্যাসাইনমেন্ট:", unsatisfying_assignment)
print("verify_sat ফলাফল:", verify_sat(formula, unsatisfying_assignment), "(প্রত্যাশিত: False)")

# ---- ব্রুট-ফোর্স SAT সলভার -- জেনুইনভাবে সঠিক, কিন্তু এক্সপোনেনশিয়াল (সব 2^n সম্ভাব্য অ্যাসাইনমেন্ট চেষ্টা করে) ----
import itertools

def brute_force_sat(formula, variables):
    for bits in itertools.product([False, True], repeat=len(variables)):
        assignment = dict(zip(variables, bits))
        if verify_sat(formula, assignment):
            return assignment
    return None   # কোনো সন্তোষজনক অ্যাসাইনমেন্ট নেই

variables = ['x1', 'x2', 'x3']
found = brute_force_sat(formula, variables)
print()
print(f"brute_force_sat 2^{len(variables)} = {2**len(variables)}টি অ্যাসাইনমেন্ট চেষ্টা করে খুঁজে পেল:", found)
print("cross-check: verify_sat দিয়ে এই পাওয়া অ্যাসাইনমেন্ট যাচাই:", verify_sat(formula, found))