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

Oracle, relativization আর polynomial hierarchy

Oracle Machines, Relativization and the Polynomial Hierarchy — Σkp, Πkp, Δkp, Complete Problems, PH ⊆ PSPACE and Collapse Theorems

Taught in Bangla, this lesson looks at questions beyond NP that need both ∃ and ∀. It defines oracle machines and the classes P^SAT and NP^NP, defines Σk, Πk and Δk by quantifiers and by oracles and proves the two agree, shows ΣkSAT is complete at each level and places MIN-FORMULA in Π2. It proves PH ⊆ PSPACE and the collapse theorem, and explains what oracle worlds say about proof techniques. In-page Python (Pyodide) checks a robust hub plan, finds minimal formulas and evaluates quantified formulas in small space.

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

  • Oracle class PA, NPA, PNP আর NPNP-এর নিখুঁত সংজ্ঞা, আর কোন প্রশ্নে কতবার oracle লাগে
  • Σkp, Πkp, Δkp-এর quantifier আর oracle সংজ্ঞা, আর দুটি যে সমান তার প্রমাণ
  • ΣkSAT প্রতিটি স্তরে complete, MIN-FORMULA কেন Π2p-এ, আর স্বাভাবিক সমস্যা কোন স্তরে বসে
  • PH ⊆ PSPACE আর “Σk = Πk হলে hierarchy ধসে” উপপাদ্যের প্রমাণ, Karp–Lipton-এর মতো পরিণাম
  • Oracle-জগতে PH কেমন আচরণ করে, আর তা থেকে প্রমাণ-কৌশলের সীমা কী বোঝা যায়

১ · NP-এর ওপরের প্রশ্ন — “সবচেয়ে ছোট” আর “সব ঝুঁকিতেও”

বাজারঘরের operations দলের দুটি প্রশ্ন ভাবুন। প্রথমটি: “ঢাকার পাঁচটি এলাকায় পণ্য পৌঁছাতে বড়জোর দুটি hub খুলতে চাই। এমন একটি hub-বাছাই আছে কি, যাতে যেকোনো একটি রাস্তা বন্ধ হলেও প্রতিটি এলাকায় অন্তত একটি hub থেকে পৌঁছানো যায়?” দ্বিতীয়টি এসেছে software দল থেকে: “coupon যাচাইয়ের এই Boolean শর্তটি কি সবচেয়ে ছোট আকারে লেখা, নাকি এর চেয়ে ছোট কিন্তু হুবহু একই আচরণের কোনো শর্ত আছে?”

দুটি প্রশ্নেরই গঠন অদ্ভুত। প্রথমটিতে “আছে” (∃ plan) আর “সব” (∀ রাস্তা-বন্ধ) পরপর। দ্বিতীয়টিতে “সব ছোট শর্তের জন্য” (∀) “এমন একটি input আছে যেখানে দুটি আলাদা” (∃)। পর্ব ৫৮-এর NP-তে শুধু একটি ∃ থাকে: একটি certificate দেখিয়ে “হ্যাঁ” প্রমাণ। পর্ব ৬২-এর coNP-তে শুধু একটি ∀। কিন্তু ∃ আর ∀ একসঙ্গে এলে কোনো একটি ছোট certificate যথেষ্ট মনে হয় না: plan-টি দেখালেও, “সব রাস্তা-বন্ধে টেকে” দাবিটি মেলাতে আবার একটি coNP ধরনের প্রশ্ন বাকি থাকে।

ক্রিকেটের অধিনায়কের কথা ভাবুন। “এমন একটি fielding সাজানো আছে কি” একটি ∃ প্রশ্ন। কিন্তু অধিনায়ক আসলে জানতে চান: “এমন একটি fielding আছে কি, যাতে ব্যাটসম্যান যেভাবেই মারুক, চারের বল আটকানো যায়?” এখানে নিজের চাল (∃) আর প্রতিপক্ষের সব সম্ভাব্য চাল (∀)। প্রতিপক্ষ আরেকবার সুযোগ পেলে আরও এক পালা যোগ হয়: ∃∀∃। Polynomial hierarchy ঠিক এই পালার সংখ্যা দিয়ে সমস্যাকে স্তরে সাজায়।

এই পর্বের কাজ তিনটি। প্রথমে পর্ব ৫২-এর oracle Turing machine-কে polynomial সময়ে নামিয়ে আনা: PSAT আর NPSAT. তারপর quantifier-এর পালা গুনে polynomial hierarchy (PH) সংজ্ঞায়িত করা, আর দেখানো যে oracle-এর ভাষা আর quantifier-এর ভাষা একই শ্রেণি দেয়। শেষে PH সম্পর্কে যা প্রমাণিত (PH ⊆ PSPACE, ধসে পড়ার উপপাদ্য) আর যা খোলা, তা আলাদা করা। পর্ব ৬৩-এর relativization এখানে আবার আসবে, তবে PH-এর চোখ দিয়ে।

২ · Oracle যন্ত্র ফিরে দেখা — PSAT আর NPSAT

পর্ব ৫২-এ oracle যন্ত্র এসেছিল computability-র প্রসঙ্গে: MB চলার মাঝে একটি আলাদা “query tape”-এ string y লিখে একটি বিশেষ state-এ গেলে, পরের ধাপেই জেনে যায় y ∈ B কি না। প্রশ্ন করার খরচ এক ধাপ, শুধু y লেখার সময়টুকু গোনা হয়। পর্ব ৬২-এ এর polynomial রূপ এসেছিল Cook reduction হিসেবে। এখন একে শ্রেণির ভাষায় লিখি।

সংজ্ঞা ২.১ (Oracle class)

একটি language A-এর জন্য, PA = যেসব language A-এর oracle-সহ একটি polynomial সময়ের deterministic oracle TM decide করে। NPA = যেসব language A-এর oracle-সহ একটি polynomial সময়ের nondeterministic oracle TM decide করে (প্রতিটি শাখা নিজের প্রশ্ন নিজে করে)। একটি শ্রেণি C-এর জন্য PC = ⋃A ∈ C PA, আর NPC-ও একইভাবে।

কয়েকটি সরল কিন্তু কাজের তথ্য, প্রতিটির ছোট প্রমাণসহ:

  1. PNP = PSAT. যেকোনো A ∈ NP-এর জন্য A ≤p SAT (Cook–Levin, পর্ব ৬০)। তাই A-কে করা প্রতিটি প্রশ্ন y-কে আগে f(y)-তে বদলে SAT-কে জিজ্ঞেস করা যায়; উত্তর একই, আর খরচ polynomial. একই যুক্তিতে NPNP = NPSAT.
  2. Oracle-এর complement একই শক্তি দেয়। M উত্তরটি নিজে উল্টে নিতে পারে, তাই PSAT = PUNSAT আর NPNP = NPcoNP.
  3. NP ∪ coNP ⊆ PSAT. L ∈ NP হলে w-কে f(w)-তে বদলে একবার জিজ্ঞেস; L ∈ coNP হলে একই প্রশ্ন করে উত্তর উল্টানো। তাই PSAT complement-এ বদ্ধ, আর NP ও coNP দুটিকেই ধারণ করে।
  4. PP = P আর NPP = NP. P-এর oracle-কে যন্ত্র নিজেই polynomial সময়ে simulate করতে পারে, তাই সে কোনো বাড়তি শক্তি দেয় না।

PSAT-এ কী কী ধরা পড়ে, একটি উদাহরণে দেখা যাক। EXACT-CLIQUE = {⟨G, k⟩ : G-এর সবচেয়ে বড় clique-এর আকার ঠিক k}. দুটি প্রশ্নেই উত্তর মেলে: “k আকারের clique আছে?” হ্যাঁ, আর “k + 1 আকারের আছে?” না। প্রথমটি NP প্রশ্ন, দ্বিতীয়টি coNP প্রশ্ন; তাই EXACT-CLIQUE ∈ PSAT, মাত্র দুটি oracle প্রশ্নে। কিন্তু এটি NP-তে বা coNP-তে আছে বলে জানা নেই, কারণ “হ্যাঁ” আর “না” দুই ধরনের প্রমাণই একসঙ্গে লাগে। আরও কঠিন উদাহরণ: “TSP-এর সবচেয়ে ছোট রুট কি একটিই?” Christos Papadimitriou ১৯৮৪ সালে দেখান যে এই UNIQUE-OPTIMUM-TSP সমস্যা PNP-complete বলে পরিচিত; এখানে binary search-এ বহু প্রশ্ন লাগে, যেমন পর্ব ৬৩-এর planner ১৯টি প্রশ্ন করেছিল।

Oracle-এর প্রশ্নের দৈর্ঘ্য: polynomial সময়ের যন্ত্র polynomial দৈর্ঘ্যের প্রশ্নই লিখতে পারে, আর বড়জোর polynomial-সংখ্যক প্রশ্ন করতে পারে। আর nondeterministic oracle যন্ত্রের প্রতিটি শাখা আলাদা প্রশ্ন করতে পারে, আর oracle-এর “না” উত্তরও ব্যবহার করতে পারে। ঠিক এই শেষ ক্ষমতাটিই NPSAT-কে NP-এর চেয়ে শক্তিশালী করে বলে মনে করা হয়: একটি শাখা “এই সূত্রটি unsatisfiable” জেনে নিয়ে এগোতে পারে, যা NP-এর verifier নিজে মেলাতে পারে না।

৩ · একটি ∃∀ প্রশ্ন — বাজারঘরের “সব ঝুঁকিতেও টেকে” এমন hub plan

প্রথম প্রশ্নটিকে নিখুঁত করা যাক। পাঁচটি এলাকা: উত্তরা (U), মিরপুর (M), গুলশান (G), মতিঝিল (J), ধানমন্ডি (D); পাঁচটি রাস্তা: U–M, M–G, G–J, J–D, M–J (কাল্পনিক মানচিত্র)। Hub খোলা যায় শুধু U, G আর D-তে, আর বড়জোর দুটি। একটি plan x হলো hub-এর একটি সেট; একটি রাস্তা-বন্ধ y হলো “কোনোটিই বন্ধ নয়” বা ঠিক একটি রাস্তা বন্ধ। ok(x, y) = “y বন্ধ থাকা অবস্থায় প্রতিটি এলাকা x-এর কোনো hub থেকে পৌঁছানো যায়”, যা একটি graph-search দিয়ে polynomial সময়ে মেলে। প্রশ্ন:

∃x ∀y ok(x, y) ?

