সরাসরি পর্বে যান
পর্ব ৬৭ · ৮৫-এর মধ্যে · মডিউল ১১

Hierarchy theorem — বেশি সময়ে বেশি সমস্যা

Hierarchy Theorems — Constructible Functions, the Space and Time Hierarchies by Diagonalization, the Log Factor, P ⊊ EXP, NL ⊊ PSPACE, an EXPSPACE-Complete Problem and the Limits of Diagonalization

Taught in Bangla, this lesson asks whether more time or space solves more problems. It defines space- and time-constructible functions, proves the space hierarchy theorem with a diagonal machine D, proves the time hierarchy theorem and traces the extra log factor, and derives NL ⊊ PSPACE and P ⊊ EXP. It presents regex equivalence with exponentiation as a natural EXPSPACE-complete problem and explains why diagonalization alone cannot settle P versus NP. In-page Python (Pyodide) runs the diagonal argument.

এই পর্বে যা শিখবেন

  • Space- আর time-constructible function-এর সংজ্ঞা, উদাহরণ আর কেন এই শর্ত ছাড়া hierarchy ভেঙে পড়ে
  • Space hierarchy theorem-এর পূর্ণ প্রমাণ: diagonal যন্ত্র D, padding আর ধাপ-গণনার counter
  • Time hierarchy theorem-এর প্রমাণ আর log f(n) গুণকের সঠিক উৎস
  • অনুসিদ্ধান্ত: NL ⊊ PSPACE, P ⊊ EXP, PSPACE ⊊ EXPSPACE, আর কোন জোড়া এই উপপাদ্য আলাদা করে না
  • একটি স্বাভাবিক, প্রমাণিতভাবে কঠিন সমস্যা, আর diagonalization কেন P বনাম NP-তে আটকে যায়

১ · বেশি সম্পদ, বেশি সমস্যা? — প্রশ্নটি কেন কঠিন

আগের পর্বগুলোতে আমরা অনেক শ্রেণি দেখেছি আর তাদের একটি শৃঙ্খলে সাজিয়েছি: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP (পর্ব ৬৪)। প্রতিটি ⊆ প্রমাণিত, কারণ প্রতিটি ক্ষেত্রে একটি যন্ত্রকে আরেক ধরনের যন্ত্র দিয়ে অনুকরণ করা যায়। কিন্তু অন্তর্ভুক্তি দেখানো সহজ, কঠোরতা দেখানো কঠিন। “P ⊊ NP” বলতে হলে প্রমাণ করতে হবে যে NP-তে অন্তত একটি সমস্যা আছে, যা কোনো polynomial-সময়ের যন্ত্র decide করে না। পৃথিবীর সব সম্ভাব্য algorithm-এর বিরুদ্ধে একটি দাবি, যার কোনোটি আমরা এখনো দেখিনি।

এই পর্বের উপপাদ্যগুলো এমন দাবির প্রথম, আর এখনো সবচেয়ে সাধারণ অস্ত্রগুলোর একটি। তারা একটি সরল প্রশ্নের উত্তর দেয়: একই ধরনের সম্পদ, যেমন deterministic সময়, যদি “যথেষ্ট বেশি” দেওয়া হয়, তাহলে কি নতুন language decide করা যায়? উত্তর: হ্যাঁ, আর “যথেষ্ট বেশি” কতটা, তা-ও নিখুঁতভাবে বলা যায়।

বাজারঘরের গুদামের হিসাবরক্ষকের কথা ভাবুন। তাঁর হাতে একটি খাতা। দশ পাতার খাতায় তিনি একদিনের অর্ডারের হিসাব রাখতে পারেন, কিন্তু পুরো মাসের প্রতিটি পার্সেলের ইতিহাস নয়। একশো পাতার খাতা পেলে কি তিনি সত্যিই এমন প্রশ্নের উত্তর দিতে পারবেন, যা দশ পাতায় কোনো কৌশলেই সম্ভব নয়? সহজাত উত্তর “অবশ্যই”। কিন্তু গণিতে সহজাত উত্তর প্রমাণ নয়: হয়তো কোনো চতুর সংক্ষেপ-পদ্ধতি দশ পাতাতেই সব ধরে ফেলে। Hierarchy theorem প্রমাণ করে, তেমন চতুরতা সবসময় সম্ভব নয়, যদি খাতার মাপ নিজে একটি সহজে মাপা যায় এমন সংখ্যা হয়।

প্রমাণের কৌশলটি আপনার চেনা। পর্ব ৫১-এ ATM-এর undecidability প্রমাণে একটি যন্ত্র D সব যন্ত্রের তালিকার কর্ণ বরাবর উত্তর উল্টে দিয়েছিল। সেখানে D-এর হাতে সীমাহীন সময় ছিল, আর তাই D নিজেই decider হতে পারেনি। এই পর্বের D একটি নির্দিষ্ট বাজেটে চলে, তাই সে সবসময় থামে, আর তার language বাজেটের ভেতরে থাকে। কিন্তু সে কম বাজেটের প্রতিটি যন্ত্রের সঙ্গে অন্তত একটি input-এ দ্বিমত করে, তাই তার language কম বাজেটের বাইরে। Cantor-এর diagonal যুক্তির মূল ধারণা ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮-এ আছে।

পর্বের পরিকল্পনা: অংশ ২-এ “ভদ্র” সীমার সংজ্ঞা; অংশ ৩-এ space hierarchy-র পূর্ণ প্রমাণ আর Python-এ D-কে চালানো; অংশ ৪-এ time hierarchy আর log গুণক; অংশ ৫-এ অনুসিদ্ধান্ত; অংশ ৬-এ একটি স্বাভাবিক সমস্যা, যা প্রমাণিতভাবে কঠিন; অংশ ৭-এ এই পদ্ধতির সীমা।

২ · Constructible function — বাজেট নিজে মাপা যায় তো?

D-কে একটি বাজেট মেনে চলতে হবে: “f(n)টি ঘরের বেশি ব্যবহার করব না” বা “f(n) ধাপের বেশি চলব না”। কিন্তু বাজেট মানতে হলে আগে বাজেটের মাপটি জানতে হয়। f(n) হিসাব করতেই যদি f(n)-এর চেয়ে অনেক বেশি জায়গা বা সময় লাগে, তাহলে D বাজেট ভাঙবে বাজেট মাপতে গিয়েই। তাই আমরা শুধু এমন f নিই, যা নিজের বাজেটের মধ্যে মাপা যায়।

সংজ্ঞা ২.১ (Space-constructible function)

f: ℕ → ℕ, যেখানে f(n) ≥ log2 n (বড় n-এ), একটি space-constructible function, যদি এমন একটি Turing machine থাকে, যা input 1n পেয়ে f(n)-এর binary রূপ O(f(n)) জায়গায় লিখে থামে।

সংজ্ঞা ২.২ (Time-constructible function)

f: ℕ → ℕ, যেখানে f(n) ≥ n log2 n (বড় n-এ), একটি time-constructible function, যদি এমন একটি Turing machine থাকে, যা input 1n পেয়ে f(n)-এর binary রূপ O(f(n)) সময়ে লিখে থামে।

এখানে 1n মানে n-টি 1-এর একটি string, অর্থাৎ যন্ত্রকে শুধু দৈর্ঘ্যটি দেওয়া হচ্ছে। দুটি নিচের সীমা (log n আর n log n) প্রযুক্তিগত। Space-এর ক্ষেত্রে, পর্ব ৬৪-এর মতো, sublinear জায়গার জন্য আমরা দুই-tape model নিই: একটি read-only input tape আর একটি work tape, যার ঘরই শুধু গোনা হয় (L আর NL-এর জন্য এই model পর্ব ৬৬-এ বিস্তারিত)। Input-এ head-এর অবস্থান মনে রাখতেই log n bit লাগে, তাই log n-এর নিচে D নিজের হিসাবই রাখতে পারে না, আর প্রমাণটি সেখানে চলে না। সময়ের ক্ষেত্রে n log n আসে কারণ input পড়তেই n ধাপ লাগে, আর অংশ ৪-এর simulation-এ একটি log গুণক এমনিতেই ঢুকে পড়বে।

প্রায় প্রতিটি “স্বাভাবিক” function constructible. কয়েকটি উদাহরণ যাচাই করা যাক।

  • f(n) = n2 দুটিই। 1n গুনে n-কে binary-তে আনা যায় (একটি binary counter, log n bit), তারপর স্কুলের নিয়মে গুণ: জায়গা O(log n), সময় O(n log n) গোনার জন্য আর O(log2 n) গুণের জন্য; দুটিই n2-এর ভেতরে।
  • f(n) = 2n দুটিই। Binary রূপ হলো 1-এর পরে n-টি 0; লিখতে O(n) সময় আর জায়গা লাগে।
  • f(n) = ⌈log2 n⌉ space-constructible (counter-এর bit-সংখ্যাই উত্তর), কিন্তু time-constructible নয়, কারণ log n < n log n; শুধু input পড়তেই n ধাপ লাগে।
  • f(n) = n log2 n, n3, n · 2n, 22n: সবই time-constructible. যোগ, গুণ আর ঘাতে গড়া সব “পরিচিত” function এমন।

তাহলে শর্তটি কেন দরকার, যদি প্রায় সবই এতে পাশ করে? কারণ কৃত্রিম function-এর জন্য hierarchy সত্যিই ভেঙে পড়ে। ১৯৭২ সালে Allan Borodin-এর gap theorem (আলাদাভাবে আগে Boris Trakhtenbrot-এর কাজেও একই ধারণা ছিল বলে পরিচিত) বলে: যেকোনো computable function g, যেখানে g(n) ≥ n, নিলে এমন একটি computable f আছে, যাতে

TIME(f(n)) = TIME(g(f(n)))

অর্থাৎ g(x) = 2x নিলে TIME(f(n)) = TIME(2f(n)): সময় exponential হারে বাড়িয়েও একটি নতুন language পাওয়া যায় না! এমন f খুব অদ্ভুত, বিশেষভাবে বানানো, যাতে f(n) আর 2f(n)-এর মাঝখানে কোনো যন্ত্রের running time না পড়ে। এমন f নিজে O(f(n)) সময়ে হিসাব করা যায় না; constructible শর্ত ঠিক এই ফাঁকটি বন্ধ করে। ভাবনার প্রশ্ন ২-এ বিস্তারিত।

৩ · Space hierarchy theorem — diagonal যন্ত্র D

প্রথমে জায়গা, কারণ এর প্রমাণ পরিষ্কার আর গুণকের কোনো ঝামেলা নেই।

উপপাদ্য ৩.১ (Space hierarchy theorem; Stearns, Hartmanis আর Lewis, ১৯৬৫)

f যদি একটি space-constructible function হয়, তাহলে এমন একটি language A আছে, যা O(f(n)) জায়গায় decide হয়, কিন্তু o(f(n)) জায়গায় হয় না। অর্থাৎ g(n) = o(f(n)) হলে SPACE(g(n)) ⊊ SPACE(f(n)).

এখানে o মানে “কঠোরভাবে ধীরে বাড়ে”: g = o(f) মানে lim g(n)/f(n) = 0 (পর্ব ৫৭)। A-কে আমরা সরাসরি বর্ণনা করব না; A হবে একটি যন্ত্র D-এর language. D-এর কাজ দুটি: নিজে O(f(n)) জায়গায় থাকা, আর o(f(n)) জায়গার প্রতিটি যন্ত্রের সঙ্গে কোথাও দ্বিমত করা।

