অ্যাডভান্সড টপিক৯ মিনিট পড়া

এনপি (NP), এনপি-কমপ্লিট (NP-Complete), এনপি-হার্ড (NP-Hard)

দ্য মিলিয়ন-ডলার প্রশ্ন: কোনো উত্তর খুঁজে বের করা কি কখনো তা যাচাই করার মতো সহজ হতে পারে?
P:পলিনোমিয়াল (Polynomial) সময়ে সমাধানযোগ্যNP:পলিনোমিয়াল সময়ে যাচাইযোগ্যNP-complete:NP-এর মধ্যে সবচেয়ে কঠিন সমস্যাNP-hard:অন্তত NP-কমপ্লিট এর মতোই কঠিন (এমনকি যাচাইযোগ্য নাও হতে পারে)

আপনি এইমাত্র একটি সুডোকু (Sudoku) পাজল শেষ করেছেন। আপনি এটি সঠিকভাবে সমাধান করেছেন কিনা তা যাচাই করবেন? খুব সহজ — প্রতিটি সারি, কলাম এবং বক্স স্ক্যান বা পরীক্ষা করুন। কয়েক সেকেন্ড সময় লাগবে। কিন্তু একটি ফাঁকা পাজল সমাধান করা? পাজলের ওপর নির্ভর করে এতে কয়েক মিনিট, কয়েক ঘণ্টা বা অনন্তকাল সময়ও লাগতে পারে।

সমাধান যাচাই করা এবং সমাধান খুঁজে বের করার মধ্যকার এই ব্যবধানটিই গণিত এবং কম্পিউটার বিঞ্জানের সবচেয়ে গুরুত্বপূর্ণ অমীমাংসিত সমস্যার মূলে রয়েছে: P বনাম NP (P vs NP)।

P — দ্রুত সমাধানযোগ্য সমস্যা (problems with fast solutions)

P (Polynomial time বা বহুপদী সময়) হলো এমন সমস্যার শ্রেণী যা একটি কম্পিউটার দ্বারা নির্দিষ্ট কোনো ধ্রুবক k এর জন্য \(O(n^k)\) সময়ে সমাধান করা যায়, যেখানে n হলো ইনপুটের আকার। এগুলো হলো "দক্ষভাবে বা কার্যকরভাবে (efficiently) সমাধানযোগ্য" সমস্যা।

উদাহরণ: একটি তালিকা বা লিস্ট সাজানো (sorting), সবচেয়ে ছোট পথ বা শর্টেস্ট পাথ (shortest paths) খুঁজে বের করা (ডাইকস্ট্রা বা Dijkstra), কোনো সংখ্যা মৌলিক (prime) কিনা তা যাচাই করা (AKS অ্যালগরিদম), লিনিয়ার সিস্টেম (linear system) সমাধান করা।

NP — দ্রুত যাচাইযোগ্য সমস্যা (problems with fast verification)

NP (Nondeterministic Polynomial time বা ননডিটারমিনিস্টিক পলিনোমিয়াল সময়) হলো এমন সমস্যার শ্রেণী যেখানে একটি প্রস্তাবিত "হ্যাঁ (yes)" সমাধানকে — যাকে সার্টিফিকেট (certificate) বলা হয় — পলিনোমিয়াল সময়ে যাচাই করা যেতে পারে।

এটিকে একটি প্যাডলক বা তালার (padlock) মতো করে ভাবুন। এর সব কম্বিনেশন বা সংখ্যা মিলিয়ে দেখতে গেলে সারাজীবন লেগে যাবে। কিন্তু যদি কেউ আপনার হাতে সঠিক কম্বিনেশনটি দিয়ে দেয়, তবে সেটি দিয়ে তালা খুলতে বা যাচাই করতে মাত্র এক সেকেন্ড সময় লাগবে।

উদাহরণ: সুডোকু (একটি সম্পূর্ণ গ্রিড \(O(n^2)\) তে যাচাই করা), ফ্যাক্টরিং বা উৎপাদকে বিশ্লেষণ (p × q = N কিনা তা \(O(n^2)\) তে যাচাই করা), হ্যামিল্টনিয়ান পাথ (একটি প্রস্তাবিত পথ প্রতিটি ভার্টেক্স একবার করে পরিদর্শন করে কিনা তা যাচাই করা)।

P শ্রেণীর প্রতিটি সমস্যাই NP-এর মধ্যেও পড়ে — যদি আপনি এটি দ্রুত সমাধান করতে পারেন, তবে আপনি দ্রুত যাচাইও করতে পারবেন। উন্মুক্ত বা অমীমাংসিত প্রশ্নটি হলো এর বিপরীতটি সত্যি কিনা: NP-এর প্রতিটি সমস্যা কি P-এর মধ্যেও পড়ে?

রিডাকশন (Reductions) — সমস্যার কাঠিন্য তুলনা করা