একটি NTM প্রথম ∃ অংশটি অনুমান করতে পারে। কিন্তু ভেতরের “∀y ok(x, y)” একটি coNP প্রশ্ন; তার complement “∃y ¬ok(x, y)”, অর্থাৎ “এই plan ভেঙে দেয় এমন একটি রাস্তা-বন্ধ আছে কি?”, একটি NP প্রশ্ন। তাই NTM এটি একটি NP oracle-কে জিজ্ঞেস করে, আর উত্তর “না” হলে গ্রহণ করে। এভাবে প্রশ্নটি NPNP-তে। নিচের ব্লক এই যন্ত্রটি সরাসরি চালায়: বাইরের ∃-কে সব plan-এর ওপর loop দিয়ে, আর oracle-কে brute force দিয়ে।

# Sigma_2 question: EXISTS a hub plan (at most 2 hubs) such that
# FOR ALL single road closures, every zone is still reachable from a hub.
from itertools import combinations
ZONES = "UMGJD"                      # Uttara Mirpur Gulshan Motijheel Dhanmondi
ROADS = ["U-M", "M-G", "G-J", "J-D", "M-J"]
PLANS = [p for r in (1, 2) for p in combinations("UGD", r)]
CLOSURES = [None] + ROADS            # no closure, or exactly one road closed
def ok(plan, closed):                # polynomial-time check V(x, y)
    seen, todo = set(plan), list(plan)
    while todo:
        v = todo.pop()
        for r in ROADS:
            a, b = r.split("-")
            if r != closed and v in (a, b):
                w = b if v == a else a
                if w not in seen: seen.add(w); todo.append(w)
    return len(seen) == len(ZONES)
calls = 0
def np_oracle(plan):                 # NP question: EXISTS a closure that breaks plan?
    global calls; calls += 1
    for c in CLOSURES:
        if not ok(plan, c): return True, c
    return False, None
for plan in PLANS:                   # the outer EXISTS (an NTM would guess it)
    bad, c = np_oracle(plan)
    print("plan", "+".join(plan).ljust(4), "| oracle: a closure breaks it?",
          f"yes ({c} closed)" if bad else "no  -> robust plan, answer YES")
    if not bad: break
print("oracle calls:", calls, "| plans:", len(PLANS), "| closures:", len(CLOSURES))

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

plan U    | oracle: a closure breaks it? yes (U-M closed)
plan G    | oracle: a closure breaks it? yes (U-M closed)
plan D    | oracle: a closure breaks it? yes (U-M closed)
plan U+G  | oracle: a closure breaks it? yes (J-D closed)
plan U+D  | oracle: a closure breaks it? no  -> robust plan, answer YES
oracle calls: 5 | plans: 6 | closures: 6

U–M আর J–D দুটি রাস্তাই উত্তরা আর ধানমন্ডির একমাত্র সংযোগ। তাই যে plan এই দুই প্রান্তের কোনো একটিতে hub রাখে না, তা ওই রাস্তা বন্ধ হলেই ভেঙে যায়। পঞ্চম প্রশ্নে oracle “না” বলে: U+D plan কোনো একক রাস্তা-বন্ধে ভাঙে না, তাই উত্তর “হ্যাঁ”। লক্ষ করুন, NTM-এর কাছে বাইরের loop নেই; সে সঠিক plan সরাসরি অনুমান করে একটিমাত্র oracle প্রশ্ন করত। এখানে loop দেখাচ্ছে deterministic simulation-এর খরচ: plan-সংখ্যা সূচকীয় হারে বাড়লে এই loop-ও বাড়ে।

1প্রতিটি plan x (∃ অংশ)2  oracle: ∃y ¬ok(x, y)?3  না হলে: গ্রহণ4সব plan ভাঙলে: বর্জন
যন্ত্রের অবস্থা
plan x
oracle-এর উত্তর
oracle প্রশ্ন
  1. প্রশ্ন সাজানো। ৬টি plan (এক বা দুই hub, U, G, D থেকে) আর ৬টি রাস্তা-বন্ধ (কোনোটিই না, বা ৫টি রাস্তার একটি)। ok(x, y) একটি polynomial সময়ের পরীক্ষা। প্রশ্নের আকার ∃x ∀y: আগে আমাদের চাল, তারপর প্রতিপক্ষের সব চাল।
  2. Plan U. Oracle-কে জিজ্ঞেস: “এমন রাস্তা-বন্ধ আছে, যাতে U-এর hub থেকে কোনো এলাকায় পৌঁছানো যায় না?” হ্যাঁ: U–M বন্ধ হলে উত্তরার hub বাকি চার এলাকা থেকে বিচ্ছিন্ন।
  3. Plan G আর D. দুটিতেই oracle “হ্যাঁ” বলে, একই কারণে: U–M বন্ধ হলে উত্তরায় কোনো hub পৌঁছায় না। এ পর্যন্ত ৩টি প্রশ্ন।
  4. Plan U+G. উত্তরা এখন নিরাপদ, কিন্তু J–D বন্ধ হলে ধানমন্ডি বিচ্ছিন্ন। Oracle আবার “হ্যাঁ”; ৪টি প্রশ্ন।
  5. Plan U+D. দুই প্রান্তেই hub, আর মাঝের M–G–J ত্রিভুজের কোনো একটি রাস্তা বন্ধ হলেও বাকি দুটি দিয়ে যাওয়া যায়। Oracle “না” বলে, তাই যন্ত্র গ্রহণ করে। (G+D পরীক্ষা করা লাগেনি; সেটি U–M বন্ধে ভাঙত।)
  6. শ্রেণি। বাইরের ∃ একটি NTM অনুমান করে, ভেতরের ∀ একটি NP oracle-এর “না” উত্তর দিয়ে মেলে। তাই এই ধরনের প্রতিটি প্রশ্ন NPNP-তে, যার নাম Σ2p (অংশ ৪)। Deterministic simulation-এ এখানে ৫টি প্রশ্ন লেগেছে।

বাস্তবে এই “∃ plan ∀ ঝুঁকি” ধরনের প্রশ্নকে বলে robust বা দুই-ধাপের optimisation: সরবরাহ-শৃঙ্খল, নেটওয়ার্ক নকশা আর সময়সূচিতে প্রায়ই আসে। এদের সমাধানে প্রায়ই একটি SAT বা ILP solver বারবার ডাকা হয়: একটি plan প্রস্তাব, তারপর তাকে ভাঙার চেষ্টা, ভাঙলে সেই প্রতি-উদাহরণ মনে রেখে নতুন প্রস্তাব। এই কৌশলের নাম counterexample-guided খোঁজ; এর প্রতিটি ধাপ ঠিক একটি NP oracle প্রশ্ন।

৪ · Polynomial hierarchy-র সংজ্ঞা — quantifier আর oracle

Nested quantifier-এর অর্থ ক্রমের ওপর নির্ভর করে, যা ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ০৫-এ দেখেছেন: ∃x∀y আর ∀y∃x এক কথা নয়। Polynomial hierarchy এই পালার সংখ্যা গোনে। প্রতিটি quantified বস্তু polynomial দৈর্ঘ্যের string, আর শেষে একটি polynomial সময়ের যাচাই।

সংজ্ঞা ৪.১ (Quantifier রূপ)

k ≥ 1-এর জন্য, L ∈ Σkp যদি একটি polynomial সময়ের deterministic TM V আর একটি polynomial q থাকে, যাতে প্রতিটি x-এর জন্য

x ∈ L ⇔ ∃y1 ∀y2 ∃y3 ⋯ Qkyk : V(x, y1, …, yk) গ্রহণ করে,

যেখানে প্রতিটি |yi| ≤ q(|x|), আর Qk হলো ∃ (k বিজোড়) বা ∀ (k জোড়)। Πkp একই, শুধু প্রথম quantifier ∀, অর্থাৎ Πkp = co-Σkp = {L̄ : L ∈ Σkp}. Σ0p = Π0p = P, আর PH = ⋃k Σkp.

এখানে “p” উপরে লেখা থাকে যাতে computability-র arithmetical hierarchy (Σk0, যেখানে quantifier অসীম ℕ-এর ওপর) থেকে আলাদা বোঝা যায়। k = 1-এ Σ1p = NP (পর্ব ৫৮-এর verifier সংজ্ঞা হুবহু) আর Π1p = coNP. লক্ষ করুন: একই ধরনের quantifier পরপর এলে একটিতে মেশানো যায় (∃y∃z = ∃⟨y, z⟩), তাই শুধু পালাবদলের সংখ্যাই গুরুত্বপূর্ণ।

সংজ্ঞা ৪.২ (Oracle রূপ)

Δ0p = Σ0p = Π0p = P, আর k ≥ 0-এর জন্য

Δk+1p = PΣkp, Σk+1p = NPΣkp, Πk+1p = coNPΣkp.

যেমন Δ2p = PNP, Σ2p = NPNP, Σ3p = NPNPNP.

Albert Meyer আর Larry Stockmeyer ১৯৭২ সালে এই hierarchy প্রস্তাব করেন, আর Stockmeyer এবং Celia Wrathall ১৯৭৬ সালের আলাদা দুটি প্রবন্ধে দুই সংজ্ঞার সমতা আর প্রতিটি স্তরের complete সমস্যা বিস্তারিত দেন বলে পরিচিত। সমতাটি k = 2-এর জন্য পুরো প্রমাণ করা যাক; সাধারণ k-এর প্রমাণ একই ছাঁচে আরোহ (induction) দিয়ে চলে।

উপপাদ্য ৪.৩

NPNP = {L : x ∈ L ⇔ ∃y ∀z V(x, y, z), V polynomial সময়ের, |y|, |z| polynomial}.

প্রমাণ (⊇):

  1. ধরুন x ∈ L ⇔ ∃y ∀z V(x, y, z). B = {⟨x, y⟩ : ∃z ¬V(x, y, z)} নিন। B ∈ NP, কারণ z নিজেই certificate. — NP-এর verifier সংজ্ঞা
  2. NTM NB: “y অনুমান করা; oracle-কে ⟨x, y⟩ জিজ্ঞেস করা; উত্তর ‘না’ হলে গ্রহণ, ‘হ্যাঁ’ হলে বর্জন।” N polynomial সময়ের। — |y| polynomial, প্রশ্ন একটি
  3. N কোনো শাখায় গ্রহণ করে ⇔ এমন y আছে যার জন্য ⟨x, y⟩ ∉ B ⇔ ∃y ∀z V(x, y, z) ⇔ x ∈ L. তাই L ∈ NPB ⊆ NPNP. — B-এর সংজ্ঞা উল্টে