যন্ত্র D. “D = input w-এর ওপর:
১. n = |w|. f(n) হিসাব করা (space-constructible বলে O(f(n)) জায়গায়), আর work tape-এ f(n)টি ঘর চিহ্নিত করা। পরের কোনো ধাপ এই সীমার বাইরে যেতে চাইলে reject.
২. w যদি কোনো Turing machine M আর কোনো k ≥ 0-এর জন্য ⟨M⟩10k আকারের না হয়, reject.
৩. M-কে w-এর ওপর simulate করা, আর ধাপ গোনা। গোনা 22f(n) ছাড়ালে reject.
৪. M accept করলে reject; M reject করলে accept.”

তিনটি খুঁটিনাটি প্রমাণের প্রাণ। প্রথম, ⟨M⟩-এর পরের 10k অংশটি padding: একই যন্ত্র M-কে ইচ্ছামতো লম্বা input-এ পরীক্ষা করার উপায়। o(f) একটি asymptotic কথা, ছোট n-এ M হয়তো D-এর বাজেটের চেয়ে বেশি জায়গা নেয়; padding নিশ্চিত করে যে বড় n-এও M-এর একটি “প্রতিনিধি” input আছে। দ্বিতীয়, ধাপ ৩-এর counter D-কে decider বানায়: যে M একই জায়গায় চিরকাল ঘোরে, তাকেও D একসময় থামিয়ে দেয়। Counter-এর মান 22f(n) পর্যন্ত, তাই লিখতে লাগে 2f(n) + 1 bit, অর্থাৎ O(f(n)) জায়গা। তৃতীয়, ধাপ ৪-এর উল্টানো নিরাপদ, কারণ D নিজে deterministic আর সবসময় থামে।

নিচের stepper একটি খেলনা সংস্করণে D-কে চালায় (পরের Python ব্লকের সঙ্গে হুবহু মিলিয়ে)। বাজেট f(n) = n; D প্রতিটি simulated ঘরের জন্য নিজের ৪টি ঘর খরচ করে (চিহ্ন, head-এর দাগ ইত্যাদি)। M এখানে “square”: একটি unary counter i-কে 1, 2, 3, … করে বাড়ায় যতক্ষণ i2 < n, তাই সে প্রায় √n ঘর নেয়, আর accept করে যদি n একটি পূর্ণবর্গ হয়। তার code “10”.

1n = |w|; f(n) = n ঘর চিহ্নিত2w = ⟨M⟩10^k? নইলে reject3M simulate; 4 × ঘর > f(n)? reject4ধাপ > 2^(2f(n))? reject5M accept → reject; reject → accept
D-এর হিসাব
w
n = f(n)
M
D-এর দরকার
M(w), D(w)
  1. ধাপ ১, বাজেট। w = 101 আর তারপর ১৩টি 0, তাই n = 16. বাজেট f(16) = 16টি ঘর চিহ্নিত হলো। এর বাইরে যাওয়ার চেষ্টা মানেই reject.
  2. ধাপ ২, আকার পরীক্ষা। শেষের 0-গুলো আর তার আগের একটি 1 বাদ দিলে থাকে “10”, যা square যন্ত্রের code. তাই w = ⟨square⟩1013, বৈধ আকার।
  3. ধাপ ৩, simulation. square-এর counter i = 1, 2, 3, 4 (কারণ 42 = 16 আর আর বাড়ে না)। সর্বোচ্চ ৪টি ঘর, D-এর লাগে 4 × 4 = 16 ≤ 16. মাত্র ৪টি ধাপ, 232-এর অনেক নিচে।
  4. ধাপ ৪, উল্টানো। 16 পূর্ণবর্গ, তাই square accept করে। D তাই reject করে। এই w-এ D আর square দ্বিমত করল: w ∈ L(square) কিন্তু w ∉ L(D).
  5. Padding ছাড়া কী হতো। k = 0: w = 101, n = 3. square-এর প্রথম ধাপেই একটি ঘর, D-এর লাগে 4 > 3: বাজেট ফুরাল, D reject করে। square-ও reject করে (3 পূর্ণবর্গ নয়)। দুজন একমত, এই input-এ কোনো দ্বিমত হয়নি। ছোট n-এ বাজেট যথেষ্ট নয়।
  6. বড় k-তে সবসময় ধরে। k = 61: n = 64, square-এর ৮টি ঘর, D-এর লাগে 32 ≤ 64. square accept, D reject. যে যন্ত্র o(n) জায়গা নেয়, তার জন্য একটি সীমার পরে প্রতিটি k-তে simulation বাজেটে ধরে, আর D উল্টো উত্তর দেয়।

এবার প্রমাণটি পূর্ণ রূপে।

প্রমাণ। A = L(D) ধরুন।

  1. D একটি decider: ধাপ ১ আর ২ সসীম; ধাপ ৩ বড়জোর 22f(n) ধাপ simulate করে। তাই D প্রতিটি input-এ থামে। — counter-এর সীমা
  2. D-এর জায়গা: চিহ্নিত f(n)টি ঘর, আর counter-এর 2f(n) + 1 bit. ⟨M⟩ read-only input tape-এই পড়া যায়, কপি করতে হয় না। মোট O(f(n)), তাই A ∈ SPACE(f(n)). — space-constructibility আর ধাপ ১-এর সীমা
  3. বিপরীতে ধরুন, কোনো যন্ত্র M A-কে g(n) = o(f(n)) জায়গায় decide করে। D M-কে simulate করতে প্রতিটি M-ঘরের জন্য একটি ধ্রুবক d-সংখ্যক ঘর খরচ করে (M-এর tape-চিহ্নকে D-এর চিহ্নে encode করার দাম); d শুধু M-এর ওপর নির্ভর করে, n-এর ওপর নয়। — simulation-এর গঠন
  4. g = o(f), তাই এমন n0 আছে, যাতে n ≥ n0 হলে d · g(n) < f(n). অর্থাৎ বড় n-এ simulation বাজেটে ধরে। — o-এর সংজ্ঞা, c = 1/d নিয়ে
  5. M একটি decider আর g(n) জায়গা নেয়, তাই তার configuration বড়জোর q · (n + 2) · g(n) · γg(n)টি (q = state, n + 2 = input-head-এর অবস্থান, g(n) = work-head-এর অবস্থান, γ = tape-চিহ্নের সংখ্যা)। কোনো configuration দুবার এলে M চিরকাল ঘুরত, তাই M এর চেয়ে কম ধাপে থামে। এই সংখ্যার log হলো log(n + 2) + O(g(n)) ≤ f(n) + o(f(n)) + O(1), যা বড় n-এ 2f(n)-এর চেয়ে ছোট। তাই counter M-কে মাঝপথে থামায় না। — configuration গোনা, পর্ব ৬৪; f(n) ≥ log n
  6. এখন k এত বড় নিন, যাতে w = ⟨M⟩10k-এর দৈর্ঘ্য n ধাপ ৪ আর ৫-এর সব সীমা ছাড়ায়। এই w-এ D পুরো simulation শেষ করে আর M-এর উল্টো উত্তর দেয়: w ∈ A ⇔ w ∉ L(M). — padding
  7. কিন্তু ধরে নেওয়া হয়েছিল L(M) = A. বিরোধ। তাই কোনো o(f(n))-জায়গার যন্ত্র A decide করে না। ∎

একটি সতর্কতা: ধাপ ৩-এর সীমা আমরা 22f(n) নিয়েছি, 2f(n) নয়। কারণ ধাপ ৫: f(n) = log n-এর মতো ছোট বাজেটে M-এর configuration-সংখ্যায় input-head-এর অবস্থানের গুণক n + 2 আছে, আর 2log n = n সেটি পুরোপুরি ধরে না। Counter-এর bit দ্বিগুণ করলেও জায়গা O(f(n)) থাকে, তাই কিছু হারায় না। পাঠ্যবইয়ে এই খুঁটিনাটি নানাভাবে সামলানো হয়।

এবার Python-এ একটি খেলনা জগৎ বানিয়ে D-কে চালানো যাক। এখানে “যন্ত্র” হলো Python generator, যা প্রতিটি ধাপে জানায় সে এখন কয়টি work-ঘর ব্যবহার করছে; D সেই সংখ্যার ৪ গুণকে বাজেট f(n) = n-এর সঙ্গে মেলায়। পাঁচটি যন্ত্র: parity (১টি ঘর), balance (0 আর 1-এর পার্থক্যের binary counter, প্রায় log n ঘর), square (প্রায় √n ঘর), copy (n ঘর, পুরো input কপি করে) আর grow (কখনো থামে না, প্রতি ধাপে নতুন ঘর নেয়)। এটি Turing machine নয়, একটি model; কিন্তু D-এর যুক্তি হুবহু একই।

def parity(w, b=0):               # 1 work cell: running parity bit
    for c in w: b ^= (c == "1"); yield 1
    return b == 0                     # accept: even number of 1s
def balance(w, d=0):              # binary counter for #0 - #1
    for c in w: d += 1 if c == "0" else -1; yield abs(d).bit_length() + 1
    return d > 0                      # accept: more 0s than 1s
def square(w):                    # unary counter i up to sqrt(n)
    i = 0
    while i * i < len(w): i += 1; yield i
    return i * i == len(w)            # accept: n is a perfect square
def copy(w):                      # copies the whole input: n cells
    yield from range(1, len(w) + 1); return w == w[::-1]
def grow(w, i=0):                 # never halts, one new cell per step
    while True: i += 1; yield i
CODE = {"00": parity, "01": balance, "10": square, "11": copy, "000": grow}
def sim(M, w, budget, d=4):       # 4 cells of D per simulated cell
    run, steps = M(w), 0
    try:
        while True:
            cells = next(run); steps += 1
            if d * cells > budget: return None, f"space {d*cells}>{budget}"
            if steps > 2 ** (2 * budget): return None, "step counter"
    except StopIteration as e: return e.value, "simulated, flipped"
def D(w):                         # diagonal machine, budget f(n) = n
    body = w.rstrip("0")              # w must look like <M> 1 0^k
    if not body.endswith("1") or body[:-1] not in CODE: return False, "form"
    v, why = sim(CODE[body[:-1]], w, len(w))
    return v is False, why            # accept only if M rejected
print("M        n  D(w)   M(w)   D's reason")
for code, M in CODE.items():
    for k in (0, 13, 61):
        w = code + "1" + "0" * k; dv, why = D(w)
        mv = "loops" if M is grow else sim(M, w, float("inf"))[0]
        print(f"{M.__name__:7}{len(w):3}  {str(dv):6} {str(mv):6} {why}")

আসল আউটপুট (ব্রাউজারের Python):

M        n  D(w)   M(w)   D's reason
parity   3  False  False  space 4>3
parity  16  True   False  simulated, flipped
parity  64  True   False  simulated, flipped
balance  3  False  False  space 8>3
balance 16  False  True   space 20>16
balance 64  False  True   simulated, flipped
square   3  False  False  space 4>3
square  16  False  True   simulated, flipped
square  64  False  True   simulated, flipped
copy     3  False  True   space 4>3
copy    16  False  False  space 20>16
copy    64  False  False  space 68>64
grow     4  False  loops  space 8>4
grow    17  False  loops  space 20>17
grow    65  False  loops  space 68>65

