P বনাম NP ও অ্যালগরিদম ডিজাইনে এর প্রভাব

১ · P — যা দ্রুত সমাধান করা যায়

এই কোর্সের M2-M10 পর্যন্ত যত অ্যালগরিদম দেখেছি — মার্জ সর্ট, ডাইজকস্ট্রা, DP-ভিত্তিক সমাধান — তাদের প্রায় সবগুলোই একটি সাধারণ ক্লাসের অন্তর্ভুক্ত:

$$P = \{\, L : L\text{-কে সিদ্ধান্ত নেওয়ার মতো একটি ডিটারমিনিস্টিক অ্যালগরিদম আছে যা } O(n^k) \text{ সময়ে চলে, কোনো ধ্রুবক } k \text{-এর জন্য} \,\}$$

সহজ কথায়: PPolynomial timeইনপুটের আকার $n$ বাড়লে রানটাইম $n$-এর কোনো নির্দিষ্ট ঘাতে (পাওয়ারে) বাড়ে — $n^2$, $n^3$ ইত্যাদি — $2^n$ বা $n!$-এর মতো নয়। হলো সেই সমস্যাগুলো যেগুলোর জন্য আমরা সরাসরি, কোনো ট্রায়াল-অ্যান্ড-এরর ছাড়াই, একটি কার্যকর সমাধান অ্যালগরিদম লিখতে পারি। L05-L06-এ ইতিমধ্যে এই "পলিনোমিয়াল বনাম এক্সপোনেনশিয়াল" গ্রোথ রেটের পার্থক্য বিস্তারিত দেখা হয়েছে — এখানে আমরা সেটাকে একটি সমস্যার ক্লাস সংজ্ঞায়িত করতে ব্যবহার করছি।

২ · NP — যা দ্রুত যাচাই করা যায়

এখন প্রশ্ন হলো: এমন সমস্যা কি আছে যেগুলোর জন্য সমাধান খুঁজে বের করা কঠিন মনে হয়, কিন্তু কেউ একটা সমাধান প্রস্তাব করলে সেটা সঠিক কিনা যাচাই করা দ্রুত? উত্তর হ্যাঁ — এবং এই ধরনের সমস্যাগুলোর ক্লাসের নামই NP (Nondeterministic Polynomial time)।

$$L \in NP \iff \exists\ \text{পলিনোমিয়াল } p \text{ ও পলিনোমিয়াল-টাইম অ্যালগরিদম } V \text{ এমন যে, প্রতিটি } x \text{-এর জন্য: } x \in L \iff \exists\, c,\ |c| \le p(|x|),\ V(x, c) = \text{Accept}$$

এখানে $c$-কে বলা হয় সার্টিফিকেট (certificate) বা প্রমাণ, আর $V$-কে বলা হয় ভেরিফায়ার (verifier)। লক্ষণীয় — এই সংজ্ঞায় কোথাও বলা নেই যে $c$ কীভাবে খুঁজে পাওয়া যাবে; শুধু বলা হয়েছে, $c$ থাকলে $V$ সেটাকে পলিনোমিয়াল সময়ে চেক করতে পারবে।

নিচের কোডে ঠিক এই ভেরিফায়ারটাই বাস্তবে লেখা হয়েছে — উপরের $\phi$ ফর্মুলাটি ক্লজের একটি লিস্ট হিসেবে প্রতিনিধিত্ব করা হয়েছে, এবং verify_assignment ফাংশনটি একটি candidate assignment নিয়ে সেটা $\phi$-কে সন্তুষ্ট করে কিনা চেক করে — সমাধান খোঁজে না, শুধু যাচাই করে।

# phi = (x0 OR x1 OR NOT x2) AND (NOT x0 OR x2) AND (x1 OR NOT x2) AND (NOT x1 OR NOT x0 OR x2)
# প্রতিটি ক্লজ = লিটারেলের একটি লিস্ট; প্রতিটি লিটারেল = (variable_index, negated_কিনা)
formula = [
    [(0, False), (1, False), (2, True)],
    [(0, True), (2, False)],
    [(1, False), (2, True)],
    [(1, True), (0, True), (2, False)],
]

def verify_assignment(formula, assignment):
    """সার্টিফিকেট (candidate assignment) যাচাই করে -- প্রতিটি ক্লজে
    অন্তত একটি লিটারেল True কিনা দেখে। সময় জটিলতা O(m), যেখানে m হলো
    ফর্মুলার মোট লিটারেল সংখ্যা -- ইনপুটের (n ভ্যারিয়েবল) সাপেক্ষে পলিনোমিয়াল।"""
    literal_checks = 0
    for clause in formula:
        clause_satisfied = False
        for var_idx, negated in clause:
            literal_checks += 1
            value = assignment[var_idx]
            if negated:
                value = not value
            if value:
                clause_satisfied = True
                break
        if not clause_satisfied:
            return False, literal_checks
    return True, literal_checks

candidate = [True, True, True]  # x0=True, x1=True, x2=True -- এটাই "সার্টিফিকেট"
is_sat, checks = verify_assignment(formula, candidate)
print(f"candidate {candidate} -> সন্তুষ্ট: {is_sat}, মোট লিটারেল-চেক: {checks}")

wrong_candidate = [True, True, False]
is_sat2, checks2 = verify_assignment(formula, wrong_candidate)
print(f"candidate {wrong_candidate} -> সন্তুষ্ট: {is_sat2}, মোট লিটারেল-চেক: {checks2}")

n = 3
print(f"\n{n} ভ্যারিয়েবলের জন্য সম্ভাব্য assignment সংখ্যা: 2^{n} = {2 ** n}")
print("প্রতিটি candidate যাচাই করতে মাত্র O(m) সময় লাগে -- কিন্তু 'কোনটা কাজ করে' তা")
print("খুঁজে বের করতে ব্রুট-ফোর্সে সবগুলো সম্ভাবনা try করা লাগতে পারে (n বড় হলে এক্সপোনেনশিয়াল)।")

৩ · P=?NP — কেন এই প্রশ্নটা এখনো খোলা

এতক্ষণে একটা জিনিস স্পষ্ট হওয়ার কথা: $P \subseteq NP$ — কারণ যদি কোনো সমস্যা পলিনোমিয়াল সময়ে সরাসরি সমাধান করা যায়, তাহলে সেই সমাধান অ্যালগরিদমটাকেই একটা (সার্টিফিকেট উপেক্ষা করা) ভেরিফায়ার হিসেবে ব্যবহার করা যায়। কিন্তু উল্টো দিকটা — $NP \subseteq P$ কিনা, অর্থাৎ যা কিছু দ্রুত যাচাই করা যায় তা কি সবসময় দ্রুত খুঁজেও বের করা যায় — এটাই কম্পিউটার সায়েন্সের সবচেয়ে বিখ্যাত খোলা প্রশ্ন, যাকে বলা হয় $P \overset{?}{=} NP$।

এই প্রশ্নের আনুষ্ঠানিক সংজ্ঞা, ইতিহাস, এবং কেন এটি প্রমাণ করা এত কঠিন — তা নিয়ে Theory of Computation কোর্সের "The P vs NP Question" পাঠ-এ পূর্ণাঙ্গ আলোচনা আছে। P ও NP-এর সম্পূর্ণ আনুষ্ঠানিক সংজ্ঞা ও প্রমাণ পদ্ধতির জন্য দেখুন "Time Complexity and the Class P" এবং "The Class NP and Verifiers" পাঠদুটো।