প্রমাণ (⊆):

  1. ধরুন L ∈ NPSAT, NSAT একটি NTM যা nc সময়ে চলে। N-এর একটি শাখা পুরোপুরি বর্ণনা করা যায় একটি string দিয়ে: তার nondeterministic বাছাইগুলো, তার প্রশ্নগুলো φ1, …, φm, আর প্রতিটির জন্য অনুমিত উত্তর a1, …, am ∈ {হ্যাঁ, না}. এর দৈর্ঘ্য polynomial. — সময় nc হলে শাখার বর্ণনা O(nc)
  2. শাখাটি “সত্যিকারের” আর গ্রহণকারী হতে হলে তিনটি শর্ত: (ক) অনুমিত উত্তর মেনে N চালালে ঠিক এই প্রশ্ন আর বাছাই আসে আর N গ্রহণ করে; (খ) যেখানে ai = হ্যাঁ, সেখানে φi সত্যিই satisfiable; (গ) যেখানে ai = না, সেখানে φi সত্যিই unsatisfiable. — oracle-এর উত্তর মিথ্যা হতে পারে না
  3. (ক) polynomial সময়ে মেলে। (খ) একটি ∃: প্রতিটি “হ্যাঁ” প্রশ্নের জন্য একটি satisfying assignment si অনুমান। (গ) একটি ∀: প্রতিটি “না” প্রশ্নের সব assignment ti-তে φi(ti) মিথ্যা। — SAT ∈ NP, UNSAT ∈ coNP
  4. তাই x ∈ L ⇔ ∃(শাখা, s1, s2, …) ∀(t1, t2, …) V(…), যেখানে V তিনটি শর্ত একসঙ্গে মেলায়। এটি ঠিক ∃∀ রূপ। ∎ — সব quantified বস্তু polynomial দৈর্ঘ্যের

প্রমাণের মূল কৌশল মনে রাখার মতো: oracle-এর প্রতিটি “হ্যাঁ” উত্তর একটি ∃ দিয়ে, আর প্রতিটি “না” উত্তর একটি ∀ দিয়ে মেলানো যায়। তাই NP-এর ওপর NP oracle বসালে quantifier-এর একটি পালা বাড়ে। নিচের stepper hierarchy-টি স্তর ধরে গড়ে তোলে।

1Σ0 = Π0 = Δ0 = P2Σ1 = NP, Π1 = coNP3Δk+1 = P^Σk4Σk+1 = NP^Σk5Πk+1 = co-Σk+16PH = ⋃ Σk ⊆ PSPACE
এই স্তরের ছবি
স্তর
oracle রূপ
quantifier রূপ
উদাহরণ
  1. স্তর ০। কোনো quantifier নেই, শুধু polynomial সময়ের V. এটিই P, যেমন PATH আর 2SAT. P-এর oracle কোনো বাড়তি শক্তি দেয় না, তাই এখান থেকেই ওপরে ওঠা শুরু।
  2. স্তর ১। একটি ∃: NP, যেমন SAT. একটি ∀: coNP, যেমন TAUTOLOGY. Oracle রূপে NP = NPP, কারণ P-এর oracle যন্ত্র নিজেই চালাতে পারে।
  3. Δ2 = PNP. Deterministic যন্ত্র NP-কে polynomial-সংখ্যক প্রশ্ন করে, প্রতিটি উত্তর দেখে পরের প্রশ্ন বাছে। এটি NP ∪ coNP ধারণ করে; EXACT-CLIQUE (দুই প্রশ্ন) এখানে। Δ2 ⊆ Σ2 ∩ Π2.
  4. Σ2 আর Π2. NP-এর ওপর NP oracle: একটি ∃, তারপর oracle-এর “না” উত্তর থেকে একটি ∀ (উপপাদ্য ৪.৩)। Robust hub plan ∃∀; MIN-FORMULA ∀∃ (অংশ ৫)।
  5. স্তর ৩। Σ3 = NPΣ2: oracle নিজেই এখন একটি ∃∀ প্রশ্নের উত্তর দেয়, তাই আরও এক পালা: ∃∀∃. প্রতিটি নতুন oracle-স্তর একটি পালা যোগ করে।
  6. সব স্তর একসঙ্গে। PH = সব স্থির k-এর Σk একসঙ্গে। প্রতিটি language কোনো একটি স্থির k-এ বসে। সব স্তর PSPACE-এর ভেতরে; স্তরগুলো সত্যিই আলাদা কি না, তা খোলা প্রশ্ন।

প্রতিটি স্তরের ভেতরের সম্পর্কগুলো সহজেই আসে: Σkp ∪ Πkp ⊆ Δk+1p ⊆ Σk+1p ∩ Πk+1p. প্রথম অন্তর্ভুক্তি: Σk-এর language-কে একবার জিজ্ঞেস (বা উত্তর উল্টে)। দ্বিতীয়টি: deterministic যন্ত্র NTM-এর একটি বিশেষ রূপ, আর PΣk complement-এ বদ্ধ বলে coNPΣk-তেও আছে। নিচের ছবিতে পুরো কাঠামো।

Polynomial hierarchy-র মানচিত্র

প্রতিটি রেখা: নিচের শ্রেণি ওপরেরটির ভেতরে (প্রমাণিত)। কোনো অন্তর্ভুক্তি কঠোর কি না, তা অজানা।

The polynomial hierarchy from P up to PSPACE, with open questions marked P NP = Σ1 SAT coNP = Π1 TAUTOLOGY Δ2 = P^NP EXACT-CLIQUE Σ2 = NP^NP robust plan Π2 = coNP^NP MIN-FORMULA Σ3 Π3 ⋮ ⋮ PH = সব স্তরের মিলন PSPACE TQBF PH = PSPACE? অজানা স্তরগুলো আলাদা? অজানা
ছবি ৬৮.১ — ড্যাশ দেওয়া রেখা মানে PH ⊆ PSPACE প্রমাণিত, কিন্তু সমান কি না অজানা। প্রতিটি নিচের শ্রেণি ওপরের দুটির ভেতরে; যেমন NP ⊆ Δ2 ⊆ Σ2 ∩ Π2. P ≠ NP-ও প্রমাণিত নয়, তাই নিচের ধাপটিও সত্যিই আলাদা কি না অজানা।

৫ · প্রতিটি স্তরের complete সমস্যা — ΣkSAT আর MIN-FORMULA

NP-এর জন্য SAT যা, প্রতিটি স্তরের জন্য তার একটি quantified রূপ ঠিক তাই। একটি Boolean সূত্র φ-এর চলকগুলোকে k টি দলে ভাগ করুন: X1, …, Xk.

উপপাদ্য ৫.১ (Stockmeyer, Wrathall, ১৯৭৬)

ΣkSAT = {⟨φ⟩ : ∃X1 ∀X2 ∃X3 ⋯ QkXk φ সত্য}. প্রতিটি k ≥ 1-এর জন্য ΣkSAT হলো Σkp-complete (≤p-এর অর্থে), আর ∀ দিয়ে শুরু রূপটি ΠkSAT হলো Πkp-complete.

প্রমাণের রূপরেখা: সদস্যপদ সরাসরি: yi = Xi-এর মান, V = “φ-এর মান হিসাব”। কঠিনতার জন্য L ∈ Σkp নিন, x ∈ L ⇔ ∃y1 ⋯ Qkyk V(x, y1, …, yk). x স্থির রাখলে V-এর গণনাটি একটি deterministic polynomial সময়ের গণনা, যাকে পর্ব ৬০-এর tableau কৌশলে একটি সূত্র ψx(y1, …, yk, T)-এ লেখা যায়, যেখানে T হলো tableau-র চলক। Qk = ∃ হলে “V গ্রহণ করে” ⇔ ∃T ψx, আর T-কে শেষ ∃ দলে মিশিয়ে দেওয়া যায়। Qk = ∀ হলে লেখা হয় “∀T (T একটি বৈধ tableau ⇒ গ্রহণ)”, আর T যায় শেষ ∀ দলে; deterministic গণনার tableau একটিই, তাই অর্থ বদলায় না। x থেকে φ বানানো polynomial সময়ের। ∎

এখন বাজারঘরের দ্বিতীয় প্রশ্ন। একটি Boolean সূত্রের আকার = তার চলক-পাতার সংখ্যা (∧, ∨ দিয়ে জোড়া, ¬ শুধু চলকের গায়ে)। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৬৯-এ এমন সূত্র ছোট করার হাতে-কলমে কৌশল দেখেছেন; এখানে প্রশ্নটি তার complexity.

উপপাদ্য ৫.২

MIN-FORMULA = {⟨φ⟩ : φ-এর সমতুল্য কোনো সূত্র φ-এর চেয়ে ছোট নয়} ∈ Π2p.

প্রমাণ:

  1. φ ∈ MIN-FORMULA ⇔ ∀ψ [|ψ| < |φ| ⇒ ∃a : φ(a) ≠ ψ(a)], যেখানে a হলো চলকের একটি মান-বসানো। — “সমতুল্য নয়” মানে কোনো input-এ আলাদা
  2. ψ-এর দৈর্ঘ্য |φ|-এর কম, a-এর দৈর্ঘ্য চলক-সংখ্যার সমান: দুটিই polynomial. — quantified বস্তুর মাপ
  3. V(φ, ψ, a) = “|ψ| ≥ |φ| হলে গ্রহণ; নইলে φ(a) ≠ ψ(a) হলে গ্রহণ”, যা polynomial সময়ে চলে। তাই রূপটি ∀ψ ∃a V, অর্থাৎ Π2p. ∎ — সংজ্ঞা ৪.১, k = 2

এর complement, “φ-এর চেয়ে ছোট সমতুল্য সূত্র আছে”, Σ2p-এ: ∃ছোট ψ ∀a φ(a) = ψ(a). MIN-FORMULA coNP-তে আছে বলে জানা নেই, কারণ “কোনো ছোট সমতুল্য নেই” বোঝাতে প্রতিটি ছোট ψ-এর জন্য আলাদা পার্থক্য-বিন্দু দেখাতে হয়। ছোট সূত্রে brute force করে দেখা যাক। নিচের ব্লক তিন চলকের প্রতিটি Boolean function-এর জন্য সবচেয়ে ছোট সূত্রের আকার বের করে, তারপর কয়েকটি সূত্র MIN-FORMULA-তে আছে কি না বলে। কৌশল: একই truth table-এর সূত্রগুলোকে একসঙ্গে রাখা, যা n = 3-এ চলে কারণ truth table মাত্র 28 = 256টি।

# MIN-FORMULA on 3 variables: formulas with AND/OR gates, literals at leaves.
# size = number of leaves. A truth table is an 8-bit integer (rows 000..111).
from collections import Counter
X, Y, Z = 0b11110000, 0b11001100, 0b10101010     # x, y, z on the 8 rows
FULL = 0xFF
best = {}                        # truth table -> fewest leaves
by_size = {1: {}}
for t, name in ((X, "x"), (Y, "y"), (Z, "z")):
    for tt, nm in ((t, name), (FULL ^ t, "¬" + name)):
        best[tt] = 1; by_size[1][tt] = nm