সারণিটি প্রমাণের প্রতিটি ধাপ দেখায়। n = 3-এ কোনো যন্ত্রই বাজেটে ধরে না, আর parity, balance, square-এর ক্ষেত্রে D আর M একমত (দুজনই False): ছোট n-এ diagonalization কিছু প্রমাণ করে না। balance-এর counter একটু বড়, তাই n = 16-এও বাজেট ছাড়ায় (20 > 16); কেবল n = 64-এ সে ধরে, আর তখন D উল্টায়। এটিই padding-এর কাজ: প্রতিটি o(n)-জায়গার যন্ত্রের জন্য একটি “যথেষ্ট লম্বা” প্রতিনিধি থাকে। copy n ঘর নেয়, D-এর লাগে 4n > n, তাই কখনো ধরে না; এতে কোনো ক্ষতি নেই, কারণ copy o(n) নয়, তার সঙ্গে দ্বিমত দরকারও নেই। grow কখনো থামে না, কিন্তু D তবু থামে: বাজেট ফুরানো মাত্র reject. grow একই ঘরে ঘুরলে ধরত ধাপ-counter, যা এখানে দরকার পড়েনি। D-এর language নিজে বাজেট f(n) = n-এর ভেতরে, অথচ সারণির প্রতিটি o(n) যন্ত্র থেকে আলাদা।

৪ · Time hierarchy theorem — log গুণক কোথা থেকে আসে

সময়ের জন্য একই পরিকল্পনা: D-কে একটি সময়-বাজেট দেওয়া, প্রতিটি দ্রুত যন্ত্রকে simulate করা, উত্তর উল্টানো। কিন্তু একটি নতুন সমস্যা দেখা দেয়। জায়গার ক্ষেত্রে simulation-এর দাম ছিল একটি ধ্রুবক গুণক d, যা o(f)-এর ভেতরে হারিয়ে যায়। সময়ের ক্ষেত্রে এক-tape D-কে প্রতিটি simulated ধাপে একটি ধাপ-counter হালনাগাদ করতে হয়, আর সেই counter-কে tape-এর এক জায়গায় ফেলে রাখলে head-কে বারবার আসা-যাওয়া করতে হতো। এই দামই শেষে log f(n) গুণক হয়ে দাঁড়ায়।

উপপাদ্য ৪.১ (Time hierarchy theorem; Hartmanis আর Stearns, ১৯৬৫, এখানে Sipser-এর রূপে)

f যদি একটি time-constructible function হয়, তাহলে এমন একটি language A আছে, যা O(f(n)) সময়ে decide হয়, কিন্তু o(f(n)/log f(n)) সময়ে হয় না। অর্থাৎ g(n) = o(f(n)/log f(n)) হলে TIME(g(n)) ⊊ TIME(f(n)).

এখানে TIME মানে আগের মতো এক-tape deterministic Turing machine-এর সময় (পর্ব ৫৭)।

যন্ত্র D. “D = input w-এর ওপর:
১. n = |w|. f(n) হিসাব করা (time-constructible বলে O(f(n)) সময়ে), আর ⌈f(n)/log2 f(n)⌉ মানটি একটি binary counter-এ রাখা। ধাপ ৩ আর ৪-এর প্রতিটি simulated ধাপের আগে counter এক কমানো; 0 হলে reject.
২. w যদি ⟨M⟩10k আকারের না হয়, অথবা ⟨M⟩ log2 f(n)-এর চেয়ে লম্বা হয়, reject.
৩. M-কে w-এর ওপর simulate করা।
৪. M accept করলে reject; M reject করলে accept.”

ধাপ ২-এর দ্বিতীয় শর্তটি ছোট কিন্তু দরকারি: D প্রতিটি ধাপে ⟨M⟩-এর δ-সারণি দেখে, আর ⟨M⟩ বেশি লম্বা হলে সেই দেখার দামও বাড়ে। একটি নির্দিষ্ট M-এর ক্ষেত্রে |⟨M⟩| একটি ধ্রুবক, তাই বড় n-এ শর্তটি আপনা-আপনি পূরণ হয়। এবার মূল প্রশ্ন: এক-tape D কীভাবে M-এর একটি ধাপ simulate করে, আর তাতে কত খরচ? নিচের stepper সংখ্যা দিয়ে দেখায়, n = 1024 আর f(n) = n2 নিয়ে।

1counter = ⌈f/log f⌉2৩ track: tape, ⟨M⟩, counter3M-এর এক ধাপ: δ খোঁজা4বান্ডিল head-এর সঙ্গে সরানো5counter − 1; 0 হলে reject6মোট ≈ f/log f × log f
n = 1024, f(n) = n²
f(n), log f
counter
এক ধাপের দাম
D-এর মোট সময়
  1. বাজেট। n = 1024, f(n) = 1,048,576 = 220, তাই log2 f(n) = 20. Counter-এ রাখা হলো ⌈1,048,576/20⌉ = 52,429, binary-তে ১৬ bit (log f-এর চেয়ে কম)।
  2. Tape-এর বিন্যাস। এক tape-কে তিন track-এ ভাগ করা হয় (পর্ব ৪৫-এর multi-track কৌশল)। Track ১-এ M-এর tape. Track ২-এ M-এর বর্তমান state আর ⟨M⟩-এর একটি কপি, track ৩-এ counter. Track ২ আর ৩-এর তথ্য একটি “বান্ডিল”, যা সবসময় M-এর head-এর ঠিক পাশে থাকে।
  3. M-এর একটি ধাপ। D head-এর নিচের চিহ্ন পড়ে, পাশের ⟨M⟩-এ মিলে যাওয়া নিয়ম খোঁজে, চিহ্ন লেখে আর state বদলায়। দাম cM, যা শুধু |⟨M⟩|-এর ওপর নির্ভর করে; একটি নির্দিষ্ট M-এর জন্য ধ্রুবক।
  4. বান্ডিল সরানো। M-এর head এক ঘর সরলে বান্ডিলকেও এক ঘর সরাতে হয়, নইলে পরের ধাপে D-কে দূরে গিয়ে counter আনতে হতো। বান্ডিলের দৈর্ঘ্য |⟨M⟩| + counter-এর ১৬ bit, অর্থাৎ O(log f(n)); সরানোর দাম এর সমানুপাতিক।
  5. Counter কমানো। 52,429 থেকে 52,428. Binary-তে এক কমানো বড়জোর ১৬টি bit ছোঁয়, আর counter বান্ডিলের ভেতরেই আছে। এক simulated ধাপের মোট দাম cM + O(log f(n)).
  6. মোট হিসাব। Counter 0-তে পৌঁছানো পর্যন্ত 52,429টি simulated ধাপ, প্রতিটি প্রায় 20 একক: মোট প্রায় 1,048,580, অর্থাৎ O(f(n)). উল্টোভাবে বললে, O(f(n)) বাজেটে D M-এর মাত্র প্রায় f(n)/log f(n)টি ধাপ simulate করতে পারে। তাই উপপাদ্য শুধু o(f(n)/log f(n)) সময়ের যন্ত্রের বিরুদ্ধে কাজ করে।

প্রমাণ। A = L(D) ধরুন।

  1. D-এর সময়: ধাপ ১ O(f(n)) (time-constructibility; ভাগফল হিসাব এর মধ্যেই সারা যায়)। ধাপ ২ input একবার পড়ে, O(n) ≤ O(f(n)). ধাপ ৩ বড়জোর ⌈f(n)/log f(n)⌉টি ধাপ simulate করে, প্রতিটি O(log f(n)) দামে, কারণ |⟨M⟩| ≤ log f(n). মোট O(f(n)), তাই A ∈ TIME(f(n)). — stepper-এর হিসাব
  2. D সবসময় থামে, কারণ counter সসীম; তাই A decidable আর উল্টানো নিরাপদ। — D একটি decider
  3. বিপরীতে ধরুন, এক-tape যন্ত্র M A-কে g(n) = o(f(n)/log f(n)) সময়ে decide করে। তাহলে এমন n0 আছে, যাতে n ≥ n0 হলে g(n) < ⌈f(n)/log f(n)⌉ আর |⟨M⟩| ≤ log f(n). — o-এর সংজ্ঞা; f(n) ≥ n log n বলে log f(n) → ∞
  4. k বড় নিয়ে w = ⟨M⟩10k, |w| ≥ n0. ধাপ ২ পাশ করে, আর counter শেষ হওয়ার আগেই M থামে। D M-এর উল্টো উত্তর দেয়: w ∈ A ⇔ w ∉ L(M). — padding
  5. L(M) = A-এর সঙ্গে বিরোধ। তাই কোনো o(f(n)/log f(n))-সময়ের এক-tape যন্ত্র A decide করে না। ∎

log গুণকটি তাহলে প্রকৃতির নিয়ম নয়, প্রমাণের একটি দাম। Multi-tape যন্ত্রে counter-কে আলাদা tape-এ রাখা যায়, তাই সরানোর দাম লাগে না। কিন্তু তখন অন্য সমস্যা: D-এর tape-সংখ্যা স্থির, অথচ M-এর tape যত খুশি থাকতে পারে, তাই D-কে অনেক tape কম tape-এ simulate করতে হয়। Hennie আর Stearns ১৯৬৬ সালে দেখান বলে পরিচিত, যেকোনো t(n)-সময়ের k-tape যন্ত্রকে একটি দুই-tape যন্ত্র O(t(n) log t(n)) সময়ে simulate করে। এখান থেকে multi-tape যন্ত্রের জন্যও একটি log গুণকসহ hierarchy আসে: g(n) log g(n) = o(f(n)) হলে TIME(g) ⊊ TIME(f). আরও সূক্ষ্ম ফল আছে (স্থির tape-সংখ্যার যন্ত্রে log গুণক ছাড়াই hierarchy, Fürer ১৯৮২ সালের কাজ বলে পরিচিত), কিন্তু সেগুলো এই কোর্সের বাইরে।

log গুণকের বাস্তব অর্থ কী? সব জোড়া সময়-সীমা এই উপপাদ্য দিয়ে আলাদা হয় না। নিচের JavaScript ব্লক কয়েকটি জোড়ার জন্য অনুপাত g(n) / (f(n)/log f(n)) হিসাব করে; অনুপাত 0-এর দিকে গেলে উপপাদ্য TIME(g) ⊊ TIME(f) দেয়, না গেলে দেয় না। বড় সংখ্যার overflow এড়াতে হিসাব log2-এ।

// Time hierarchy test: TIME(g) ⊊ TIME(f) is guaranteed when
// g(n) / (f(n) / log f(n)) -> 0. We work with log2 values to avoid overflow.
const lg = Math.log2;
const pairs = [                       // [g, f, log2 g(n), log2 f(n)]
  ["n^2", "n^2 log n",   n => 2 * lg(n), n => 2 * lg(n) + lg(lg(n))],
  ["n^2", "n^2 log^2 n", n => 2 * lg(n), n => 2 * lg(n) + 2 * lg(lg(n))],
  ["n^2", "n^3",         n => 2 * lg(n), n => 3 * lg(n)],
  ["2^n", "n 2^n",       n => n,         n => n + lg(n)],
  ["2^n", "2^(2n)",      n => n,         n => 2 * n],
];
const ns = [2 ** 4, 2 ** 8, 2 ** 16, 2 ** 32];
console.log("ratio g / (f / log f) at n = 2^4, 2^8, 2^16, 2^32");
for (const [g, f, LG, LF] of pairs) {
  const r = ns.map(n => 2 ** (LG(n) - LF(n) + lg(LF(n))));
  console.log(`${g.padEnd(4)} vs ${f.padEnd(12)}` +
              r.map(x => x.toExponential(2).padStart(10)).join(""));
}
// The plain growth of three functions, for comparison.
console.log("\n     n         n^2     n^2 log n           2^n");
for (const n of [10, 20, 40, 80]) {
  console.log(String(n).padStart(6), (n * n).toExponential(2).padStart(11),
    (n * n * lg(n)).toExponential(2).padStart(13),
    (2 ** n).toExponential(2).padStart(13));
}

আসল আউটপুট (ব্রাউজারের JavaScript):