সমস্যা A, সমস্যা B-তে রিডিউস (reduces) হয় (লেখা হয় A ≤p B), যদি A-এর যেকোনো ইনস্ট্যান্সকে (instance) পলিনোমিয়াল সময়ের মধ্যে অ্যান্সার বা উত্তর অপরিবর্তিত রেখে B-এর একটি ইনস্ট্যান্সে রূপান্তর করা যায়। আপনি যদি B সমাধান করতে পারেন, তবে আপনি A-ও সমাধান করতে পারবেন। এর মানে হলো সমাধান করার ক্ষেত্রে B হলো "অন্ততপক্ষে A-এর মতোই কঠিন"।

NP-হার্ডনেস প্রমাণ করার জন্য রিডাকশন একটি প্রধান হাতিয়ার: আপনাকে প্রমাণ করতে হবে যে, একটি পরিচিত কঠিন সমস্যাকে আপনার বর্তমান সমস্যাতে রিডিউস করা যায়।

NP-কমপ্লিটনেস (NP-Completeness) — NP-এর মধ্যে সবচেয়ে কঠিন সমস্যা

একটি সমস্যা X কে NP-কমপ্লিট (NP-complete) বলা হবে যদি: (১) X সমস্যাটি NP-এর অন্তর্ভুক্ত হয় এবং (২) অন্য সব NP সমস্যাকে পলিনোমিয়াল টাইমে X-এ রিডিউস করা যায়। NP-কমপ্লিট সমস্যাগুলো হলো NP-এর মধ্যে "সবচেয়ে কঠিন" — এর যেকোনো একটিকে কার্যকরভাবে (efficiently) সমাধান করতে পারার অর্থ হলো পুরো NP-কে সমাধান করা।

স্টিফেন কুক (Stephen Cook) ১৯৭১ সালে প্রথম NP-কমপ্লিট সমস্যাটি প্রমাণ করেন: SAT — কোনো বুলিয়ান ফর্মুলা (Boolean formula) কি এর ভেরিয়েবলগুলোতে ট্রু/ফলস (true/false) মান বসিয়ে স্যাটিসফাই (satisfy) বা সত্য প্রমাণ করা সম্ভব? SAT থেকে শুরু করে, রিডাকশনের একটি শৃঙ্খলের (chain of reductions) মাধ্যমে আরও শত শত সমস্যাকে NP-কমপ্লিট হিসেবে প্রমাণ করা হয়েছে।

বিখ্যাত কিছু NP-কমপ্লিট সমস্যা

3-SAT: প্রতি ক্লজে (clause) ৩টি লিটারালসহ (literal) স্যাটিসফায়াবিলিটি — এটি NP-কমপ্লিটনেস প্রমাণের মূল চালিকাশক্তি (workhorse)।
গ্রাফ কালারিং (Graph Coloring): আপনি কি একটি গ্রাফের ভার্টেক্সগুলোকে k ≤ 3 টি রঙ দিয়ে এমনভাবে রাঙাতে পারবেন যেন পাশাপাশি থাকা কোনো দুটি ভার্টেক্সের রঙ একই না হয়?
হ্যামিল্টনিয়ান পাথ (Hamiltonian Path): এমন কোনো পথ কি আছে যা প্রতিটি ভার্টেক্সকে ঠিক একবারই পরিদর্শন করে?
TSP (ডিসিশন বা সিদ্ধান্ত): এমন কোনো ট্যুর (tour) কি আছে যা মোট k খরচের মধ্যে সব শহরে ভ্রমণ করে আসতে পারে?
সাবসেট সাম (Subset Sum): কোনো সেটের কিছু উপাদানের যোগফল কি হুবহু T এর সমান হয়?
ক্লিক (Clique): গ্রাফটিতে কি k আকারের একটি সম্পূর্ণ সাবগ্রাফ (complete subgraph) রয়েছে?

NP-হার্ড (NP-Hard) — NP-এর বাইরে

NP-হার্ড (NP-hard) মানে হলো "অন্তত NP-কমপ্লিট এর মতোই কঠিন", তবে এই সমস্যাটি নিজের জন্য NP-এর অন্তর্ভুক্ত না-ও হতে পারে — এমনকি এটি যাচাই করার জন্য কোনো পলিনোমিয়াল টাইমের সার্টিফিকেটও (polynomial-time verifiable certificate) না থাকতে পারে।

TSP-এর অপ্টিমাইজেশন (optimization) সংস্করণ ("সর্বনিম্ন খরচের ট্যুরটি বা পাথটি খুঁজে বের করুন") একটি NP-হার্ড সমস্যা, কিন্তু এটি NP-কমপ্লিট নয় — কারণ এটি কোনো হ্যাঁ/না বা ইয়েস/নো (yes/no) ডিসিশন প্রবলেম নয়। হল্টিং প্রবলেম (Halting Problem) হলো NP-হার্ড এবং আনডিসাইডেবল (undecidable) — যা আরও বেশি কঠিন।

কেন P ≠ NP এখনো প্রমাণিত হয়নি