for s in range(2, 11):           # combine two smaller formulas
    by_size[s] = {}
    for i in range(1, s):
        for a, fa in by_size[i].items():
            for b, fb in by_size[s - i].items():
                for tt, nm in ((a & b, f"({fa}∧{fb})"), (a | b, f"({fa}∨{fb})")):
                    if tt not in best:
                        best[tt] = s; by_size[s][tt] = nm
best.pop(0); best.pop(FULL)      # drop the two constants (x∧¬x, x∨¬x)
print("non-constant functions:", len(best), "of", 2 ** 8 - 2)
print("functions needing s leaves:", sorted(Counter(best.values()).items()))
def check(name, tt, size):       # is a formula of this size minimal?
    m = best[tt]
    print(f"{name:12} leaves {size}, minimum {m}:",
          "minimal" if m == size else "NOT minimal, e.g. " + by_size[m][tt])
check("(x∧y)∨(x∧z)", (X & Y) | (X & Z), 4)
check("x∧(y∨z)", X & (Y | Z), 3)
check("majority", (X & Y) | (X & Z) | (Y & Z), 6)
check("parity x⊕y⊕z", X ^ Y ^ Z, 10)

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

non-constant functions: 254 of 254
functions needing s leaves: [(1, 6), (2, 24), (3, 64), (4, 30), (5, 80), (6, 32), (8, 16), (10, 2)]
(x∧y)∨(x∧z)  leaves 4, minimum 3: NOT minimal, e.g. (x∧(y∨z))
x∧(y∨z)      leaves 3, minimum 3: minimal
majority     leaves 6, minimum 5: NOT minimal, e.g. ((x∧y)∨(z∧(x∨y)))
parity x⊕y⊕z leaves 10, minimum 10: minimal

২৫৪টি অ-ধ্রুবক function-এর প্রত্যেকটির সবচেয়ে ছোট সূত্র পাওয়া গেছে। (x∧y)∨(x∧z) MIN-FORMULA-তে নেই: certificate হলো ছোট সূত্র x∧(y∨z), যা একটি Σ2 “হ্যাঁ”-এর ∃ অংশ, আর সমতা মেলানো ∀ অংশ। তিন ভোটের সংখ্যাগরিষ্ঠতা (majority) পাঠ্যবইয়ের ৬-পাতার রূপে নয়, ৫ পাতায় হয়। আর মাত্র দুটি function-এর ১০টি পাতা লাগে: তিন চলকের parity আর তার উল্টো। কৌতূহলের বিষয়, ৭ বা ৯ পাতার কোনো function নেই। লক্ষ করুন, এই কৌশলের খরচ 22nটি truth table-এর মতো বাড়ে, তাই n = 3-এ সহজ হলেও বড় n-এ অচল।

অন্য স্বাভাবিক সমস্যাগুলো কোথায় বসে, তার একটি সতর্ক তালিকা। “complete” লেখা মানে প্রমাণিত, উল্লিখিত reduction-এর অর্থে।

সমস্যাজানা অবস্থানমন্তব্য
SAT, TAUTOLOGYNP-complete, coNP-completeস্তর ১ (পর্ব ৬০, ৬২)
EXACT-CLIQUEΔ2p-এ (দুই প্রশ্ন)NP বা coNP-তে আছে বলে জানা নেই
UNIQUE-OPTIMUM-TSPΔ2p-completePapadimitriou ১৯৮৪ বলে পরিচিত
Σ2SAT (∃∀ সূত্র)Σ2p-completeউপপাদ্য ৫.১
ছোট সমতুল্য DNF আছে?Σ2p-completeChristopher Umans, ১৯৯৮–২০০১ বলে পরিচিত
ছোট সমতুল্য সূত্র আছে? (MIN-FORMULA-র complement)Σ2p-এ; Turing reduction-এ completeBuchfuhrer আর Umans (প্রকাশ ২০১১) বলে পরিচিত; ≤p-এর অর্থে প্রশ্নটি খোলা বলে জানা যায়
TQBF (পালার সংখ্যা সীমাহীন)PSPACE-completeপর্ব ৬৫; PH-এর কোনো স্তরে আছে বলে জানা নেই

৬ · PH ⊆ PSPACE আর hierarchy ধসে পড়া

উপপাদ্য ৬.১

PH ⊆ PSPACE.

প্রমাণ:

  1. একটি স্থির k আর L ∈ Σkp নিন: x ∈ L ⇔ ∃y1 ∀y2 ⋯ Qkyk V(x, y1, …, yk). — সংজ্ঞা ৪.১
  2. একটি deterministic যন্ত্র recursive ভাবে চলে: y1-এর সব মান পালাক্রমে লিখে, প্রতিটির জন্য বাকি k − 1 পালার প্রশ্নের উত্তর বের করে; ∃ স্তরে একটি “হ্যাঁ” পেলেই হ্যাঁ, ∀ স্তরে একটি “না” পেলেই না। — quantifier-এর অর্থ
  3. যেকোনো মুহূর্তে tape-এ থাকে শুধু বর্তমান y1, …, yk (প্রতিটি q(n) দৈর্ঘ্যের) আর V-এর একটি চলমান গণনা (polynomial জায়গা)। পরের মান চেষ্টার সময় একই জায়গা আবার ব্যবহার হয়। মোট জায়গা O(k · q(n)) + poly(n), যা polynomial. — জায়গার পুনর্ব্যবহার, পর্ব ৬৪
  4. তাই প্রতিটি Σkp ⊆ PSPACE, আর মিলন PH ⊆ PSPACE. ∎ — সময় সূচকীয় হতে পারে, জায়গা নয়

একই কথা অন্যভাবে: ΣkSAT হলো TQBF-এর বিশেষ রূপ, যেখানে পালার সংখ্যা k-তে বাঁধা; আর TQBF PSPACE-এ (পর্ব ৬৫)। নিচের ব্লক ঠিক এই recursive evaluator চালায়, একটিমাত্র shared মান-বসানো buffer দিয়ে, আর ছয়টি ভিন্ন quantifier-ক্রমে একই সূত্র φ যাচাই করে।

# Evaluate Q1 v1 Q2 v2 ... Q6 v6 phi by recursion: time grows, space does not.
# phi: CNF over variables 1..6 (literal -3 means NOT v3)
PHI = [(1, 4, -5), (-1, -4, 6), (2, 5, -6), (-2, -5, 3), (3, 6, 4), (-3, -6, -2)]
A = [None] * 7                       # ONE shared assignment buffer, reused
def phi():
    return all(any(A[abs(l)] == (l > 0) for l in c) for c in PHI)
stats = {}
def ev(prefix, depth):               # each level stores one bit: A[depth + 1]
    stats["calls"] += 1
    stats["depth"] = max(stats["depth"], depth)
    if depth == len(prefix):
        return phi()
    want = prefix[depth] == "E"      # E: one True child is enough; A: one False
    for b in (False, True):
        A[depth + 1] = b
        if ev(prefix, depth + 1) == want:
            return want
    return not want
def blocks(prefix):                  # alternation blocks = level in PH
    return 1 + sum(prefix[i] != prefix[i - 1] for i in range(1, len(prefix)))
print("prefix  class  value  calls  max depth (space)")
for prefix in ("EEEEEE", "AAAAAA", "EEEAAA", "AAAEEE", "EEAAEE", "EAEAEA"):
    stats.update(calls=0, depth=0)
    val = ev(prefix, 0)
    k = blocks(prefix)
    cls = ("Σ" if prefix[0] == "E" else "Π") + str(k)
    print(f"{prefix}  {cls:5}  {val!s:5}  {stats['calls']:5}  {stats['depth']}")
print("worst case calls for 6 variables:", 2 ** 7 - 1)

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

prefix  class  value  calls  max depth (space)
EEEEEE  Σ1     True      14  6
AAAAAA  Π1     False      7  6
EEEAAA  Σ2     False     43  6
AAAEEE  Π2     True      52  6
EEAAEE  Σ3     True      27  6
EAEAEA  Σ6     False     37  6
worst case calls for 6 variables: 127

প্রথম দুই সারি স্তর ১: φ satisfiable (Σ1, True) কিন্তু tautology নয় (Π1, False). তৃতীয় আর চতুর্থ সারি nested quantifier-এর শিক্ষা আবার দেখায়: একই সূত্রে ∃v1v2v3 ∀v4v5v6 মিথ্যা, কিন্তু ∀v1v2v3 ∃v4v5v6 সত্য; ক্রম বদলালে উত্তর বদলায়। সবচেয়ে জরুরি কলাম শেষেরটি: পালার সংখ্যা ১ থেকে ৬ যা-ই হোক, recursion-এর গভীরতা (জায়গা) সবসময় চলক-সংখ্যার সমান, ৬. ডাকের সংখ্যা (সময়) বদলায়, আর সবচেয়ে খারাপ ক্ষেত্রে 27 − 1 = 127 পর্যন্ত যেতে পারে। এটিই PH ⊆ PSPACE-এর প্রমাণের হাতে-কলমে রূপ।

এবার hierarchy-র সবচেয়ে বিখ্যাত ধর্ম: একটি স্তরে দুই দিক মিলে গেলে ওপরের সব স্তর সেখানে নেমে আসে।

উপপাদ্য ৬.২ (Hierarchy ধসে পড়া)

যেকোনো k ≥ 1-এর জন্য, Σkp = Πkp হলে PH = Σkp. বিশেষত NP = coNP হলে PH = NP, আর P = NP হলে PH = P.