ratio g / (f / log f) at n = 2^4, 2^8, 2^16, 2^32
n^2  vs n^2 log n      2.50e+0   2.37e+0   2.25e+0   2.16e+0
n^2  vs n^2 log^2 n    7.50e-1   3.44e-1   1.56e-1   7.23e-2
n^2  vs n^3            7.50e-1   9.38e-2   7.32e-4   2.24e-8
2^n  vs n 2^n          1.25e+0   1.03e+0   1.00e+0   1.00e+0
2^n  vs 2^(2n)         4.88e-4  4.42e-75   0.00e+0   0.00e+0

     n         n^2     n^2 log n           2^n
    10     1.00e+2       3.32e+2       1.02e+3
    20     4.00e+2       1.73e+3       1.05e+6
    40     1.60e+3       8.52e+3      1.10e+12
    80     6.40e+3       4.05e+4      1.21e+24

প্রথম সারি সবচেয়ে শিক্ষণীয়: n2 বনাম n2 log n-এ অনুপাত 2-এর দিকে যায়, 0-এর দিকে নয় (আসলে log f / log n = (2 log n + log log n)/log n → 2). তাই এই উপপাদ্য TIME(n2) ⊊ TIME(n2 log n) প্রমাণ করে না; এটি সত্য কি না, তা অন্য যুক্তির প্রশ্ন। একটি log বেশি দিলে (দ্বিতীয় সারি) অনুপাত ধীরে কিন্তু নিশ্চিতভাবে 0-এর দিকে নামে: TIME(n2) ⊊ TIME(n2 log2 n). n2 বনাম n3 দ্রুত 0. চতুর্থ সারিতে 2n বনাম n · 2n-এর অনুপাত 1-এ থামে: আলাদা হয় না। শেষ সারির অনুপাত 2n/2n; n = 216-এ এত ছোট যে double সংখ্যায় 0 হয়ে যায়। নিচের সারণি মনে করিয়ে দেয়, n2 আর n2 log n কাছাকাছি থাকে, অথচ 2n দ্রুত সবাইকে ছাড়িয়ে যায়।

৫ · অনুসিদ্ধান্ত — NL ⊊ PSPACE, P ⊊ EXP আর আরও

দুটি উপপাদ্যকে আগের পর্বগুলোর অন্তর্ভুক্তির সঙ্গে জুড়লে অনেকগুলো কঠোর পার্থক্য বেরিয়ে আসে। প্রথমে সরলগুলো।

অনুসিদ্ধান্ত ৫.১ (polynomial সিঁড়ি)

১. যেকোনো দুটি যুক্তিসংগত সংখ্যা 0 ≤ a < b-এর জন্য SPACE(na) ⊊ SPACE(nb).
২. যেকোনো দুটি যুক্তিসংগত সংখ্যা 1 ≤ a < b-এর জন্য TIME(na) ⊊ TIME(nb).

প্রমাণ। ১: nb space-constructible আর na = o(nb); উপপাদ্য ৩.১. ২: nb time-constructible, আর na / (nb / (b log n)) = b log n / nb − a → 0; উপপাদ্য ৪.১. ∎ অর্থাৎ P-এর ভেতরে অসীম সিঁড়ি: TIME(n) ⊊ TIME(n2) ⊊ TIME(n3) ⊊ … P একটি একক “দক্ষ” স্তর নয়, অসীম স্তরের মিলন।

অনুসিদ্ধান্ত ৫.২

NL ⊊ PSPACE, আর তাই L ⊊ PSPACE.

প্রমাণ।

  1. NL = NSPACE(log n) ⊆ SPACE(log2 n). — Savitch-এর theorem, পর্ব ৬৪; log n ≥ log n শর্ত পূরণ হয়
  2. log2 n = o(n), আর n space-constructible, তাই SPACE(log2 n) ⊊ SPACE(n). — উপপাদ্য ৩.১
  3. SPACE(n) ⊆ PSPACE. — সংজ্ঞা
  4. জুড়ে দিলে NL ⊆ SPACE(log2 n) ⊊ SPACE(n) ⊆ PSPACE. আর L ⊆ NL. ∎

এবার সবচেয়ে বিখ্যাতটি, ধাপে ধাপে। EXP = ⋃k TIME(2nk).

1P ⊆ TIME(2^n)2f(n) = 2^(2n) time-constructible32^n = o(2^(2n) / log 2^(2n))?4TIME(2^n) ⊊ TIME(2^(2n))5TIME(2^(2n)) ⊆ EXP6P ⊊ EXP ∎
দাবি আর সংখ্যায় যাচাই
দাবি
সংখ্যায়
  1. P ⊆ TIME(2n). প্রতিটি স্থির k-এর জন্য nk = O(2n), তাই TIME(nk) ⊆ TIME(2n). n = 100-এ 1003 = 106, আর 2100 প্রায় 1.27 × 1030.
  2. বাজেট constructible. f(n) = 22n-এর binary রূপ 1-এর পরে 2n-টি 0; n = 10-এ ২১ অঙ্কের string. লিখতে O(n) সময়, যা O(f(n))-এর অনেক নিচে।
  3. log গুণকের শর্ত। log2 f(n) = 2n, তাই 2n / (22n/2n) = 2n/2n. n = 10-এ 0.0195, n = 20-এ প্রায় 3.81 × 10−5; 0-এর দিকে যায়। শর্ত পূরণ।
  4. উপপাদ্য প্রয়োগ। উপপাদ্য ৪.১ থেকে এমন language L আছে, যা TIME(22n)-এ আছে কিন্তু TIME(2n)-এ নেই।
  5. EXP-এর ভেতরে। n ≥ 2 হলে 2n ≤ n2, তাই TIME(22n) ⊆ TIME(2n2) ⊆ EXP. n = 10-এ 20 ≤ 100.
  6. শৃঙ্খল জোড়া। P ⊆ TIME(2n) ⊊ TIME(22n) ⊆ EXP. L ∈ EXP, কিন্তু L ∉ TIME(2n) ⊇ P, তাই L ∉ P. অতএব P ⊊ EXP. ∎

একই কৌশলে EXPSPACE = ⋃k SPACE(2nk)-এর জন্য PSPACE ⊆ SPACE(2n) ⊊ SPACE(22n) ⊆ EXPSPACE, অর্থাৎ PSPACE ⊊ EXPSPACE. নিচের ছবি পুরো শৃঙ্খলে কী জানা আর কী অজানা, তা একসঙ্গে দেখায়।

শ্রেণির শৃঙ্খল — hierarchy theorem কী আলাদা করে

বাঁয়ে শৃঙ্খল: প্রতিটি ⊆ প্রমাণিত, কিন্তু আলাদাভাবে কঠোর কি না অজানা। ডানের রঙিন বন্ধনী: বন্ধনীর দুই প্রান্ত আলাদা (≠), অর্থাৎ ভেতরের অন্তত একটি ধাপ কঠোর, প্রমাণিত।

Inclusion chain with the separations proved by hierarchy theorems L NL P NP PSPACE EXP EXPSPACE ⊆ ? ⊆ ? ⊆ ? ⊆ ? ⊆ ? ⊆ ? ≠ ≠ ≠ NL ≠ PSPACE: space + Savitch P ≠ EXP: time hierarchy PSPACE ≠ EXPSPACE: space প্রতিটি একক “⊆ ?”: অজানা
ছবি ৬৭.১ — নীল বন্ধনী: NL ⊊ PSPACE, তাই NL ⊆ P ⊆ NP ⊆ PSPACE-এর তিন ধাপের অন্তত একটি কঠোর। সবুজ: P ⊊ EXP, তাই P ⊆ NP ⊆ PSPACE ⊆ EXP-এর অন্তত একটি। বেগুনি: PSPACE ⊊ EXPSPACE. কোন নির্দিষ্ট ধাপ কঠোর, তা আজও কেউ জানে না; বেশিরভাগ গবেষক মনে করেন সবগুলোই কঠোর, কিন্তু প্রমাণিত নয়।

ছবির একটি কৌতূহলী দিক: আমরা জানি P ≠ EXP, কিন্তু জানি না P ≠ PSPACE, যদিও PSPACE অনেক “ছোট”। কারণ hierarchy theorem একই ধরনের সম্পদ তুলনা করে: সময়ের সঙ্গে সময়, জায়গার সঙ্গে জায়গা। P (সময়) আর PSPACE (জায়গা) আলাদা সম্পদ, তাই উপপাদ্য সেখানে কিছু বলে না। নিচের সারণিতে কিছু জোড়ার অবস্থা।

জোড়াঅবস্থাকেন
SPACE(log n) বনাম SPACE(log2 n)কঠোর, প্রমাণিতspace hierarchy
TIME(n2) বনাম TIME(n3)কঠোর, প্রমাণিতtime hierarchy
TIME(n2) বনাম TIME(n2 log n)এই উপপাদ্য থেকে আসে নাlog গুণক খেয়ে ফেলে
NL বনাম PSPACE; P বনাম EXPকঠোর, প্রমাণিতঅনুসিদ্ধান্ত ৫.২, stepper
NP বনাম NEXPকঠোর, প্রমাণিতnondeterministic time hierarchy (অংশ ৭)
L বনাম P; P বনাম NP; P বনাম PSPACEঅজানাআলাদা সম্পদ বা আলাদা mode

৬ · প্রমাণিতভাবে কঠিন একটি স্বাভাবিক সমস্যা — ঘাতসহ regex

Hierarchy theorem-এর A একটি কৃত্রিম language: “যন্ত্রের বর্ণনা নিয়ে উল্টো উত্তর দাও”। কেউ বাস্তবে এমন প্রশ্ন জিজ্ঞাসা করে না। তাহলে কি এই উপপাদ্য শুধু তাত্ত্বিক কৌতূহল? না, কারণ completeness-এর সঙ্গে মিলিয়ে এটি স্বাভাবিক সমস্যার কাঠিন্য প্রমাণ করে। যুক্তিটি সাধারণ: কোনো সমস্যা B যদি EXPSPACE-complete হয়, আর B ∈ PSPACE হতো, তাহলে EXPSPACE-এর প্রতিটি সমস্যা polynomial সময়ে B-তে নেমে PSPACE-এ চলে আসত, অর্থাৎ EXPSPACE ⊆ PSPACE, যা PSPACE ⊊ EXPSPACE-এর বিরোধী। তাই B ∉ PSPACE, আর P ⊆ PSPACE বলে B ∉ P-ও। (একই যুক্তিতে, TQBF-এর মতো PSPACE-complete সমস্যা, পর্ব ৬৫, P-তে থাকলে P = PSPACE হতো; কিন্তু P ≠ PSPACE প্রমাণিত নয় বলে সেখানে এই যুক্তি শর্তহীন কাঠিন্য দেয় না।) কোনো অপ্রমাণিত অনুমান ছাড়াই।

বাজারঘরের একটি বাস্তব প্রশ্ন দিয়ে শুরু করা যাক। Admin-রা কুপনের নিয়ম regular expression দিয়ে লেখেন, আর বাস্তব regex-এ গোনা পুনরাবৃত্তি থাকে: [0-9]{4} মানে ঠিক চারটি অঙ্ক। দুজন admin দুটি নিয়ম লিখলেন; সিস্টেম জানতে চায় দুটি নিয়ম একই কুপনগুলো গ্রহণ করে কি না। এটি regex equivalence-এর প্রশ্ন। সাধারণ regex-এ (∪, concatenation, ∗) এটি PSPACE-complete বলে পরিচিত (Meyer আর Stockmeyer, ১৯৭২–৭৩; পর্ব ২০)। গোনা পুনরাবৃত্তি যোগ করলে কী হয়?

সংজ্ঞা ৬.১ (ঘাতসহ regex)

