P বনাম NP ও NP-সম্পূর্ণতা পরিচিতি

১ · Class P — দক্ষভাবে সমাধানযোগ্য

Class PClass P (Polynomial time)এমন সমস্যার শ্রেণি যা একটি ডিটারমিনিস্টিক অ্যালগরিদম দিয়ে $O(n^k)$ সময়ে ($k$ একটি ধ্রুবক) সমাধান করা যায়।-তে সেই সব সমস্যা পড়ে যা একটি ডিটারমিনিস্টিক অ্যালগরিদম দিয়ে পলিনমিয়াল সময়ে ($O(n^k)$, $k$ একটি ধ্রুবক) সমাধান করা যায়। L39-এর ভাষায়: O(1), O(log n), O(n), O(n log n), O(n²), O(n³) — এই সবগুলো ক্লাসের সমস্যাই P-এর অন্তর্ভুক্ত। উদাহরণ: sorting, searching, shortest path খোঁজা (graph traversal) — সবই P-তে।

২ · Class NP — দ্রুত যাচাইযোগ্য

Class NPClass NP (Nondeterministic Polynomial time)এমন সমস্যার শ্রেণি যেখানে একটি প্রস্তাবিত সমাধান দেওয়া থাকলে, তা সঠিক কি না তা পলিনমিয়াল সময়ে যাচাই করা যায় — সমাধান খোঁজাটা যত কঠিনই হোক না কেন।-এর সংজ্ঞা ভিন্ন কোণ থেকে — একটি সমস্যা NP-তে পড়ে যদি তার জন্য একটি প্রস্তাবিত সমাধান (candidate solution) দেওয়া থাকলে, সেটি সঠিক কি না তা পলিনমিয়াল সময়ে যাচাই করা যায় — এমনকি যদি সেই সমাধান খুঁজে বের করা অনেক বেশি সময় নেয়। যেমন একটি ৯×৯ সুডোকুর পূর্ণ সমাধান দেওয়া থাকলে তা সঠিক কি না চেক করা তাৎক্ষণিক — কিন্তু শূন্য থেকে সমাধান খোঁজা অনেক কঠিন।

৩ · খোলা প্রশ্ন — P = NP?

প্রশ্নটি সহজ শোনায়: যা কিছু দ্রুত যাচাই করা যায়, তা কি সবসময় দ্রুত সমাধানও করা যায়? অর্থাৎ $P = NP$? এটি কম্পিউটার সায়েন্স তথা গণিতের সবচেয়ে বিখ্যাত অমীমাংসিত সমস্যাগুলোর একটি — Clay Mathematics Institute-এর সাতটি "Millennium Prize Problem"-এর একটি, যার সমাধানের জন্য \$১০ লক্ষ পুরস্কার ঘোষিত। বেশিরভাগ কম্পিউটার বিজ্ঞানী বিশ্বাস করেন $P \ne NP$ (অর্থাৎ কিছু সমস্যা যাচাই করা সহজ কিন্তু সমাধান করা মৌলিকভাবেই কঠিন), কিন্তু আজ পর্যন্ত এটি প্রমাণিত হয়নি।

৪ · NP-সম্পূর্ণতা — NP-এর সবচেয়ে কঠিন সমস্যা

NP-সম্পূর্ণ (NP-complete)NP-completeNP-এর এমন সমস্যা যার জন্য কোনো পলিনমিয়াল-সময় অ্যালগরিদম পাওয়া গেলে, NP-এর প্রতিটি সমস্যাই পলিনমিয়াল সময়ে সমাধানযোগ্য হয়ে যাবে (অর্থাৎ P=NP প্রমাণিত হবে)। সমস্যাগুলো হলো NP-এর "সবচেয়ে কঠিন" সমস্যা — যদি এদের মধ্যে যেকোনো একটির জন্য একটি পলিনমিয়াল-সময় অ্যালগরিদম পাওয়া যেত, তাহলে NP-এর প্রতিটি সমস্যাই পলিনমিয়াল সময়ে সমাধানযোগ্য হয়ে যেত (অর্থাৎ $P=NP$ প্রমাণিত হতো)। কয়েকটি ক্লাসিক উদাহরণ —

৫ · ব্যবহারিক শিক্ষা

যখন কোনো সমস্যাকে NP-সম্পূর্ণ হিসেবে চেনা যায়, তখন একটি দ্রুত, সঠিক (exact) অ্যালগরিদম খোঁজায় সময় নষ্ট না করে বরং এই পথগুলো বিবেচনা করা উচিত — approximation algorithm (কাছাকাছি উত্তর, নিশ্চিত সময়ে), heuristic (বেশিরভাগ ক্ষেত্রে ভালো কাজ করে এমন কৌশল, গ্যারান্টি ছাড়া), অথবা সমস্যাটিকে একটি বিশেষ, সহজ কেসে সীমাবদ্ধ করা (যেমন ইনপুট সাইজ ছোট রাখা)।

৬ · কোড: যাচাই সহজ, সমাধান কঠিন

import itertools

# একটি বুলিয়ান ফর্মুলা (৩টি ভ্যারিয়েবল a, b, c):
# (a OR b) AND (NOT b OR c) AND (a OR NOT c)
def formula(a, b, c):
    return (a or b) and ((not b) or c) and (a or (not c))

# ধাপ ১ — ভেরিফিকেশন সহজ (O(1) ফর্মুলা-মূল্যায়ন):
# একটি candidate assignment দেওয়া থাকলে তা যাচাই করতে ফর্মুলাটি শুধু একবার চালাতে হয়
candidate = {"a": True, "b": False, "c": True}
is_satisfied = formula(candidate["a"], candidate["b"], candidate["c"])
print("Candidate assignment:", candidate)
print("এই assignment ফর্মুলাটি সন্তুষ্ট করে কি না:", is_satisfied)

# ধাপ ২ — সমাধান খোঁজা কঠিন: brute force-এ সব 2^k সম্ভাব্য assignment পরীক্ষা করতে হয়
k = 3
tried = 0
satisfying = []
for values in itertools.product([True, False], repeat=k):
    tried += 1
    a, b, c = values
    if formula(a, b, c):
        satisfying.append(values)

print(f"\nমোট {tried} = 2^{k} টি combination brute-force-এ পরীক্ষা করা হলো")
print("সন্তুষ্টকারী assignment(গুলো):", satisfying)
print(f"লক্ষ করুন: k={k} ভ্যারিয়েবলের জন্য brute force-এ 2^{k}={2**k}টি চেষ্টা লাগলো —")
print("k বাড়লে (যেমন k=50) এই সংখ্যা এক্সপোনেনশিয়ালভাবে অসম্ভব হয়ে যাবে, যদিও যাচাই সবসময়ই O(1)।")