1ধরুন NP = coNP2L ∈ Σ2: x ∈ L ⇔ ∃y ∀z V3ভেতরের ∀ অংশ coNP = NP4∃y ∃w W: L ∈ NP5Π2 = coΣ2 ⊆ coNP = NP6আরোহ: Σk = NP সব k-এ
প্রমাণের অবস্থা
দাবি
কারণ
  1. অনুমান। ধরুন NP = coNP. লক্ষ্য: Σ2p ⊆ NP দেখানো, তারপর ওপরের সব স্তর।
  2. একটি Σ2 language নিন। x ∈ L ⇔ ∃y ∀z V(x, y, z), V polynomial সময়ের, |y| আর |z| polynomial.
  3. ভেতরের অংশটিকে আলাদা language হিসেবে দেখুন। B = {⟨x, y⟩ : ∀z V(x, y, z)} হলো coNP-তে। অনুমান অনুযায়ী coNP = NP, তাই B-এর একটি polynomial সময়ের verifier W আর certificate w আছে: ⟨x, y⟩ ∈ B ⇔ ∃w W(x, y, w).
  4. দুটি ∃ মিশিয়ে দিন। x ∈ L ⇔ ∃y ∃w W(x, y, w) ⇔ ∃⟨y, w⟩ W. এটি একটিমাত্র ∃, তাই L ∈ NP. অর্থাৎ Σ2p ⊆ NP, আর NP ⊆ Σ2p আগে থেকেই জানা।
  5. অন্য দিক। Π2p = co-Σ2p ⊆ coNP = NP. তাই Σ2p = Π2p = NP.
  6. আরোহ। Σ3p = NPΣ2 = NPNP = Σ2p = NP, আর একই যুক্তি প্রতিটি স্তরে চলে। তাই PH = NP. সাধারণ k-এর জন্য একই কৌশল: শেষ দুই পালার একটিকে উল্টে পাশের একই রকম quantifier-এর সঙ্গে মেশানো। ∎

সাধারণ k-এর রূপরেখা: ধরুন Σkp = Πkp, আর L ∈ Σk+1p: x ∈ L ⇔ ∃y1 [∀y2 ⋯ Qk+1yk+1 V]. বন্ধনীর ভেতরের অংশ, ⟨x, y1⟩-এর একটি language হিসেবে, k পালার ∀ দিয়ে শুরু, তাই Πkp-এ। অনুমান অনুযায়ী সেটি Σkp-এও, অর্থাৎ ∃z1 ∀z2 ⋯ রূপে লেখা যায়। তখন বাইরের ∃y1 আর ভেতরের ∃z1 মিশে একটি ∃ হয়, আর মোট পালা k-তে নামে: Σk+1p ⊆ Σkp. একই যুক্তি ওপরের প্রতিটি স্তরে পুনরাবৃত্তি করলে PH = Σkp.

এই উপপাদ্য থেকে কয়েকটি গুরুত্বপূর্ণ পরিণাম আসে, যেগুলো পরীক্ষায় প্রায়ই প্রমাণ করতে বলা হয়:

  • PH-এর কোনো complete সমস্যা থাকলে PH ধসে পড়ে। ধরুন B PH-complete (≤p-এর অর্থে)। B ∈ PH, তাই কোনো স্থির k-এর জন্য B ∈ Σkp. প্রতিটি L ∈ PH-এর জন্য L ≤p B, আর Σkp ≤p-এ বদ্ধ, তাই L ∈ Σkp. ফলে PH = Σkp.
  • PH = PSPACE হলে PH ধসে পড়ে। তখন TQBF (PSPACE-complete) PH-complete হতো। তাই বেশিরভাগ গবেষক PH ≠ PSPACE মনে করেন, কিন্তু তা প্রমাণিত নয়; P ≠ PSPACE-ও প্রমাণিত নয়।
  • Karp–Lipton. Richard Karp আর Richard Lipton ১৯৮০ সালে দেখান: SAT-এর polynomial আকারের Boolean circuit থাকলে (NP ⊆ P/poly) PH = Σ2p; Σ2-এ ধসের এই রূপটি ওই প্রবন্ধে Michael Sipser-এর অবদান বলে উল্লেখ আছে। তাই “PH ধসে পড়ে না” বিশ্বাস করলে SAT-এর ছোট circuit নেই, এটিও মানতে হয় (পর্ব ৭০)।
  • Graph isomorphism. GI NP-complete হলে PH = Σ2p (Boppana, Håstad আর Zachos, ১৯৮৭ বলে পরিচিত)। পর্ব ৬৩-এ এটিকেই GI-এর NP-intermediate প্রার্থী হওয়ার একটি কারণ বলা হয়েছিল।

দিক উল্টাবেন না। “P = NP ⇒ PH = P” প্রমাণিত। কিন্তু উল্টোটি, “PH কোথাও ধসে পড়লে P = NP”, ভুল: PH Σ2-এ ধসে পড়েও P ≠ NP থাকতে পারে, এমন কোনো বিরোধ জানা নেই। একইভাবে, “PH অসীম” (সব স্তর আলাদা) প্রমাণিত নয়; এটি P ≠ NP-এর চেয়েও শক্ত একটি অনুমান, কারণ PH অসীম হলে P ≠ NP আসে।

৭ · Relativization আর PH — oracle-জগতে hierarchy

পর্ব ৬৩-এ Baker–Gill–Solovay (১৯৭৫) দেখেছেন: এমন oracle A আছে যাতে PA = NPA, আর এমন B আছে যাতে PB ≠ NPB; তাই যে কৌশল relativize করে, তা একা P বনাম NP মীমাংসা করতে পারে না। পুরো প্রমাণ সেখানে; এখানে প্রশ্নটি PH নিয়ে। সংজ্ঞা ৪.২-এর প্রতিটি শ্রেণিতে একটি oracle A যোগ করলে relativized hierarchy PHA পাওয়া যায়: Σ1p,A = NPA, Σk+1p,A = NPΣkp,A, এভাবে।

  • পুরো ধসের জগৎ। A = TQBF নিলে PA = PSPACE, আর polynomial জায়গায় প্রতিটি oracle প্রশ্নের উত্তর নিজে হিসাব করা যায় বলে প্রতিটি স্তর Σkp,A ⊆ PSPACE. তাই এই জগতে PHA = PA = PSPACE: পুরো hierarchy একতলা।
  • অসীম hierarchy-র জগৎ। Andrew Yao ১৯৮৫ সালে এমন একটি oracle B বানান, যেখানে PHB-এর প্রতিটি স্তর আলাদা আর PHB ≠ PSPACEB; Johan Håstad ১৯৮৬ সালে আরও সরল ও শক্ত প্রমাণ দেন। Ker-I Ko ১৯৮৯ সালে দেখান, যেকোনো k-এর জন্য এমন oracle আছে যেখানে hierarchy ঠিক k স্তরে থামে।
  • Random oracle. Benjamin Rossman, Rocco Servedio আর Li-Yang Tan ২০১৫ সালে দেখান যে একটি random oracle-এর সাপেক্ষে প্রায় নিশ্চিতভাবে (probability 1) PH অসীম, যা বহুদিনের একটি খোলা প্রশ্ন ছিল বলে জানা যায়।

অর্থ পরিষ্কার: যে প্রমাণ-কৌশল relativize করে, তা PH অসীম বা ধসে পড়া, কোনোটিই প্রমাণ করতে পারে না, কারণ দুই রকম জগৎই আছে। আরেকটি সুন্দর সংযোগ আছে: Merrick Furst, James Saxe আর Michael Sipser ১৯৮১ সালের দিকে লক্ষ করেন যে oracle-এর ওপর একটি ∃∀∃⋯ প্রশ্ন আসলে oracle-এর 2nটি bit-এর ওপর একটি OR-AND-OR⋯ circuit, যার গভীরতা পালার সংখ্যার সমান। তাই “স্থির গভীরতার ছোট circuit parity হিসাব করতে পারে না” ধরনের circuit lower bound থেকেই oracle-জগতের এই ফলগুলো আসে। Yao আর Håstad ঠিক এই পথে কাজ করেছেন; বিস্তারিত পর্ব ৭০-এ।

আরও গভীরে: PH-এর সঙ্গে অন্য শ্রেণির দুটি বিস্ময়কর সম্পর্ক প্রমাণিত। Michael Sipser, Péter Gács আর Clemens Lautemann ১৯৮৩ সালে দেখান যে randomized শ্রেণি BPP ⊆ Σ2p ∩ Π2p (পর্ব ৬৯), অর্থাৎ randomness দ্বিতীয় স্তরের বেশি শক্তি দেয় না। আর Seinosuke Toda ১৯৯১ সালে (সম্মেলনে ১৯৮৯) প্রমাণ করেন PH ⊆ P#P: সমাধানের সংখ্যা গোনার একটি oracle পুরো hierarchy-র সব পালা সামলাতে পারে। একটি আধুনিক দৃষ্টিভঙ্গি alternating Turing machine: ∃ আর ∀ state-এর পালাবদল গুনে PH, আর polynomial সময়ে সীমাহীন পালাবদল নিলে ঠিক PSPACE (Chandra, Kozen আর Stockmeyer, ১৯৮১)।

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

  • Σ2p-এর দুটি সংজ্ঞা দিন। ∃y ∀z V(x, y, z) (polynomial দৈর্ঘ্য, polynomial সময়ের V); সমতুল্যভাবে NPNP.
  • MIN-FORMULA কোন স্তরে? Π2p: ∀ছোট ψ ∃a φ(a) ≠ ψ(a).
  • প্রমাণ করুন PH ⊆ PSPACE. Quantifier-গুলো recursive ভাবে পরীক্ষা, একই জায়গা বারবার ব্যবহার; জায়গা O(k · q(n)).
  • NP = coNP হলে কী হয়? PH = NP; ভেতরের ∀ অংশকে ∃ দিয়ে লিখে দুটি ∃ মেশানো।
  • PH-এর কোনো complete সমস্যা আছে? থাকলে PH ধসে পড়ত; তাই বেশিরভাগ গবেষক মনে করেন নেই, কিন্তু প্রমাণিত নয়।

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

Polynomial hierarchy এমন বিষয়, যেখানে সংজ্ঞার একটি ছোট ভুল পুরো যুক্তি নষ্ট করে, আর AI assistant সেই ভুলগুলো আত্মবিশ্বাসের সঙ্গে লেখে। বারবার দেখা যায়: Σ2p-কে “NP ∩ coNP” বলা, quantifier-এর ক্রম উল্টে ∃∀-কে ∀∃ লেখা, Δ2 আর Σ2 গুলিয়ে ফেলা, “PH অসীম প্রমাণিত” বা “PH = PSPACE” লেখা, ধসে পড়ার উপপাদ্যের দিক উল্টে “PH ধসে পড়লে P = NP” বলা, MIN-FORMULA-কে “NP-complete” বলা, আর বানানো সাল বা প্রবন্ধ দেওয়া। ভালো খবর: ছোট instance-এ quantified সূত্র brute force দিয়ে হিসাব করা সহজ, তাই অনেক দাবি নিজে মিলিয়ে নেওয়া যায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“Σ2p = NP ∩ coNP”সংজ্ঞা ৪.১ মেলান: Σ2 = ∃∀, যা NP ∪ coNP-কে ধারণ করে; NP ∩ coNP অনেক ছোট শ্রেণি
∃y ∀z আর ∀z ∃y এক ধরাqbf_space.py-র মতো ছোট সূত্রে দুই ক্রমেই হিসাব করুন; উত্তর আলাদা হতে পারে
“PH অসীম” বা “PH = PSPACE” প্রমাণিতদুটিই খোলা; PH = PSPACE হলে PH ধসে পড়ত
“PH ধসে পড়লে P = NP”প্রমাণিত দিক শুধু P = NP ⇒ PH = P; উল্টোটি জানা নেই
“MIN-FORMULA NP-complete”সদস্যপদ Π2-এ; NP-তে আছে বলে জানা নেই। Reduction-এর অর্থ (≤p না Turing) জিজ্ঞেস করুন
বানানো সাল বা “সম্প্রতি প্রমাণিত”Arora–Barak (অধ্যায় ৫), Sipser বা মূল প্রবন্ধে নিজে খুঁজুন

AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞাটি quantifier আর oracle দুই রূপে লিখতে বলা, প্রতিটি উপপাদ্যের শর্ত চাওয়া, আর প্রতিটি “এই সমস্যা Σk-এ” দাবির জন্য quantified রূপটি স্পষ্ট লিখে ছোট instance-এ brute force দিয়ে মেলানো।

আমি গণনার তত্ত্বের polynomial hierarchy শিখছি। নিচের কাজগুলো করো। ১. Σ2p, Π2p আর Δ2p-এর সংজ্ঞা দাও, quantifier রূপে (polynomial দৈর্ঘ্যের y, z আর polynomial সময়ের V) আর oracle রূপে (NP^NP, coNP^NP, P^NP) লেখো। ২. প্রমাণ করো NP^NP ⊆ ∃∀ শ্রেণি: oracle-এর "হ্যাঁ" আর "না" উত্তর কীভাবে ∃ আর ∀ হয়, ধাপে ধাপে লেখো। ৩. MIN-FORMULA কেন Π2p-এ, quantified রূপটি লেখো। এটি Σ2p-complete কি না জানা আছে কি না, কোন reduction-এর অর্থে, সতর্কভাবে বলো। ৪. "Σk = Πk হলে PH = Σk" উপপাদ্যের k = 1 ক্ষেত্রটি প্রমাণ করো, আর বলো এর উল্টো দিক প্রমাণিত কি না। ৫. প্রতিটি বাক্যের পাশে লেখো "প্রমাণিত", "খোলা" না "অনুমান"। কোনো সাল বা প্রবন্ধ নিশ্চিত না হলে বলো, বানিয়ো না।

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

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

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

প্র ০১NP আর coNP তো আছেই; তাহলে Meyer আর Stockmeyer কেন একটি পুরো hierarchy সংজ্ঞায়িত করার প্রয়োজন বোধ করলেন? কোন বাস্তব প্রশ্ন এর পেছনে ছিল?

১৯৭১–৭২ সালে Cook আর Karp-এর কাজের পর অনেক সমস্যা দ্রুত NP-complete বলে চেনা গেল। কিন্তু কিছু প্রশ্ন এই ছাঁচে বসছিল না। সবচেয়ে স্বাভাবিকটি ছিল circuit বা সূত্র ছোট করা: একটি Boolean সূত্র দেওয়া আছে, এর চেয়ে ছোট সমতুল্য সূত্র আছে কি? Hardware নকশায় এটি পুরোনো ও বাস্তব প্রশ্ন; ডিসক্রিট ম্যাথমেটিক্সে Karnaugh map বা Quine–McCluskey পদ্ধতি এরই ছোট রূপ। এখানে “হ্যাঁ”-এর certificate একটি ছোট সূত্র ψ, কিন্তু ψ সত্যিই সমতুল্য কি না মেলাতে আবার একটি coNP প্রশ্ন লাগে: সব input-এ দুটি সমান কি না। তাই প্রশ্নটি NP-তে আছে বলে মনে হয় না, coNP-তেও না।

Albert Meyer আর Larry Stockmeyer ১৯৭২ সালে regular expression-এর সমতুল্যতা নিয়ে কাজ করতে গিয়ে এই ধরনের প্রশ্নের জন্য একটি কাঠামো প্রস্তাব করেন: NP-এর সংজ্ঞায় একটি ∃ আছে; ∃ আর ∀ পালাক্রমে বাড়ালে কী হয়? এর oracle রূপটি Turing-এর পুরোনো ধারণার polynomial সংস্করণ, আর computability-র arithmetical hierarchy-র (Kleene, Mostowski) সরাসরি অনুকরণ। সেখানে quantifier-এর পালা বাড়ালে কঠোরভাবে নতুন শ্রেণি আসে, যা diagonalization দিয়ে প্রমাণিত। Polynomial জগতে একই কথা প্রমাণ করা যায়নি; বরং দেখা গেল এটি P বনাম NP-এর মতোই কঠিন।

কাঠামোটির মূল্য তিন জায়গায়। প্রথমত, এটি ভাষা দেয়: “এই সমস্যা Σ2-complete” বললে বোঝা যায় এটি সম্ভবত NP-complete সমস্যার চেয়েও কঠিন, আর একটি SAT solver একবার ডাকলে চলবে না। দ্বিতীয়ত, এটি প্রমাণের হাতিয়ার: “এমন হলে PH ধসে পড়ত” দেখিয়ে বহু অনুমানকে বিশ্বাসযোগ্য করা যায়। তৃতীয়ত, এটি PSPACE-এর নিচের একটি সূক্ষ্ম মানচিত্র দেয়।

মূল উপলব্ধি: PH এসেছে এমন বাস্তব প্রশ্ন থেকে (যেমন সূত্র ছোট করা), যেখানে একটি certificate যথেষ্ট নয়; পালাবদল গুনে এটি NP আর PSPACE-এর মাঝখানের জায়গাকে স্তরে ভাগ করে।

প্র ০২“PH ধসে পড়ে না” অনুমানটি কেন এত বেশি ব্যবহৃত হয়? Karp–Lipton আর graph isomorphism-এর ফলগুলো এই অনুমানকে কীভাবে কাজে লাগায়?

Complexity তত্ত্বে প্রায় কোনো আলাদা হওয়া (separation) প্রমাণিত নয়, তাই গবেষকেরা শর্তসাপেক্ষ ফল প্রমাণ করেন: “যদি X, তাহলে Y” ধরনের। P ≠ NP সবচেয়ে পরিচিত শর্ত। কিন্তু অনেক প্রশ্নে P ≠ NP যথেষ্ট শক্ত নয়, আর তখন একটু শক্ত অনুমান ব্যবহার হয়: “PH অসীম”, বা অন্তত “PH কোনো নির্দিষ্ট স্তরে ধসে পড়ে না”। এটি P ≠ NP-এর একটি স্বাভাবিক সাধারণীকরণ: প্রতিটি স্তরে ∃ আর ∀-এর মধ্যে সত্যিকারের ফারাক আছে।

Karp–Lipton উপপাদ্য (১৯৮০) এর সবচেয়ে বিখ্যাত ব্যবহার। প্রশ্নটি: SAT-এর কি polynomial আকারের circuit থাকতে পারে, যদিও polynomial algorithm নেই? Circuit প্রতিটি input-দৈর্ঘ্যের জন্য আলাদা হতে পারে, তাই এটি algorithm-এর চেয়ে দুর্বল দাবি। Karp আর Lipton দেখান, এমন circuit থাকলে PH = Σ2p. প্রমাণের মূল কৌশল: একটি Π2 প্রশ্ন ∀y ∃z-এ ভেতরের ∃z-কে SAT-circuit দিয়ে সমাধান করা যায়, আর সঠিক circuit-টি বাইরে একটি ∃ দিয়ে অনুমান করে self-reducibility দিয়ে মেলানো যায়; ফলে ∀∃ রূপ ∃∀-তে নামে। তাই যিনি বিশ্বাস করেন PH ধসে পড়ে না, তাঁকে মানতে হয় SAT-এর ছোট circuit নেই। এটিই circuit lower bound-কে P ≠ NP-এর একটি পথ বানায় (পর্ব ৭০)।

Graph isomorphism-এর ক্ষেত্রে যুক্তিটি interactive proof দিয়ে চলে: GI-এর complement-এর জন্য একটি ছোট randomized interactive proof আছে (Goldreich, Micali আর Wigderson ১৯৮৬ বলে পরিচিত)। GI NP-complete হলে coNP-এর সব সমস্যার এমন প্রমাণ থাকত, আর Boppana, Håstad আর Zachos ১৯৮৭ সালে দেখান যে তাতে PH Σ2-এ ধসে পড়ে। তাই “GI সম্ভবত NP-complete নয়” কথাটি আসলে “PH সম্ভবত ধসে পড়ে না” থেকে আসা।

লক্ষ করার বিষয়: এই সব যুক্তি একটি অপ্রমাণিত বিশ্বাসের ওপর দাঁড়িয়ে। তবু শর্তসাপেক্ষ ফলের একটি সুবিধা আছে: অনুমানটি কোনোদিন ভুল প্রমাণিত হলে ঠিক কোন কোন ফল বদলাবে, তা আগেই জানা থাকে।

মূল উপলব্ধি: “PH ধসে পড়ে না” হলো P ≠ NP-এর একটি শক্ত, স্বাভাবিক সাধারণীকরণ; Karp–Lipton আর GI-এর ফল এই অনুমানকে ব্যবহার করে circuit আর NP-completeness সম্পর্কে শর্তসাপেক্ষ কিন্তু জোরালো বক্তব্য দেয়।

প্র ০৩Relativization বাধা PH-এর ক্ষেত্রে কী বলে? Oracle-জগতের ফল আর স্থির গভীরতার circuit lower bound কীভাবে জড়িয়ে গেল?

পর্ব ৬৩-এর Baker–Gill–Solovay যুক্তি এখানে হুবহু খাটে, শুধু বেশি জোরে। TQBF oracle-এর সাপেক্ষে PH পুরো ধসে পড়ে, কারণ তখন PTQBF = PSPACE আর প্রতিটি স্তর PSPACE-এর ভেতরে। অন্যদিকে Yao (১৯৮৫) আর Håstad (১৯৮৬) এমন oracle বানান যেখানে প্রতিটি স্তর আলাদা, আর Ko (১৯৮৯) দেখান যেকোনো নির্দিষ্ট স্তরে থামা hierarchy-ও oracle দিয়ে পাওয়া যায়। তাই PH অসীম, PH ধসে পড়ে, PH = PSPACE: এর কোনোটিই relativizing কৌশলে প্রমাণ বা খণ্ডন করা যাবে না।