সাধারণ regex-এর সঙ্গে একটি নতুন operation: R↑k মানে R-এর k-টি কপি পরপর, যেখানে k binary-তে লেখা। এমন expression-কে বলা হয় exponentiation-সহ regex. তারপর

EQREX↑ = { ⟨Q, R⟩ : Q আর R ঘাতসহ regex, আর L(Q) = L(R) }

↑ language-এর শ্রেণি বদলায় না (R↑k-কে R R … R লিখে ফেলা যায়, ফল এখনো regular). বদলায় শুধু সংক্ষেপের মাত্রা: k লিখতে লাগে log k bit, কিন্তু কপি k-টি। ঘাতের ওপর ঘাত বসালে এই ফাঁক exponential হয়ে যায়। নিচের Python ব্লক দুটি জিনিস দেখায়: লেখা দৈর্ঘ্য বনাম খোলা দৈর্ঘ্য, আর ছোট দৈর্ঘ্য পর্যন্ত দুটি expression-এর brute-force তুলনা। এখানে “দৈর্ঘ্য” মানে চিহ্ন আর operator-এর সংখ্যা, ঘাত binary-তে গোনা।

S = lambda a: ("sym", a); E = ("eps",)          # regex with ↑ as tuples
Or = lambda a, b: ("or", a, b); Cat = lambda a, b: ("cat", a, b)
Star = lambda a: ("star", a); Pow = lambda a, k: ("pow", a, k)
def written(R):                   # length as written, exponent in binary
    if R[0] in ("sym", "eps"): return 1
    if R[0] == "pow": return written(R[1]) + R[2].bit_length() + 1
    return sum(written(x) for x in R[1:]) + 1
def expanded(R):                  # length after replacing A↑k by A A ... A
    if R[0] in ("sym", "eps"): return 1
    if R[0] == "pow": return R[2] * expanded(R[1]) + R[2] - 1
    return sum(expanded(x) for x in R[1:]) + 1
def cat(X, Y, L): return {x + y for x in X for y in Y if len(x + y) <= L}
def lang(R, L):                   # all strings of length <= L in L(R)
    op = R[0]
    if op == "sym": return {R[1]}
    if op == "eps": return {""}
    if op == "or": return lang(R[1], L) | lang(R[2], L)
    if op == "cat": return cat(lang(R[1], L), lang(R[2], L), L)
    A, T = lang(R[1], L), {""}
    if op == "pow":
        for _ in range(R[2]): T = cat(T, A, L)
    else:
        for _ in range(L + 1): T |= cat(T, A, L)
    return T
print(" m  written  expanded   (R_m = ((0 ∪ 1)↑2)↑2 ... m times)")
R = Or(S("0"), S("1"))
for m in range(1, 33):
    R = Pow(R, 2)
    if m in (1, 2, 4, 8, 16, 32): print(f"{m:2} {written(R):8} {expanded(R):9}")
X = Star(Or(Pow(S("0"), 2), Pow(S("0"), 3)))
for Y in (Or(E, Cat(Pow(S("0"), 2), Star(S("0")))), Star(Pow(S("0"), 2))):
    a, b = lang(X, 10), lang(Y, 10)
    bad = sorted(a ^ b, key=lambda s: (len(s), s))
    print("equal up to length 10:", not bad, "| first difference:", bad[:1])

আসল আউটপুট (ব্রাউজারের Python):

 m  written  expanded   (R_m = ((0 ∪ 1)↑2)↑2 ... m times)
 1        6         7
 2        9        15
 4       15        63
 8       27      1023
16       51    262143
32       99 17179869183
equal up to length 10: True | first difference: []
equal up to length 10: False | first difference: ['000']

Rm হলো (0 ∪ 1)-এর ওপর m-বার “↑2”, অর্থাৎ ঠিক 2m দৈর্ঘ্যের সব binary string. লেখা দৈর্ঘ্য 3m + 3, রৈখিক; খোলা দৈর্ঘ্য 4 · 2m − 1, exponential. m = 32-এ ৯৯টি চিহ্নের একটি expression খুললে প্রায় ১৭০০ কোটি চিহ্ন। শেষ দুই লাইনে X = (0↑2 ∪ 0↑3)∗, যা 1 ছাড়া প্রতিটি দৈর্ঘ্যের 0-string গ্রহণ করে। X আর ε ∪ 0↑20∗ দৈর্ঘ্য ১০ পর্যন্ত মেলে (আসলে সব দৈর্ঘ্যে সমান)। X আর (0↑2)∗ মেলে না; প্রথম পার্থক্য 000. মনে রাখবেন, একটি সীমা পর্যন্ত মেলানো decider নয়: সমতা প্রমাণ হয় না, শুধু পার্থক্য পাওয়া গেলে অসমতা প্রমাণ হয়।

উপপাদ্য ৬.২ (Meyer আর Stockmeyer, ১৯৭২; Sipser-এর রূপে)

EQREX↑ EXPSPACE-complete. ফলে EQREX↑ ∉ PSPACE, আর তাই EQREX↑ ∉ P.

প্রমাণের রূপরেখা। দুই অংশ।

  1. EQREX↑ ∈ EXPSPACE. সব ↑ খুলে ফেলা: দৈর্ঘ্য বড়জোর 2O(n)-এর ক্রমে (উপরের সারণির মতো)। তারপর সাধারণ regex-এর equivalence, যা expression-এর দৈর্ঘ্যের polynomial জায়গায় সমাধান হয় (দুটি NFA-র state-সেট একসঙ্গে মনে রেখে একটি পার্থক্যকারী string খোঁজা, nondeterministically, তারপর Savitch; পর্ব ২০, ৬৪)। Exponential দৈর্ঘ্যের polynomial = exponential জায়গা। — খুলে ফেলার দাম
  2. EXPSPACE-hardness. ধরুন M একটি যন্ত্র, যা 2nk জায়গায় চলে, আর w একটি input. একটি ঘাতসহ regex R বানানো হয়, যা ঠিক সেইসব string বর্ণনা করে, যারা M-এর w-এর ওপর accepting computation history নয়। একটি string ভুল হতে পারে তিনভাবে: শুরু ভুল, শেষে accept নেই, অথবা কোথাও পরপর দুটি configuration-এর মধ্যে একটি অবৈধ পরিবর্তন। তৃতীয় শর্তে “একটি ঘর আর ঠিক 2nk ঘর পরের ঘর” তুলনা করতে হয়; ↑ দিয়ে সেই দূরত্ব লেখা যায় O(nk) চিহ্নে। তাই R-এর দৈর্ঘ্য polynomial, আর M w-কে accept করে না ⇔ L(R) = Δ∗ (Δ = history-র সব চিহ্ন)। EXPSPACE complement-এ বদ্ধ, তাই এখান থেকে EXPSPACE-এর প্রতিটি সমস্যা EQREX↑-এ polynomial সময়ে নামে। — computation history-র কৌশল, পর্ব ৫৪-এর মতো
  3. শেষে PSPACE ⊊ EXPSPACE (অংশ ৫) আর উপরের সাধারণ যুক্তি: EQREX↑ ∉ PSPACE ⊇ P. ∎

বাজারঘরের জন্য অর্থ: কুপন-নিয়মে {1000}-এর মতো গোনা পুনরাবৃত্তি বসতে দিলে, দুটি নিয়ম সমান কি না তা যাচাই করার এমন কোনো algorithm নেই, যা সব input-এ polynomial জায়গায় চলে; এটি অনুমান নয়, প্রমাণিত। বাস্তবে নিয়মগুলো ছোট আর সরল হয়, তাই যন্ত্র সাধারণত দ্রুত উত্তর দেয়। কিন্তু worst case-এর বিস্ফোরণ নকশার ত্রুটি নয়, সমস্যার প্রকৃতি। প্রকৌশলীর কাজ সীমা বসানো: ঘাতের মাপে সীমা, সময়সীমা, আর “নিশ্চিত নই” উত্তরের ব্যবস্থা।

৭ · Hierarchy theorem কী পারে না — P বনাম NP আর relativization

এত শক্তিশালী একটি কৌশল দিয়ে P ≠ NP কেন প্রমাণ হয় না? তিনটি স্তরে উত্তর।

এক, ভুল তুলনা। Hierarchy theorem বলে “একই ধরনের যন্ত্রকে বেশি সম্পদ দিলে বেশি পারে”। P আর NP-তে সম্পদ একই (polynomial সময়), কিন্তু যন্ত্রের ধরন আলাদা: deterministic বনাম nondeterministic. P আর PSPACE-এ যন্ত্রের ধরন একই, কিন্তু সম্পদ আলাদা: সময় বনাম জায়গা। দুই ক্ষেত্রেই “বেশি একই জিনিস” নেই, তাই উপপাদ্য প্রযোজ্য নয়।

দুই, nondeterminism-এ উল্টানো কঠিন। Nondeterministic সময়ের জন্যও hierarchy আছে, কিন্তু প্রমাণ অনেক সূক্ষ্ম। কারণ D-এর ধাপ ৪, “M accept করলে reject”, একটি NTM-এর জন্য সস্তা নয়: NTM-এর উত্তর উল্টাতে সব শাখা দেখতে হয়, যা সাধারণত exponential দাম (এই দামই NP বনাম coNP প্রশ্নের কেন্দ্রে, পর্ব ৬২)। Stephen Cook ১৯৭২ সালে polynomial সীমার জন্য প্রথম ফল দেন, আর পরে Seiferas, Fischer আর Meyer (১৯৭৮) এবং Žák (১৯৮৩) “lazy diagonalization” নামের কৌশলে সাধারণ রূপ দেন বলে পরিচিত। ফলটি nondeterministic time hierarchy theorem: g time-constructible আর f(n + 1) = o(g(n)) হলে NTIME(f(n)) ⊊ NTIME(g(n)). এর একটি অনুসিদ্ধান্ত NP ⊊ NEXP. কিন্তু এটিও deterministic আর nondeterministic-এর তুলনা নয়।

তিন, relativization. সবচেয়ে গভীর কারণটি পর্ব ৬৩-এ দেখেছেন। একটি oracle Turing machine চলার মাঝে এক ধাপে জেনে নিতে পারে, একটি string একটি নির্দিষ্ট language O-এর সদস্য কি না। হিসাব করে দেখুন, এই পর্বের প্রতিটি প্রমাণ শুধু দুটি কাজ করে: অন্য যন্ত্রকে simulate করা আর উত্তর উল্টানো। সবার হাতে একই oracle থাকলে D-ও oracle-এর প্রশ্ন simulate করতে পারে (নিজেই একই প্রশ্ন oracle-কে করে)। তাই প্রমাণ হুবহু চলে, আর প্রতিটি O-এর জন্য PO ⊊ EXPO. এমন প্রমাণকে বলে relativizing. কিন্তু Baker, Gill আর Solovay ১৯৭৫ সালে দেখান, এমন oracle A আছে যাতে PA = NPA, আবার এমন B আছে যাতে PB ≠ NPB. যে প্রমাণ সব oracle-জগতে চলে, সে এই দুই জগতে দুই রকম উত্তর দিতে পারে না।

উপসংহার ৭.১ (relativization-এর বাধা)

শুধু simulation আর উল্টানো দিয়ে গড়া, অর্থাৎ relativize করে এমন কোনো প্রমাণ P = NP বা P ≠ NP কোনোটিই প্রমাণ করতে পারে না। Hierarchy theorem-এর প্রমাণ relativize করে।

এর মানে diagonalization অকেজো নয়; মানে, P বনাম NP-এর জন্য একে এমন কোনো উপাদানের সঙ্গে মেলাতে হবে, যা oracle-এর সামনে ভেঙে পড়ে। পর্ব ৬৮-এ oracle আর polynomial hierarchy আরও কাছ থেকে দেখবেন।