প্রায় সব কম্পিউটার বিঞ্জানীই বিশ্বাস করেন যে P ≠ NP। কিন্তু গত ৫০ বছরেরও বেশি সময় ধরে এর কোনো সুনির্দিষ্ট প্রমাণ পাওয়া যায়নি। P ≠ NP প্রমাণ করতে হলে, আপনাকে প্রমাণ করতে হবে যে এমন কোনো অ্যালগরিদম — এমনকি যেসব অ্যালগরিদম আজও আবিষ্কৃত হয়নি — একটি NP-কমপ্লিট সমস্যাকে পলিনোমিয়াল সময়ের মধ্যে সমাধান করতে পারে পলিনোমিয়াল টাইমে। প্রতিটি পরিচিত প্রমাণ কৌশলই মৌলিক বাধা বা সীমাবদ্ধতার মুখোমুখি হয়েছে। এর সঠিক উত্তরের জন্য হয়তো সম্পূর্ণ নতুন কোনো গাণিতিক পদ্ধতির প্রয়োজন হতে পারে।

Click chart to zoom
একটি সমস্যাকে P, NP, NP-Complete, অথবা NP-Hard হিসেবে শ্রেণীবদ্ধ করার ডিসিশন ফ্লোচার্ট
দ্রষ্টব্য: যদি P = NP হয়, তবে ক্রিপ্টোগ্রাফি (cryptography) ধসে পড়বে: RSA, HTTPS, এবং প্রতিটি পাসওয়ার্ডকে পলিনোমিয়াল সময়ের মধ্যেই ভেঙে ফেলা (crack) সম্ভব হবে। ইন্টারনেট এখনো ঠিকমতো কাজ করছে — এটি P ≠ NP হওয়ার একটি অনানুষ্ঠানিক (informal) প্রমাণ।

একটি NP সার্টিফিকেট যাচাইকরণ — সাবসেট সাম (Subset Sum)

# Subset Sum: does any subset sum to target T?
# Checking is O(n) — a certificate is just the subset.
# Finding is NP-hard (exponential worst case).


def verify_subset_sum(nums, subset_indices, target):
    """O(n) verification — the NP part."""
    total = sum(nums[i] for i in subset_indices)
    return total == target


def find_subset_sum(nums, target):
    """Backtracking — exponential worst case."""
    n = len(nums)
    def backtrack(idx, remaining, chosen):
        if remaining == 0:
            return chosen[:]
        if idx == n or remaining < 0:
            return None
        # Include nums[idx]
        chosen.append(idx)
        result = backtrack(idx+1, remaining-nums[idx], chosen)
        if result: return result
        chosen.pop()
        # Skip nums[idx]
        return backtrack(idx+1, remaining, chosen)
    return backtrack(0, target, [])


nums = [3, 1, 4, 1, 5, 9, 2, 6]
target = 15
indices = find_subset_sum(nums, target)
print("Subset indices:", indices)
print("Values:", [nums[i] for i in indices])
print("Sum:", sum(nums[i] for i in indices))
print("Certificate valid:", verify_subset_sum(nums, indices, target))
Output
Subset indices: [0, 2, 4, 6]
Values: [3, 4, 5, 2]
Sum: 14
Certificate valid: False

Complexity

✅ ক্লাস P
সর্টিং বা সাজানো, সবচেয়ে ছোট পথ, লিনিয়ার প্রোগ্রামিং, প্রাইমালিটি (AKS 2002)
দ্রুত সমাধানযোগ্য \(O(n^k)\)
🔍 ক্লাস NP
P-এর সবকিছুই এতে আছে; সুডোকু, উৎপাদকে বিশ্লেষণ বা ফ্যাক্টরিং, সাবসেট সাম, হ্যামিল্টনিয়ান পাথ
দ্রুত যাচাইযোগ্য; সমাধান করতে এক্সপোনেনশিয়াল (exponential) সময় লাগতে পারে যাচাই করতে \(O(n^k)\)
🔥 NP-কমপ্লিট (NP-complete)
SAT, 3-SAT, ক্লিক (Clique), TSP, গ্রাফ কালারিং, ন্যাপস্যাক (Knapsack), সাবসেট সাম
NP-এর মধ্যে সবচেয়ে কঠিন সমস্যা সবচেয়ে পরিচিত অপটিমাম: এক্সপোনেনশিয়াল (exponential)
💀 NP-হার্ড (NP-এর বাইরে)
অপ্টিমাইজেশন TSP, হল্টিং প্রবলেম (Halting Problem) — এর কোনো পলিনোমিয়াল-টাইম যাচাইযোগ্য সার্টিফিকেট নাও থাকতে পারে
অন্তত NP-কমপ্লিট এর মতোই কঠিন আনডিসাইডেবল (undecidable) হতে পারে

ছোট কুইজ

একটি সমস্যা NP তে আছে। এটি আপনাকে কী বলে?

পড়া চালিয়ে যান