এই oracle-গুলো বানানোর কৌশলটি নিজেই একটি গল্প। ১৯৮১ সালের দিকে Furst, Saxe আর Sipser লক্ষ করেন যে একটি oracle যন্ত্রের Σk প্রশ্ন, oracle-কে দৈর্ঘ্য n-এর string-এর একটি বিশাল truth table হিসেবে দেখলে, আসলে সেই 2nটি bit-এর ওপর একটি k-গভীরতার AND-OR circuit, যার আকার n-এর polynomial-এর সূচকীয়, অর্থাৎ 2poly(n), কিন্তু 2n bit-এর তুলনায় “quasi-polynomial” মাপের। Parity-র মতো একটি function যদি স্থির গভীরতার এমন circuit-এ হিসাব করা না যায়, তাহলে একটি oracle বানানো যায় যেখানে PSPACEB-এর একটি language PHB-এর বাইরে। তাঁরা এবং স্বাধীনভাবে Ajtai parity-র superpolynomial lower bound দেন; Yao আর Håstad সেটিকে সূচকীয় আর গভীরতা-নির্ভর করে oracle-ফল পান। Håstad-এর switching lemma এখন circuit complexity-র একটি মৌলিক হাতিয়ার।

Random oracle-এর প্রশ্ন বহুদিন খোলা ছিল বলে জানা যায়: সব oracle নয়, “সাধারণ” একটি random oracle-এর সাপেক্ষে PH কি অসীম? Rossman, Servedio আর Tan ২০১৫ সালে একটি average-case depth hierarchy উপপাদ্য প্রমাণ করে উত্তর দেন: হ্যাঁ, probability 1-এ।

এর শিক্ষা দুই দিকের। একদিকে, oracle-ফল মনে করিয়ে দেয় যে আসল PH-এর প্রশ্নে relativize না করে এমন কৌশল লাগবে। অন্যদিকে, এই ফলগুলো circuit lower bound-এর সবচেয়ে সফল এলাকা (স্থির গভীরতার circuit) তৈরি করেছে।

মূল উপলব্ধি: Oracle-জগতে PH ধসে পড়তেও পারে, অসীমও হতে পারে, তাই relativizing কৌশল একা যথেষ্ট নয়; আর এই oracle-গুলো বানাতে গিয়েই স্থির গভীরতার circuit-এর lower bound তত্ত্ব জন্মেছে।

প্র ০৪সীমিত পালার খেলা আর robust planning কেন PH-এর স্বাভাবিক জায়গা? বাস্তবে ∃∀ সমস্যা কীভাবে সমাধান করা হয়?

দুই খেলোয়াড়ের একটি খেলা ভাবুন, যেখানে প্রতিটি চাল polynomial দৈর্ঘ্যের, আর খেলা ঠিক k চালে শেষ হয়, শেষে কে জিতল তা polynomial সময়ে মেলানো যায়। “প্রথম খেলোয়াড়ের জেতার কৌশল আছে কি” প্রশ্নটি ঠিক ∃চাল1 ∀চাল2 ∃চাল3 ⋯, অর্থাৎ Σkp. চালের সংখ্যা input-এর সঙ্গে বাড়লে (যেমন n × n বোর্ডে generalized geography) পালার সংখ্যা স্থির থাকে না, আর প্রশ্নটি PSPACE-এ উঠে যায়, যেখানে TQBF আর এমন খেলা complete (পর্ব ৬৫)। তাই PH হলো “স্থির সংখ্যক পালার খেলা”, আর PSPACE “polynomial সংখ্যক পালার খেলা”।

বাজারঘরের robust hub plan ঠিক দুই পালার খেলা: আমরা plan বাছি, প্রকৃতি (বা প্রতিপক্ষ) একটি রাস্তা বন্ধ করে। Operations research-এ একে robust বা দুই-ধাপের optimisation বলে; সাইবার নিরাপত্তায় attacker-defender মডেল, আর সফটওয়্যার যাচাইয়ে “এমন একটি parameter আছে যাতে সব input-এ program ঠিক চলে” ধরনের synthesis প্রশ্ন একই আকারের।

বাস্তবে এদের সমাধানে প্রায়ই সেই কৌশলটি ব্যবহার হয় যা NPNP-এর সংজ্ঞায় লুকিয়ে আছে: একটি SAT বা ILP solver বারবার ডাকা। Counterexample-guided খোঁজে (CEGAR-ধাঁচের loop) প্রথম solver একটি plan প্রস্তাব করে, দ্বিতীয় solver সেই plan ভাঙার একটি পরিস্থিতি খোঁজে; পেলে সেটিকে শর্ত হিসেবে প্রথম solver-এ যোগ করা হয়। সবচেয়ে খারাপ ক্ষেত্রে loop সূচকীয় বার ঘুরতে পারে, কারণ সমস্যাটি Σ2-complete হতে পারে; কিন্তু বাস্তবের instance-এ প্রায়ই অল্প কয়েকটি প্রতি-উদাহরণেই plan স্থির হয়। ২QBF বা পূর্ণ QBF solver-ও আছে, আর প্রতিযোগিতায় তাদের তুলনা হয়।

সতর্কতা দুটি: এই solver-ভিত্তিক সাফল্য PH ধসে পড়ার প্রমাণ নয়, আর একটি Σ2 সমস্যাকে একবারের SAT-এ লেখার চেষ্টা সাধারণত সূচকীয় আকারের সূত্র তৈরি করে, কারণ ∀ অংশটি সব পরিস্থিতি খুলে লিখতে হয়।

মূল উপলব্ধি: স্থির k পালার খেলা আর robust planning স্বাভাবিকভাবে Σkp-এ বসে; বাস্তবে এদের সমাধান হয় SAT solver বারবার ডেকে, যা NPNP-এর oracle সংজ্ঞারই প্রকৌশল রূপ।

প্র ০৫Toda-এর উপপাদ্য PH ⊆ P#P কেন বিস্ময়কর? “গোনা” আর “পালাবদল”-এর সম্পর্ক থেকে আমরা কী শিখি?

#SAT হলো একটি সূত্রের satisfying assignment-এর সংখ্যা গোনার সমস্যা, আর #P এমন গোনার function-গুলোর শ্রেণি, যা Leslie Valiant ১৯৭৯ সালে সংজ্ঞায়িত করেন। প্রথম দেখায় গোনা শুধু NP-এর একটু শক্ত রূপ মনে হয়: সংখ্যাটি শূন্যের বেশি কি না জানলেই SAT. কিন্তু Seinosuke Toda ১৯৮৯ সালের সম্মেলনে আর ১৯৯১ সালের প্রবন্ধে দেখান যে একটিমাত্র #P oracle প্রশ্নের সঙ্গে polynomial সময়ের যন্ত্র পুরো polynomial hierarchy সামলাতে পারে: PH ⊆ P#P. অর্থাৎ যেকোনো স্থির সংখ্যক ∃∀ পালার প্রশ্ন “কতগুলো সমাধান আছে” প্রশ্নে রূপান্তর করা যায়।

প্রমাণের দুটি ধাপ, আর দুটিই randomness ব্যবহার করে। প্রথম ধাপে, Valiant আর Vazirani-র (১৯৮৬) isolation কৌশলের মতো random hashing দিয়ে একটি ∃ quantifier-কে “সমাধানের সংখ্যা বিজোড় কি না” (⊕P) প্রশ্নে বদলানো হয়, ছোট ভুলের সম্ভাবনাসহ; পালাক্রমে এটি পুরো hierarchy-কে randomized ⊕P যন্ত্রে নামায়। দ্বিতীয় ধাপে, একটি বীজগাণিতিক কৌশলে randomness আর parity দুটিকেই একটি #P গোনার ভেতরে ঢুকিয়ে দেওয়া হয়। এই কাজের জন্য Toda ১৯৯৮ সালে Gödel Prize পান বলে পরিচিত।

এর শিক্ষা গভীর। “পালাবদল” (একজন বাছে, আরেকজন সাড়া দেয়) আর “গোনা” (সব সম্ভাবনার যোগফল) প্রথম দেখায় ভিন্ন ধরনের শক্তি; Toda দেখান গোনা অন্তত পালাবদলের সমান শক্তিশালী। একই সঙ্গে এটি সতর্ক করে: #P-এর জন্য দ্রুত algorithm, এমনকি ভালো approximation-এর কিছু রূপও, পুরো PH-কে নামিয়ে আনত। Permanent গোনা #P-complete (Valiant ১৯৭৯), তাই permanent-এর দ্রুত algorithm PH-কে P-তে নামিয়ে দিত। সেই কারণেই geometric complexity theory-র মতো কর্মসূচি permanent বনাম determinant-কে গুরুত্ব দেয় (পর্ব ৬৩-এর আরও গভীরে)।

মূল উপলব্ধি: Toda-এর উপপাদ্য দেখায় সমাধান গোনার শক্তি polynomial hierarchy-র সব পালাবদলের চেয়ে কম নয়, তাই #P-এর কঠিনতা PH-এর কঠিনতার একটি ঊর্ধ্বসীমা দেয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের সূত্র বা graph বসিয়েও যাচাই করতে পারেন।

  1. নকশা (oracle যন্ত্র ও quantifier রূপ): EXACT-CLIQUE = {⟨G, k⟩ : G-এর সবচেয়ে বড় clique-এর আকার ঠিক k}. (ক) একটি PSAT যন্ত্র নকশা করুন যা ঠিক দুটি oracle প্রশ্ন করে। (খ) EXACT-CLIQUE-কে ∃∀ রূপে লিখে দেখান এটি Σ2p-এ। (গ) বাজারঘরের ছয় গুদামের graph-এ চালান: edge {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {4,5}, {5,6}, {4,6}; k = 3 আর k = 2-এর উত্তর কী?

    (ক) “⟨G, k⟩-এ: CLIQUE-কে SAT-এ reduce করে জিজ্ঞেস ‘G-এ k-clique আছে?’; তারপর ‘G-এ (k + 1)-clique আছে?’। প্রথমটি হ্যাঁ আর দ্বিতীয়টি না হলে গ্রহণ, নইলে বর্জন।” দুটি reduction polynomial, তাই EXACT-CLIQUE ∈ PSAT = Δ2p. সঠিকতা: সবচেয়ে বড় clique ঠিক k ⇔ k-clique আছে আর (k + 1)-clique নেই (বড় clique থাকলে তার যেকোনো k + 1টি vertex-ও clique হয়)।

    (খ) ⟨G, k⟩ ∈ EXACT-CLIQUE ⇔ ∃C ∀S [C একটি k-clique ∧ (|S| = k + 1 ⇒ S clique নয়)]. C আর S vertex-এর তালিকা, দৈর্ঘ্য polynomial; ভেতরের শর্ত polynomial সময়ে মেলে। তাই Σ2p-এ; একইভাবে ∀S ∃C রূপে লিখলে Π2p-এও।

    (গ) 3-clique আছে ({1,2,3}, {2,3,4}, {4,5,6}), কিন্তু কোনো 4-clique নেই। তাই k = 3: প্রথম প্রশ্ন হ্যাঁ, দ্বিতীয় না → গ্রহণ। k = 2: প্রথম প্রশ্ন হ্যাঁ, কিন্তু “3-clique আছে?” হ্যাঁ → বর্জন। (সব subset scratch-এ brute force দিয়ে মেলানো।)

  2. প্রমাণ: প্রমাণ করুন: P = NP হলে PH = P. প্রতিটি ধাপের কারণ লিখুন।

    ১. P = NP হলে NP = coNP, কারণ P complement-এ বদ্ধ: L ∈ NP = P ⇒ L̄ ∈ P = NP. ২. উপপাদ্য ৬.২ (k = 1) থেকে PH = NP. ৩. NP = P, তাই PH = P. ∎

    সরাসরি আরোহেও করা যায়: দাবি Σkp = P সব k-এর জন্য। k = 1: অনুমান। k → k + 1: Σk+1p = NPΣkp = NPP = NP = P, কারণ P-এর oracle যন্ত্র নিজেই polynomial সময়ে simulate করতে পারে (তথ্য ৪, অংশ ২)। লক্ষ করুন, “NPP = NP” ধাপটি oracle শ্রেণির সংজ্ঞা থেকে আসে; এটি relativize করে, তাই প্রমাণটিও relativize করে, যা সমস্যা নয়, কারণ এটি একটি শর্তসাপেক্ষ বক্তব্য।

  3. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: PH = PSPACE. প্রমাণ: TQBF PSPACE-complete. প্রতিটি TQBF সূত্রে quantifier-এর পালা সসীম, ধরি k, তাই সূত্রটি ΣkSAT বা ΠkSAT-এর একটি instance, যা PH-এ। তাই TQBF ∈ PH, আর PSPACE ⊆ PH. ∎” ভুলটি কোথায়? আর দাবিটি সত্য হলে কী হতো?

    ভুলটি “প্রতিটি instance কোনো স্তরে, তাই language-টি PH-এ” ধাপে। একটি language PH-এ থাকতে হলে একটি স্থির k থাকতে হবে, যাতে সব instance একই Σk যাচাই দিয়ে মেলে। TQBF-এ পালার সংখ্যা input-এর সঙ্গে বাড়ে (n চলকের সূত্রে n পর্যন্ত), তাই কোনো একটি k সব instance-কে ঢাকে না। “প্রতিটি instance সসীম” আর “একটি স্থির সীমা আছে” আলাদা কথা, যেমন প্রতিটি স্বাভাবিক সংখ্যা সসীম কিন্তু সব সংখ্যার একটি সাধারণ ঊর্ধ্বসীমা নেই।

    দাবিটি সত্য হলে TQBF কোনো Σkp-এ থাকত, আর TQBF PSPACE-complete বলে PSPACE ⊆ Σkp, অর্থাৎ PH = Σkp: hierarchy ধসে পড়ত। PH = PSPACE কি না খোলা প্রশ্ন, আর বেশিরভাগ গবেষক মনে করেন সমান নয়।

  4. হিসাব (আউটপুট অনুমান): qbf_space.py-র ev ফাংশনে PHI = [(1, 2), (1, −2)], অর্থাৎ φ = (v1 ∨ v2) ∧ (v1 ∨ ¬v2), আর দুটি prefix চালানো হলো: "EA" (∃v1 ∀v2) আর "AE" (∀v1 ∃v2). প্রতিটির value, calls আর max depth কত হবে? প্রতিটি কোন শ্রেণির রূপ?

    "EA": মূল (ডাক ১) → v1 = False (ডাক ২) → v2 = False-এ পাতা (ডাক ৩): (F ∨ F) মিথ্যা, তাই ∀ সঙ্গে সঙ্গে False ফেরত দেয়। তারপর v1 = True (ডাক ৪) → দুই পাতা (ডাক ৫, ৬) দুটিই সত্য → True. মূল ∃ True পায়। ফল: value True, calls 6, max depth 2; রূপ Σ2.

    "AE": মূল (ডাক ১) → v1 = False (ডাক ২) → v2 = False (ডাক ৩) মিথ্যা, v2 = True (ডাক ৪): (F ∨ T) ∧ (F ∨ F) মিথ্যা। ∃ শাখা False, তাই ∀ মূল সঙ্গে সঙ্গে False. ফল: value False, calls 4, max depth 2; রূপ Π2. φ আসলে v1-এর সমতুল্য, তাই v1-এর ওপর ∃ সত্য আর ∀ মিথ্যা। (দুটি ফলই scratch-এ একই code চালিয়ে মেলানো।)

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

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

ক্রম“NP = coNP হলে Σ2p = NP” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ধরুন NP = coNP, আর L ∈ Σ2p: x ∈ L ⇔ ∃y ∀z V(x, y, z)
  2. ভেতরের language B = {⟨x, y⟩ : ∀z V(x, y, z)} coNP-তে
  3. NP = coNP বলে B-এর verifier W আছে: ⟨x, y⟩ ∈ B ⇔ ∃w W(x, y, w)
  4. তাই x ∈ L ⇔ ∃⟨y, w⟩ W(x, y, w), অর্থাৎ L ∈ NP
  5. Complement নিয়ে Π2p ⊆ coNP = NP, তাই Σ2p = Π2p = NP

Σ2p-এর সঠিক বর্ণনা কোনটি?

  • NP ∩ coNP
  • যেসব L-এর জন্য x ∈ L ⇔ ∀y ∃z V(x, y, z)
  • যেসব L-এর জন্য x ∈ L ⇔ ∃y ∀z V(x, y, z), যেখানে y, z polynomial দৈর্ঘ্যের আর V polynomial সময়ের
  • PNP

একটি NP oracle-সহ nondeterministic polynomial সময়ের যন্ত্র NP-এর চেয়ে বেশি শক্তিশালী হতে পারে বলে মনে করা হয় কেন?

  • কারণ oracle-কে সূচকীয় দৈর্ঘ্যের প্রশ্ন করা যায়
  • কারণ যন্ত্রটি oracle-এর “না” উত্তর ব্যবহার করে একটি coNP বক্তব্য জেনে নিতে পারে
  • কারণ oracle মাঝে মাঝে ভুল উত্তর দেয়, যা randomness যোগ করে
  • কারণ এটি সব decidable language চেনে

যদি NP = coNP প্রমাণিত হয়, polynomial hierarchy সম্পর্কে কী প্রমাণযোগ্যভাবে আসে?

  • PH = NP
  • PH = P
  • PH = PSPACE
  • PH-এর সব স্তর আলাদা থাকে

PH আর PSPACE-এর সম্পর্ক নিয়ে কোন বক্তব্যটি সঠিক?

  • PH = PSPACE প্রমাণিত
  • PH ⊊ PSPACE প্রমাণিত
  • TQBF Σ3p-এ আছে
  • PH ⊆ PSPACE প্রমাণিত, আর PH = PSPACE হলে PH কোনো স্তরে ধসে পড়ত

MIN-FORMULA = {⟨φ⟩ : φ-এর সমতুল্য কোনো সূত্র φ-এর চেয়ে ছোট নয়}. এর সম্পর্কে কোনটি প্রমাণিত?

  • MIN-FORMULA NP-complete
  • MIN-FORMULA ∈ Π2p
  • MIN-FORMULA ∈ P, কারণ truth table দেখে ছোট করা যায়
  • MIN-FORMULA undecidable

Oracle-জগতে polynomial hierarchy সম্পর্কে কোনটি প্রমাণিত?

  • প্রতিটি oracle A-তে PHA ধসে পড়ে
  • প্রতিটি oracle A-তে PHA অসীম
  • এমন oracle আছে যেখানে PH ধসে পড়ে, আর এমনও আছে যেখানে PH অসীম
  • Oracle-ফল থেকে প্রমাণিত যে আসল PH অসীম

বাজারঘরের প্রশ্ন: “বড়জোর দুটি hub-এর এমন একটি বাছাই আছে কি, যাতে যেকোনো একটি রাস্তা বন্ধ হলেও প্রতিটি এলাকায় পৌঁছানো যায়?” (plan আর রাস্তা-বন্ধ polynomial দৈর্ঘ্যে লেখা, আর পৌঁছানো যায় কি না polynomial সময়ে মেলে)। এই ধরনের প্রশ্নের সাধারণ রূপ স্বাভাবিকভাবে কোন শ্রেণিতে পড়ে?

  • P, কারণ graph-search polynomial
  • NP, কারণ plan-টিই certificate
  • coNP, কারণ “সব রাস্তা-বন্ধ” একটি ∀
  • Σ2p, কারণ রূপটি ∃plan ∀রাস্তা-বন্ধ ok(plan, বন্ধ)

শব্দকোষ

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

মনে রাখুন

  1. Oracle class: PA, NPA; PNP = PSAT, NPNP = NPcoNP, আর NP ∪ coNP ⊆ PNP. EXACT-CLIQUE দুই প্রশ্নে PNP-এ।
  2. Σkp = k পালার ∃∀⋯ (polynomial দৈর্ঘ্য, polynomial সময়ের V) = NPΣk−1p; Πkp = co-Σkp; Δk+1p = PΣkp; PH = ⋃ Σkp.
  3. ΣkSAT প্রতিটি স্তরে complete; MIN-FORMULA ∈ Π2p; robust “∃ plan ∀ ঝুঁকি” প্রশ্ন Σ2-এর রূপ।
  4. প্রমাণিত: PH ⊆ PSPACE; Σk = Πk ⇒ PH = Σk; P = NP ⇒ PH = P; PH-এর complete সমস্যা বা PH = PSPACE ⇒ ধস। খোলা: PH অসীম কি না, PH = PSPACE কি না।
  5. Oracle-জগতে PH পুরো ধসে পড়তেও পারে (TQBF), অসীমও হতে পারে (Yao, Håstad; random oracle ২০১৫); তাই relativizing কৌশল একা যথেষ্ট নয়।

পরের পর্বে: যন্ত্রের হাতে একটি মুদ্রা: probabilistic Turing machine, RP, BPP আর ZPP, ভুলের সম্ভাবনা কমানোর amplification, Miller–Rabin আর Freivalds-এর মতো randomized algorithm, আর এই পর্বের আরও গভীরে বলা BPP ⊆ Σ2p ∩ Π2p-এর প্রেক্ষাপট (পর্ব ৬৯)।

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

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