আরেকটি সূক্ষ্ম বিষয়: hierarchy theorem একটি অস্তিত্বের কথা বলে। “TIME(n3)-এ এমন language আছে, যা TIME(n2)-এ নেই” সত্য, কিন্তু কোনো পরিচিত স্বাভাবিক সমস্যা, যেমন দুটি n × n matrix গুণ বা কোনো graph-এর triangle খোঁজা, n2 সময়ে করা যায় না, এমন প্রমাণ এখান থেকে আসে না। স্বাভাবিক সমস্যার নিম্নসীমা প্রমাণ এখনো complexity তত্ত্বের সবচেয়ে কঠিন কাজগুলোর একটি; পর্ব ৭২-এর fine-grained complexity এই ফাঁকে কাজ করে, প্রমাণের বদলে অনুমান আর reduction দিয়ে।

আরও গভীরে: Hierarchy-র উল্টো দিকে দুটি অদ্ভুত ফল আছে। Borodin-এর gap theorem (১৯৭২) বলে, constructible নয় এমন সীমায় সময় বিশাল পরিমাণে বাড়িয়েও নতুন কিছু না-ও মিলতে পারে; আর Manuel Blum-এর speedup theorem (১৯৬৭) বলে, এমন decidable language আছে যার কোনো “সবচেয়ে দ্রুত” algorithm নেই, প্রতিটির চেয়ে অনেক দ্রুত আরেকটি থাকে (প্রায় সব input-এ)। দুটিই কৃত্রিমভাবে বানানো উদাহরণ দিয়ে প্রমাণিত, আর দুটিই দেখায় যে “একটি সমস্যার complexity” ধারণাটি সব ক্ষেত্রে একটি সংখ্যায় ধরা যায় না। জায়গার নিচের প্রান্তে আরেকটি পরিচিত ফল: o(log log n) জায়গায় decide হওয়া প্রতিটি language regular বলে ১৯৬০-এর দশকের কাজ থেকে জানা।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Space hierarchy theorem বিবৃত করুন। f space-constructible হলে এমন A আছে, যা O(f(n)) জায়গায় decide হয় কিন্তু o(f(n)) জায়গায় নয়।
  • Time hierarchy-তে log গুণক কেন? এক-tape D-কে প্রতিটি simulated ধাপে O(log f(n)) দৈর্ঘ্যের counter head-এর সঙ্গে সরাতে হয়।
  • P ⊊ EXP প্রমাণ করুন। P ⊆ TIME(2n) ⊊ TIME(22n) ⊆ EXP, কারণ 2n = o(22n/2n).
  • NL ⊊ PSPACE কীভাবে? Savitch: NL ⊆ SPACE(log2 n); space hierarchy: ⊊ SPACE(n) ⊆ PSPACE.
  • Diagonalization দিয়ে P ≠ NP কেন হয় না? প্রমাণটি relativize করে, অথচ PA = NPA আর PB ≠ NPB দুই রকম oracle আছে (Baker–Gill–Solovay).

৮ · AI-এর যুগে hierarchy theorem

AI assistant-কে hierarchy theorem জিজ্ঞাসা করলে সাধারণত সুন্দর একটি অনুচ্ছেদ আসে। কিন্তু এই বিষয়ের প্রতিটি শর্ত প্রমাণের এক একটি খুঁটি, আর ঠিক সেগুলোই সবচেয়ে বেশি হারায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Constructible শর্ত বাদ দিয়ে “f = o(g) হলেই TIME(f) ⊊ TIME(g)”Gap theorem মনে করুন; শর্তসহ বিবৃতি Sipser বা Arora–Barak-এ মিলিয়ে নিন
Time hierarchy-তে log গুণক ভুলে যাওয়া, যেমন “TIME(n2) ⊊ TIME(n2 log n) এই উপপাদ্য থেকে”g / (f / log f) অনুপাত নিজে হিসাব করুন; 0-এর দিকে না গেলে দাবি এখান থেকে আসে না
“Hierarchy theorem দেখায় P ≠ NP” বা “P ≠ PSPACE প্রমাণিত”একই সম্পদ, একই mode কি না দেখুন; P বনাম NP, P বনাম PSPACE খোলা
“NL ⊊ PSPACE, তাই NL ≠ P” বা “P ⊊ EXP, তাই NP ≠ EXP”শুধু শৃঙ্খলের কোনো একটি ধাপ কঠোর জানা; কোনটি, তা অজানা
Diagonal D-তে padding বা ধাপ-counter বাদ দেওয়াজিজ্ঞাসা করুন: ছোট n-এ কী হয়? M একই জায়গায় ঘুরলে D থামে কি?
বানানো সাল বা নাম (যেমন space hierarchy-কে শুধু Hartmanis–Stearns বলা, বা EQREX↑-এর বছর)মূল প্রবন্ধের নাম আর বছর নিজে খুঁজে দেখুন; নিশ্চিত না হলে “বলে পরিচিত” লিখুন

ভালো ব্যবহার: AI-কে বিবৃতির সব শর্ত আলাদা করে লিখতে বলা, প্রমাণের প্রতিটি ধাপের কারণ চাওয়া, আর একটি ছোট simulation চাওয়া, যা আপনি নিজে চালিয়ে দেখবেন।

আমি গণনার তত্ত্ব শিখছি। Space hierarchy theorem নিয়ে প্রশ্ন। ১. উপপাদ্যটি সব শর্তসহ বিবৃত করো (space-constructible-এর সংজ্ঞা, f(n) ≥ log n, কোন model-এ জায়গা গোনা হয়)। ২. Diagonal যন্ত্র D-এর ধাপগুলো লেখো। input কেন ⟨M⟩10^k আকারের হতে হয়, আর ধাপ-counter কেন লাগে, প্রতিটির কারণ আলাদা করে বলো। ৩. প্রমাণের প্রতিটি ধাপে কোন সংজ্ঞা বা আগের ফল ব্যবহার হচ্ছে, তা লেখো। ৪. শুধু Python standard library দিয়ে একটি খেলনা simulation দাও: কয়েকটি "যন্ত্র" যারা প্রতিটি ধাপে ব্যবহৃত ঘরের সংখ্যা জানায়, আর একটি D যা বাজেট f(n) = n মেনে তাদের উত্তর উল্টায়। ছোট আর বড় padding-এ ফল ছাপো। ৫. এই উপপাদ্য থেকে NL ⊊ PSPACE কীভাবে আসে দেখাও, আর বলো এটি থেকে P ≠ PSPACE কেন আসে না। ৬. কোনো সাল বা নাম নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Halting problem-এর diagonalization আর hierarchy theorem-এর diagonalization-এর মধ্যে আসল পার্থক্য কী? D-কে “একটু বেশি” সম্পদ কেন দিতে হয়, আর সেই “একটু” কতটা?

দুই ক্ষেত্রেই মূল যন্ত্র একই: একটি তালিকার প্রতিটি যন্ত্রকে নিজের বর্ণনার ওপর (বা তার কাছাকাছি input-এ) চালিয়ে উত্তর উল্টে দেওয়া। Georg Cantor ১৮৯১ সালে বাস্তব সংখ্যার অগণনীয়তা প্রমাণে এই ধারণা দেন, Turing ১৯৩৬ সালে এটিকে গণনায় আনেন, আর Hartmanis ও Stearns ১৯৬৫ সালে সম্পদের হিসাবে।

পার্থক্য D-এর নিজের অবস্থায়। Halting problem-এ (পর্ব ৫১) আমরা ধরে নিই একটি decider H আছে, আর তা দিয়ে D বানিয়ে বিরোধ দেখাই। D সেখানে একটি কাল্পনিক যন্ত্র, যার অস্তিত্বই ভুল। Hierarchy theorem-এ D সত্যিকারের, সবসময় থামে এমন যন্ত্র; বিরোধ আসে D-এর language-কে কম বাজেটের কোনো যন্ত্র decide করে, এই অনুমান থেকে। অর্থাৎ এখানে diagonalization একটি গঠনমূলক প্রমাণ: A = L(D) স্পষ্টভাবে লেখা যায়।

“একটু বেশি” সম্পদ দরকার, কারণ D-কে M-কে simulate করতে হয়, আর simulation-এর একটি দাম আছে। জায়গায় সেই দাম একটি ধ্রুবক গুণক d: M-এর চিহ্নকে D-এর চিহ্নে encode করা। ধ্রুবক গুণক o(f)-এর ভেতরে হারিয়ে যায়, তাই space hierarchy প্রায় নিখুঁত: o(f) বনাম O(f). সময়ে, এক-tape যন্ত্রে, দাম log f(n) গুণক, কারণ ধাপ-counter আর M-এর বর্ণনা head-এর পাশে টেনে নিতে হয়। এজন্য time hierarchy-র ফাঁক o(f/log f) বনাম O(f). Multi-tape যন্ত্রে Hennie–Stearns simulation-এর কারণে একই ধরনের log গুণক আসে।

একটি আকর্ষণীয় দিক: এই ফাঁক প্রমাণ-কৌশলের সীমা, প্রকৃতির নয়। কেউ যদি আরও দক্ষ universal simulation বানাতে পারেন, ফাঁক ছোট হবে। কিছু বিশেষ model-এ (যেমন RAM-এর কিছু রূপে) প্রায় নিখুঁত hierarchy জানা আছে বলে পরিচিত। অর্থাৎ “একটু বেশি” মানে আসলে “universal machine-এর overhead-এর সমান বেশি”।

মূল উপলব্ধি: Hierarchy-র diagonalization গঠনমূলক, আর তার ফাঁকের মাপ ঠিক universal simulation-এর দামের সমান: জায়গায় ধ্রুবক, এক-tape সময়ে log f(n).

প্র ০২Gap theorem বলে TIME(f) = TIME(2f) হতে পারে। এটি কি hierarchy theorem-এর বিরোধী? Constructibility শর্তটি আসলে কী রক্ষা করে?

বিরোধী নয়, কারণ দুটির শর্ত আলাদা। Gap theorem (Allan Borodin, ১৯৭২; Boris Trakhtenbrot-এর আগের কাজেও একই ধারণা ছিল বলে পরিচিত) বলে: যেকোনো computable g, যেখানে g(n) ≥ n, নিলে এমন একটি computable f আছে, যাতে TIME(f(n)) = TIME(g(f(n))). সেই f time-constructible নয়, আর hierarchy theorem শুধু constructible সীমার কথা বলে।

Gap-এর f কীভাবে বানানো হয়, তা দেখলেই বোঝা যায় শর্তটি কী রক্ষা করে। মোটামুটি ধারণা: প্রতিটি n-এর জন্য প্রথম n-টি যন্ত্রকে দৈর্ঘ্য n-এর সব input-এ চালিয়ে দেখা হয়, আর এমন একটি সংখ্যা f(n) বেছে নেওয়া হয়, যাতে কোনো যন্ত্রের থামার সময় f(n) আর g(f(n))-এর মাঝখানে না পড়ে। যেহেতু যন্ত্র সসীম আর input সসীম, এমন একটি “খালি জায়গা” সবসময় পাওয়া যায় (সংখ্যাগুলোর ফাঁকে)। ফলে যে যন্ত্র g(f(n)) সময়ে থামে, সে আসলে f(n) সময়েই থামে; দুই শ্রেণি সমান।

এখন hierarchy-র D এমন f দিয়ে চলতে পারে না, কারণ f(n) মাপতে D-কে উপরের মতো অনেক যন্ত্র চালাতে হতো, যা f(n)-এর চেয়ে অনেক বেশি সময় নেয়। D নিজের বাজেট মাপতে গিয়েই বাজেট ভাঙে। Constructibility ঠিক এই নিশ্চয়তা দেয়: বাজেট নিজের ভেতরেই মাপা যায়। তাই f-এর পর্যাপ্ত “ভদ্রতা” না থাকলে বেশি সময় অর্থহীন হতে পারে।

