টাইম কমপ্লেক্সিটি ও ক্লাস P

১ · "আদৌ গণনাযোগ্য" থেকে "কতটা কার্যকরভাবে গণনাযোগ্য"

M8-M9 জুড়ে আমরা দেখেছি টুরিং মেশিন (M8) কী গণনা করতে পারে, আর M9-এ দেখেছি কিছু সমস্যা (হল্টিং প্রবলেম, রাইসের থিওরেম, PCP) কোনো টুরিং মেশিন দিয়েই সমাধানযোগ্য নয় — এই প্রশ্নটা ছিল বাইনারি: হ্যাঁ, গণনাযোগ্য, নাকি না। কিন্তু বাস্তবে, একটি সমস্যা "গণনাযোগ্য" হলেই যথেষ্ট নয় — যদি সমাধানটি বের করতে মহাবিশ্বের বয়সের চেয়েও বেশি সময় লাগে, সেটি ব্যবহারিকভাবে অসমাধানযোগ্যই। M10-M11 এই দ্বিতীয়, সূক্ষ্মতর প্রশ্নটি নিয়ে কাজ করবে — L01-এর তৃতীয় স্তম্ভ, কমপ্লেক্সিটি থিওরি।

২ · টাইম কমপ্লেক্সিটি — সংজ্ঞা

একটি অ্যালগরিদম/টুরিং মেশিনের রানিং টাইম বলতে বোঝায় ইনপুট length $n$-এর একটি ফাংশন হিসেবে অ্যালগরিদমটি কতটি ধাপ নেয় — সাধারণত worst case (দৈর্ঘ্য $n$-এর সবচেয়ে খারাপ সম্ভাব্য ইনপুটের জন্য) বিবেচনা করা হয়, এবং সাধারণ Big-O নোটেশনে (../dsa/-এ ইতিমধ্যে বিস্তারিত আলোচিত asymptotic নোটেশনের সরাসরি পুনর্ব্যবহার, এখানে পুনরায় derive করছি না) একটি আপার বাউন্ড হিসেবে প্রকাশ করা হয় (যেমন $O(n^2)$)। টুরিং-মেশিন-ভিত্তিক কমপ্লেক্সিটি থিওরিতে নির্দিষ্টভাবে, "রানিং টাইম" মানে TM ইনপুট প্রক্রিয়া করে থামা পর্যন্ত কতগুলো ট্রানজিশন (ধাপ) নেয়, ইনপুট length-এর ফাংশন হিসেবে।

৩ · ক্লাস P — ফরমাল সংজ্ঞা

ক্লাস P (KaTeX-এ):

$$\mathrm{P} = \{L : L \text{ কোনো ডিটারমিনিস্টিক TM দিয়ে } O(n^k) \text{ সময়ে ডিসাইড করা যায়, কোনো ধ্রুবক } k \geq 1\text{-এর জন্য}\}$$

অর্থাৎ, P হলো সেইসব ল্যাঙ্গুয়েজ যেগুলো পলিনমিয়াল সময়ে ডিসাইডযোগ্য — "কার্যকরভাবে সমাধানযোগ্য"-এর প্রমিত, ব্যাপকভাবে-স্বীকৃত সংজ্ঞা। একটি সৎ সতর্কতা দিয়ে বলা প্রয়োজন — পলিনমিয়াল সময় সবসময় ব্যবহারিকভাবে দ্রুত নয় (যেমন $O(n^{100})$ পলিনমিয়াল হলেও বাস্তবে সম্পূর্ণ অকেজো) — কিন্তু পলিনমিয়াল-বনাম-এক্সপোনেনশিয়াল হলো প্রমিত তাত্ত্বিক বিভাজনরেখা, কারণ এক্সপোনেনশিয়াল অ্যালগরিদম $n$ বাড়ার সাথে সাথে অনেক দ্রুত অসাধ্য হয়ে ওঠে — এই কোর্স এটিকেই "কার্যকর"-এর working সংজ্ঞা হিসেবে গ্রহণ করে।

নিচের কোড সেলে পলিনমিয়াল ($O(n^k)$, বিভিন্ন $k$-এর জন্য) বনাম এক্সপোনেনশিয়াল ($O(2^n)$) সময়ের প্রকৃত ধাপ-সংখ্যা পাশাপাশি গণনা করে দেখা যাক — বড় $n$-এ ব্যবধানটা ঠিক কতটা নাটকীয়।

# পলিনমিয়াল O(n^k) বনাম এক্সপোনেনশিয়াল O(2^n) -- বাস্তব ধাপ-সংখ্যা পাশাপাশি

def time_complexity_class(exponent, n_values):
    # O(n^exponent) সময়ের জন্য প্রতিটি n-এ ধাপ-সংখ্যা গণনা
    return {n: n ** exponent for n in n_values}

def exponential_time(n_values):
    # O(2^n) সময়ের জন্য প্রতিটি n-এ ধাপ-সংখ্যা গণনা
    return {n: 2 ** n for n in n_values}

n_values = [10, 100, 1000]

results = {}
for k in [1, 2, 3]:
    results[f"O(n^{k})"] = time_complexity_class(k, n_values)
results["O(2^n)"] = exponential_time(n_values)

print(f"{'n':>6} | {'O(n^1)':>12} | {'O(n^2)':>16} | {'O(n^3)':>20} | {'O(2^n)':>14}")
print("-" * 80)
for n in n_values:
    row = [str(results[f"O(n^{k})"][n]) for k in [1, 2, 3]]
    exp_val = results["O(2^n)"][n]
    exp_str = str(exp_val) if exp_val < 10**20 else f"~10^{len(str(exp_val))-1} (একটি {len(str(exp_val))}-অঙ্কের সংখ্যা)"
    print(f"{n:>6} | {row[0]:>12} | {row[1]:>16} | {row[2]:>20} | {exp_str:>14}")

print()
print(f"n=1000-এ O(n^3) = {results['O(n^3)'][1000]:,} ধাপ")
print(f"n=1000-এ O(2^n) হলো একটি {len(str(results['O(2^n)'][1000]))}-অঙ্কের সংখ্যা -- ব্যবহারিকভাবে অগণনাযোগ্য")