বাস্তবে এর প্রভাব প্রায় নেই, কারণ algorithm বিশ্লেষণে যে সীমা আসে (n log n, n3, 2n) সবই constructible. কিন্তু তাত্ত্বিকভাবে শিক্ষাটি গুরুত্বপূর্ণ: “বেশি সম্পদ মানে বেশি ক্ষমতা” কোনো সার্বজনীন সত্য নয়, এটি সম্পদের মাপ সম্পর্কে একটি শর্তসাপেক্ষ উপপাদ্য। AI বা পাঠ্যপুস্তকের সারাংশে শর্তটি বাদ পড়লে বিবৃতিটি আক্ষরিক অর্থে মিথ্যা হয়ে যায়।

মূল উপলব্ধি: Hierarchy আর gap পরস্পরবিরোধী নয়; constructibility নিশ্চিত করে যে বাজেট নিজের ভেতরে মাপা যায়, আর এই শর্ত না থাকলে বিশাল বাড়তি সময়ও নতুন কিছু না-ও দিতে পারে।

প্র ০৩আমরা NL ⊊ PSPACE আর P ⊊ EXP জানি, কিন্তু শৃঙ্খলের কোনো একক ধাপ কঠোর কি না জানি না। এই অদ্ভুত অবস্থা কেন, আর nondeterministic time hierarchy এখানে কতটা সাহায্য করে?

অবস্থাটি একটি সরল যুক্তির ফল। যদি a ⊆ b ⊆ c ⊆ d আর a ≠ d জানা থাকে, তাহলে তিনটি ⊆-এর সবকটি সমতা হতে পারে না; অন্তত একটি কঠোর। কিন্তু কোনটি, তা এই যুক্তি বলে না। P ⊆ NP ⊆ PSPACE ⊆ EXP-এ ঠিক তা-ই ঘটছে। বেশিরভাগ গবেষক মনে করেন তিনটিই কঠোর, কিন্তু একটিও প্রমাণিত নয়।

কেন একক ধাপ এত কঠিন? প্রতিটি ধাপে দুটি আলাদা জিনিস তুলনা হচ্ছে। P ⊆ NP: deterministic বনাম nondeterministic. NP ⊆ PSPACE: সময় বনাম জায়গা। PSPACE ⊆ EXP: জায়গা বনাম সময়। Hierarchy theorem শুধু একই জিনিসের বেশি আর কম তুলনা করে। বাইরের দুই প্রান্ত (P আর EXP) একই সম্পদ, একই mode, তাই সেখানে উপপাদ্য কাজ করে, ভেতরে করে না।

Nondeterministic time hierarchy (Cook ১৯৭২-এ প্রথম রূপ; পরে Seiferas, Fischer আর Meyer ১৯৭৮; Žák ১৯৮৩, বলে পরিচিত) NTIME-এর ভেতরে একই কাজ করে, আর NP ⊊ NEXP দেয়। এর প্রমাণে বাধাটি শিক্ষণীয়: D-কে M-এর উত্তর উল্টাতে হয়, কিন্তু nondeterministic M-এর “না” উত্তর যাচাই করতে সব শাখা দেখতে হয়। Lazy diagonalization এটি এড়ায়: D প্রতিটি input-এ উল্টানোর চেষ্টা করে না, বরং একটি লম্বা input-ব্যবধিতে M-কে এমনভাবে “ধাওয়া” করে যে শুধু শেষ প্রান্তে, যেখানে input যথেষ্ট লম্বা আর exponential deterministic simulation বাজেটে ধরে, সেখানে উল্টানো হয়। ফলে কোথাও না কোথাও দ্বিমত নিশ্চিত হয়।

কিন্তু NP ⊊ NEXP-ও P বনাম NP-তে সাহায্য করে না। মজার একটি পরোক্ষ ফল আছে: যদি P = NP হতো, তাহলে padding যুক্তি দিয়ে EXP = NEXP হতো। অর্থাৎ EXP ≠ NEXP প্রমাণ করতে পারলে P ≠ NP আসত, যা এই প্রশ্নের কঠিনতা আরও স্পষ্ট করে।

মূল উপলব্ধি: শৃঙ্খলের দুই প্রান্তের পার্থক্য hierarchy দেয়, কারণ প্রান্তে একই সম্পদ আর mode; ভেতরের প্রতিটি ধাপে দুটি আলাদা জিনিসের তুলনা, যেখানে diagonalization-এর কোনো সরল প্রয়োগ নেই।

প্র ০৪এমন কোন “স্বাভাবিক” সমস্যা আছে, যাদের কাঠিন্য কোনো অপ্রমাণিত অনুমান ছাড়াই প্রমাণিত? প্রকৌশলীর কাছে এর মানে কী?

NP-complete সমস্যার কাঠিন্য সবসময় শর্তসাপেক্ষ: “P ≠ NP হলে এটি P-তে নেই”। কিন্তু hierarchy theorem আর completeness মেলালে কিছু সমস্যার জন্য শর্তহীন ফল পাওয়া যায়, কারণ উপরের দিকের শ্রেণিগুলো (EXP, EXPSPACE) প্রমাণিতভাবে P-র চেয়ে বড়।

প্রথম উদাহরণ এই পর্বেই: ঘাতসহ regex-এর equivalence, Albert Meyer আর Larry Stockmeyer-এর ১৯৭২ সালের কাজ থেকে EXPSPACE-complete বলে পরিচিত (তাঁদের মূল প্রবন্ধ বর্গ-operation নিয়ে, পরে সাধারণ ঘাতে একই ফল)। দ্বিতীয়: n × n বোর্ডের সাধারণীকৃত দাবা, যা Aviezri Fraenkel আর David Lichtenstein ১৯৮১ সালে EXP-complete দেখান বলে পরিচিত; তাই P ⊊ EXP থেকে এটি প্রমাণিতভাবে polynomial সময়ের বাইরে। (মনে রাখবেন, সাধারণ 8 × 8 দাবা একটি সসীম খেলা; complexity-র প্রশ্ন শুধু বোর্ড বড় হলে অর্থবহ।) তৃতীয়: Presburger arithmetic, অর্থাৎ শুধু যোগ আর তুলনা নিয়ে পূর্ণসংখ্যার যুক্তিবাক্যের সত্যতা। এটি decidable, কিন্তু Michael Fischer আর Michael Rabin ১৯৭৪ সালে দেখান যে যেকোনো decision procedure-এর, এমনকি nondeterministic-এরও, কিছু input-এ দ্বি-exponential (22cn) ধাপ লাগে।

প্রকৌশলীর কাছে তিনটি শিক্ষা। এক, এই সমস্যাগুলো বাস্তবে আসে: config-ভাষায় পুনরাবৃত্তি-গোনা, খেলার AI, program verification-এ arithmetic. দুই, “আরও ভালো algorithm খুঁজি” এখানে অর্থহীন worst case-এ; প্রমাণিত সীমা আছে। তিন, তবু বাস্তবের input প্রায়ই ছোট বা গঠনযুক্ত, তাই solver-গুলো অনেক ক্ষেত্রে দ্রুত চলে (যেমন Presburger-এর জন্য SMT solver). সঠিক নকশা হলো সীমা মেনে চলা: input-এর মাপে সীমা, সময়সীমা, আর “অজানা” উত্তরকে বৈধ ফল হিসেবে গ্রহণ।

মূল উপলব্ধি: Hierarchy theorem আর completeness মিলে কিছু স্বাভাবিক সমস্যার শর্তহীন কাঠিন্য দেয়; প্রকৌশলে এর মানে worst case-এর বিরুদ্ধে লড়াই নয়, সীমা আর সময়সীমা দিয়ে নকশা।

প্র ০৫Blum-এর speedup theorem বলে কিছু সমস্যার কোনো “সবচেয়ে দ্রুত” algorithm নেই। তাহলে “একটি সমস্যার time complexity” কথাটির মানে কী?

Manuel Blum ১৯৬৭ সালে একটি machine-নিরপেক্ষ complexity তত্ত্বের প্রবন্ধে দেখান: যেকোনো computable function r নিলে এমন একটি decidable language L আছে, যার প্রতিটি algorithm A-এর জন্য আরেকটি algorithm A′ আছে, যা প্রায় সব input-এ A-এর চেয়ে r-গুণ দ্রুত (আরও নিখুঁতভাবে, r(A′-এর সময়) ≤ A-এর সময়)। r(x) = 2x নিলে: প্রতিটি algorithm-এর চেয়ে exponential হারে দ্রুত আরেকটি আছে, আর তার চেয়েও দ্রুত আরেকটি, অসীমভাবে। সর্বোত্তম কেউ নেই।

এর আগে Hartmanis আর Stearns-এর linear speedup theorem (১৯৬৫) একটি নরম রূপ দেখিয়েছিল: multi-tape যন্ত্রে running time-কে যেকোনো স্থির গুণকে কমানো যায় (n-এর চেয়ে দ্রুত বাড়া সময়ের জন্য), বড় tape-alphabet ব্যবহার করে কয়েকটি ঘর একসঙ্গে পড়ে। তাই “এই algorithm ঠিক 3n2 ধাপ নেয়” কথাটি model-এর খুঁটিনাটির ওপর নির্ভর করে, আর O-notation-এ গুণক বাদ দেওয়া তত্ত্বের দিক থেকেও যুক্তিসংগত।

তাহলে “X-এর complexity n2” মানে কী? সাধারণত দুটি আলাদা দাবি: একটি ওপরের সীমা (একটি O(n2) algorithm আছে) আর একটি নিচের সীমা (কোনো o(n2) algorithm নেই)। Blum দেখান, কিছু সমস্যার জন্য এই দুটি একটি সংখ্যায় মেলে না। সেগুলো কৃত্রিম, কিন্তু স্বাভাবিক সমস্যাতেও এমন ছায়া দেখা যায়। Matrix গুণের ঘাত ω (n × n matrix গুণে nω-এর ক্রমে ধাপ) নিয়ে কয়েক দশক ধরে একের পর এক সামান্য উন্নতি হয়েছে, বর্তমান সীমা প্রায় ২.৩৭; ω = 2 কি না, তা খোলা, আর ω-কে অসীম একটি algorithm-ক্রমের সীমা হিসেবেই সংজ্ঞায়িত করা হয়।

Hierarchy theorem এর বিপরীত দিক দেখায়: শ্রেণির স্তরে বেশি সময় সত্যিই বেশি দেয়। দুটি মিলিয়ে ছবি: শ্রেণিগুলো ভালোভাবে আলাদা, কিন্তু একটি নির্দিষ্ট সমস্যার “সঠিক” complexity সবসময় একটি পরিষ্কার সংখ্যা নয়।

মূল উপলব্ধি: একটি সমস্যার complexity আসলে ওপরের আর নিচের সীমার একটি জোড়া; Blum-এর speedup দেখায় যে এই জোড়া কিছু ক্ষেত্রে কখনো একটি “সর্বোত্তম algorithm”-এ মেলে না।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। diagonal_space.py-তে নিজের padding দিয়ে অনুশীলন ৪ যাচাই করতে পারেন।

  1. নকশা: এমন একটি language A-এর জন্য diagonal যন্ত্র D-এর বর্ণনা দিন, যা SPACE(n2)-এ আছে কিন্তু SPACE(n)-এ নেই। n2 কেন space-constructible, D-এর ধাপ-counter কত বড়, আর কেন A ∉ SPACE(n), তিনটিই বলুন।

    Constructibility: 1n পড়ে একটি binary counter-এ n গোনা (log n bit), তারপর স্কুলের নিয়মে n × n গুণ (O(log n) bit), ফল n2-এর binary রূপ। মোট জায়গা O(log n) ≤ O(n2).

    D: “input w-এ: (১) n = |w|; n2 হিসাব করে work tape-এ n2টি ঘর চিহ্নিত; বাইরে যেতে চাইলে reject. (২) w = ⟨M⟩10k না হলে reject. (৩) M-কে w-এ simulate, ধাপ গোনা; 22n2 ছাড়ালে reject. (৪) M accept করলে reject, reject করলে accept.” Counter-এর মান 22n2 পর্যন্ত, তাই 2n2 + 1 bit, O(n2) জায়গা।

    কেন A ∉ SPACE(n): ধরুন M A-কে c · n জায়গায় decide করে। D-এর simulation লাগে d · c · n ঘর, আর বড় n-এ d · c · n < n2. M-এর configuration 2O(n)টি, যা বড় n-এ 22n2-এর নিচে। তাই যথেষ্ট লম্বা w = ⟨M⟩10k-এ D পুরো simulation শেষ করে উল্টো উত্তর দেয়: w ∈ A ⇔ w ∉ L(M), বিরোধ। এটি উপপাদ্য ৩.১-এর f = n2, g = n দিয়ে প্রয়োগ, কারণ n = o(n2).

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: P ≠ NP. প্রমাণ: (১) Time hierarchy theorem থেকে প্রতিটি k-এর জন্য TIME(nk) ⊊ TIME(2n). (২) SAT-এর সমাধানে সব 2m মান-নির্ধারণ পরীক্ষা করতে হয়, তাই SAT ∈ TIME(2n) কিন্তু কোনো TIME(nk)-এ নেই। (৩) একই যুক্তিতে TIME(n2) ⊊ TIME(n2 log n), তাই সূক্ষ্ম স্তরেও SAT আলাদা। (৪) SAT ∈ NP, তাই P ≠ NP. ∎” কোথায় কোথায় ভুল?

    ধাপ ১ ঠিক: nk = o(2n/n), তাই TIME(nk) ⊊ TIME(2n).

    ধাপ ২ মূল ভুল: Hierarchy theorem বলে TIME(2n)-এ কোনো একটি language আছে, যা TIME(nk)-এ নেই; সেটি D-এর কৃত্রিম language, SAT নয়। “সব মান-নির্ধারণ পরীক্ষা করতে হয়” একটি অপ্রমাণিত দাবি; brute force একটি algorithm মাত্র, আর কোনো চতুর algorithm নেই, তা কেউ প্রমাণ করেনি। এই দাবিই আসলে P ≠ NP-এর সমতুল্য।

    ধাপ ৩ আলাদা ভুল: n2 / (n2 log n / log(n2 log n)) → 2, 0 নয়; তাই time hierarchy থেকে TIME(n2) ⊊ TIME(n2 log n) আসে না। (TIME(n2) ⊊ TIME(n2 log2 n) আসে।)

    কাঠামোগত সমস্যা: P বনাম NP deterministic বনাম nondeterministic-এর প্রশ্ন; hierarchy theorem একই mode-এ বেশি আর কম সময় তুলনা করে। তার ওপর প্রমাণটি relativize করত, আর Baker–Gill–Solovay দেখান এমন প্রমাণ এই প্রশ্নে কাজ করতে পারে না।

  3. হিসাব: নিচের প্রতিটি জোড়ায় বলুন space বা time hierarchy theorem (উপপাদ্য ৩.১, ৪.১) কঠোর অন্তর্ভুক্তি দেয় কি না, অনুপাত দেখিয়ে। (ক) TIME(n log n) বনাম TIME(n2); (খ) TIME(2n) বনাম TIME(n2 · 2n); (গ) TIME(2n) বনাম TIME(n · 2n); (ঘ) SPACE(log n) বনাম SPACE(log2 n); (ঙ) P বনাম PSPACE.

    (ক) হ্যাঁ। f = n2, log f = 2 log n, অনুপাত n log n / (n2/(2 log n)) = 2 log2 n / n → 0. Scratch-এ যাচাই: n = 16, 256, 1024, 4096-এ 2.0, 0.5, 0.195, 0.070.

    (খ) হ্যাঁ। log f = n + 2 log n, অনুপাত (n + 2 log n)/n2 → 0. একই n-গুলোতে 0.094, 0.0042, 0.0010, 0.00025.

    (গ) না, এই উপপাদ্য থেকে নয়। log f = n + log n, অনুপাত (n + log n)/n → 1. একই n-গুলোতে 1.25, 1.03, 1.0098, 1.0029. জোড়াটি আলাদা কি না, এই উপপাদ্য বলে না।

    (ঘ) হ্যাঁ। log2 n space-constructible (f(n) ≥ log n), আর log n / log2 n = 1/log n → 0. Space-এ কোনো log গুণক লাগে না।

    (ঙ) না। একটি সময়ের শ্রেণি, একটি জায়গার; hierarchy theorem আলাদা সম্পদ তুলনা করে না। P ⊆ PSPACE জানা, কঠোর কি না খোলা প্রশ্ন।

  4. আগাম অনুমান: diagonal_space.py-এর D (বাজেট f(n) = n, প্রতি simulated ঘরে ৪টি D-ঘর) নিচের input-গুলোতে কী ছাপবে, অর্থাৎ D(w), M(w) আর কারণ? (ক) balance, k = 29; (খ) square, k = 5; (গ) square, k = 21. প্রতিটিতে D আর M একমত না দ্বিমত?

    (ক) w = 011 আর ২৯টি 0, n = 32. 0 আছে ৩০টি, 1 আছে ২টি; পার্থক্য সর্বোচ্চ 28, binary-তে ৫ bit, তাই ঘর 5 + 1 = 6, D-এর লাগে 24 ≤ 32: simulation ধরে। balance accept করে (বেশি 0), তাই D reject. দ্বিমত।

    (খ) w = 101 আর ৫টি 0, n = 8. square-এর counter i = 1, 2, 3 (কারণ 22 < 8 ≤ 32); i = 3-এ D-এর লাগে 12 > 8: বাজেট ফুরাল, D reject. square-ও reject করত (8 পূর্ণবর্গ নয়)। একমত, কোনো দ্বিমত নেই।

    (গ) n = 24. i উঠবে 5 পর্যন্ত (42 = 16 < 24 ≤ 25), D-এর লাগে 20 ≤ 24: ধরে। square reject করে (24 পূর্ণবর্গ নয়), তাই D accept. দ্বিমত। তিনটি উত্তরই scratch-এ একই code চালিয়ে মিলানো হয়েছে: (False, simulated), (False, space 12>8), (True, simulated).

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমTime hierarchy theorem-এর diagonal যন্ত্র D-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. n = |w| বের করে f(n) হিসাব করা
  2. ⌈f(n)/log f(n)⌉ একটি binary counter-এ রাখা
  3. w ⟨M⟩10k আকারের কি না দেখা; না হলে reject
  4. M-কে w-এর ওপর simulate করা, প্রতি ধাপে counter কমিয়ে
  5. M accept করলে reject, M reject করলে accept

Space hierarchy theorem “এমন language আছে, যা O(f(n)) জায়গায় decide হয় কিন্তু o(f(n)) জায়গায় হয় না” কোন শর্তে প্রমাণিত?

  • যেকোনো ক্রমবর্ধমান computable f-এর জন্য
  • f space-constructible হলে (f(n) ≥ log n, আর 1n থেকে f(n) O(f(n)) জায়গায় হিসাব করা যায়)
  • শুধু f যদি একটি polynomial হয়
  • f time-constructible হলে

এক-tape deterministic Turing machine-এর time hierarchy theorem (g = o(f/log f) হলে TIME(g) ⊊ TIME(f), f time-constructible) সরাসরি কোন অন্তর্ভুক্তিকে কঠোর প্রমাণ করে?

  • TIME(n2) ⊊ TIME(n2 log n)
  • P ⊊ NP
  • TIME(n2) ⊊ TIME(n3)
  • TIME(2n) ⊊ TIME(n · 2n)

Hierarchy theorem-এর diagonal যন্ত্র D input-কে ⟨M⟩10k আকারে নেয়। 10k অংশটি (padding) কেন দরকার?

  • o(f) শুধু বড় n-এ কাজ করে, তাই একই M-কে ইচ্ছামতো লম্বা input-এ পরীক্ষা করতে হয়
  • যাতে D প্রতিটি input-এ থামে
  • যাতে ⟨M⟩ কোথায় শেষ, তা বোঝা যায়, আর অন্য কোনো কারণ নেই
  • যাতে D-এর জায়গা কম লাগে

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE শৃঙ্খল সম্পর্কে কোন বক্তব্যটি প্রমাণিত?

  • P ⊊ NP
  • L ⊊ NL
  • সবগুলো ⊆ আসলে সমতা হতে পারে
  • NL ⊊ PSPACE, তাই NL থেকে PSPACE পর্যন্ত অন্তত একটি ⊆ কঠোর, কিন্তু কোনটি তা অজানা

Hierarchy theorem-এর মতো diagonalization প্রমাণ দিয়ে P বনাম NP মীমাংসা করা যায় না কেন?

  • Diagonalization একটি ভুল প্রমাণ-পদ্ধতি
  • এমন প্রমাণ relativize করে, অথচ এমন oracle আছে যেখানে P = NP আর এমন oracle-ও আছে যেখানে P ≠ NP
  • কারণ P = NP ইতিমধ্যে প্রমাণিত
  • কারণ polynomial function time-constructible নয়

ঘাতসহ regex-এর equivalence সমস্যা EQREX↑ EXPSPACE-complete. এ থেকে কী প্রমাণিত?

  • EQREX↑ undecidable
  • EQREX↑ PSPACE-এ আছে
  • EQREX↑ PSPACE-এ নেই, তাই P-তেও নেই, কোনো অপ্রমাণিত অনুমান ছাড়াই
  • P ≠ NP

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Constructible function: বাজেট নিজের ভেতরে মাপা যায় (space: f ≥ log n, O(f) জায়গায়; time: f ≥ n log n, O(f) সময়ে)। শর্ত না থাকলে gap theorem hierarchy ভেঙে দিতে পারে।
  2. Space hierarchy: g = o(f) হলে SPACE(g) ⊊ SPACE(f). Diagonal D: বাজেট চিহ্নিত, ⟨M⟩10k আকার, ধাপ-counter, উত্তর উল্টানো।
  3. Time hierarchy (এক-tape): g = o(f/log f) হলে TIME(g) ⊊ TIME(f); log f(n) গুণক আসে counter head-এর সঙ্গে টানার দাম থেকে।
  4. অনুসিদ্ধান্ত: NL ⊊ PSPACE, P ⊊ EXP, PSPACE ⊊ EXPSPACE, NP ⊊ NEXP; কিন্তু শৃঙ্খলের কোন একক ধাপ কঠোর, তা অজানা। EQREX↑ EXPSPACE-complete, তাই শর্তহীনভাবে P-র বাইরে।
  5. Hierarchy একই সম্পদ, একই mode তুলনা করে, আর তার প্রমাণ relativize করে; তাই P বনাম NP বা P বনাম PSPACE-এ সে চুপ।

পরের পর্বে: Oracle Turing machine আর relativization আরও কাছ থেকে, তারপর polynomial hierarchy: ∃ আর ∀-এর পালাবদলে Σkp আর Πkp, NPNP, আর “NP = coNP হলে hierarchy ধসে পড়ে” কেন।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান