এই পর্বে যা শিখবেন
- Boolean circuit-এর আনুষ্ঠানিক সংজ্ঞা, size আর depth, আর gate ধরে ধরে একটি circuit-এর মান বের করা
- প্রতিটি function-এর circuit আছে কেন, আর Shannon-এর গণনায় প্রায় সব function-এর বিশাল circuit লাগে কেন (পূর্ণ প্রমাণ)
- Circuit family, uniformity, P/poly আর advice-এর সম্পর্ক, আর P ⊆ P/poly-র tableau প্রমাণ
- CIRCUIT-SAT কেন NP-complete, আর circuit থেকে CNF-এ যাওয়ার Tseitin কৌশল
- NC, AC0, PARITY ∉ AC0, Karp–Lipton, আর circuit lower bound-এ কী প্রমাণিত আর কী খোলা
১ · Boolean circuit — gate দিয়ে বানানো হিসাব
এ পর্যন্ত এই কোর্সের প্রতিটি যন্ত্র ছিল একটি “অভিন্ন” algorithm: একটি Turing machine যেকোনো দৈর্ঘ্যের input নেয়। বাস্তবের chip অন্যরকম। একটি 64-bit adder শুধু 64-bit সংখ্যা যোগ করে; 128 bit-এর জন্য আলাদা chip লাগে। প্রতিটি chip হলো logic gate-এর একটি স্থির জাল (Computer Architecture কোর্সের পর্ব ০৮)। এই পর্বে সেই জালকে গণনার একটি গাণিতিক model হিসেবে দেখব, আর প্রশ্ন করব: একটি কাজের জন্য সবচেয়ে ছোট জাল কত বড়?
পরীক্ষার ফল তৈরির কথা ভাবুন। একটি বোর্ডের ফল-কক্ষে কয়েকজন কর্মী সারি বেঁধে বসে আছেন। প্রথম সারির প্রত্যেকে দুটি নম্বর দেখে একটি ছোট সিদ্ধান্ত নেন (“দুটিতেই পাস?”), পরের সারি আগের সারির সিদ্ধান্ত মিলিয়ে আবার সিদ্ধান্ত নেয়, আর শেষ কর্মী চূড়ান্ত ফল ঘোষণা করেন। কর্মীর মোট সংখ্যা হলো খরচ (size), আর সারির সংখ্যা হলো কত দ্রুত ফল বেরোবে (depth), কারণ একই সারির সবাই একসঙ্গে কাজ করতে পারেন।
n-টি input-এর একটি Boolean circuit C হলো একটি directed acyclic graph (চক্রহীন directed graph), যার
- n-টি input node x1, …, xn, যাদের কোনো আগত তীর নেই;
- বাকি প্রতিটি node একটি gate: ∧ (AND) বা ∨ (OR), যার ঠিক দুটি আগত তীর (fan-in 2), অথবা ¬ (NOT), যার একটি;
- একটি gate চিহ্নিত output gate.
Input x ∈ {0, 1}n দিলে gate-গুলোর মান topological ক্রমে হিসাব হয়, আর output gate-এর মান C(x). এভাবে C একটি Boolean function f: {0, 1}n → {0, 1} হিসাব করে। size(C) = gate-এর সংখ্যা (input node গোনা হয় না), depth(C) = কোনো input থেকে output পর্যন্ত দীর্ঘতম পথে gate-এর সংখ্যা।
লক্ষ করুন, একটি gate-এর output যতগুলো খুশি gate-এ যেতে পারে (fan-out সীমাহীন)। এটিই circuit-কে Boolean সূত্র (formula) থেকে আলাদা করে: সূত্রে প্রতিটি উপ-রাশি একবারই ব্যবহার হয়, circuit-এ একবার হিসাব করা মান বারবার ব্যবহার করা যায়। ¬-gate একটি input নেয় বলে একে অনেক বই size-এ গোনে না; এই পর্বে গোনা হবে, যাতে Python-এর হিসাব আর লেখা মেলে। এমন রীতির পার্থক্য size-কে শুধু একটি ধ্রুবক গুণ বদলায়।
বাজারঘরের একটি নিয়ম দিয়ে শুরু করা যাক। তিনটি bit: x1 = 1 মানে ঠিকানা ঢাকা জেলায়, x2 = 1 মানে অর্ডার ১০০০ টাকার বেশি, x3 = 1 মানে গ্রাহক একটি কুপন দিয়েছেন। নিয়ম: “ঢাকায় বড় অর্ডার, অথবা ঢাকার বাইরে কুপন থাকলে ফ্রি ডেলিভারি।” অর্থাৎ
f(x1, x2, x3) = (x1 ∧ x2) ∨ (x3 ∧ ¬x1)
চারটি gate-এ: g1 = ¬x1, g2 = x1 ∧ x2, g3 = x3 ∧ g1, g4 = g2 ∨ g3 (output). x1 দুটি gate-এ যায়, এটি fan-out-এর একটি উদাহরণ।
বাজারঘরের ফ্রি-ডেলিভারি circuit
ওপরে তিনটি input, নিচে output. প্রতিটি বৃত্ত একটি gate; size ৪, depth ৩.
নিচের stepper input x = (0, 1, 1)-এ, অর্থাৎ ঢাকার বাইরে, বড় অর্ডার, কুপন আছে, এমন একটি অর্ডারে circuit-টি gate ধরে ধরে চালায়।
1x1, x2, x3 ← input2g1 = ¬x13g2 = x1 ∧ x24g3 = x3 ∧ g15g4 = g2 ∨ g3 → output
| হিসাব | |
| এই node-এর গভীরতা |
- Input. তিনটি input node-এ মান বসে: x1 = 0 (ঢাকার বাইরে), x2 = 1, x3 = 1. Input-এর গভীরতা ০ ধরা হয়।
- g1 = ¬x1. ¬0 = 1. এই gate শুধু input পড়ে, তাই গভীরতা ১.
- g2 = x1 ∧ x2. 0 ∧ 1 = 0. g1 আর g2 একে অপরের ওপর নির্ভর করে না, তাই বাস্তবের chip-এ দুটি একসঙ্গে হিসাব হয়; দুটিরই গভীরতা ১.
- g3 = x3 ∧ g1. 1 ∧ 1 = 1. এটি g1-এর ফলের জন্য অপেক্ষা করে, তাই গভীরতা ২.
- g4 = g2 ∨ g3. 0 ∨ 1 = 1. দীর্ঘতম পথ x1 → g1 → g3 → g4, তাই গভীরতা ৩.
- ফল. C(0, 1, 1) = 1: ফ্রি ডেলিভারি। Size ৪ মানে মোট কাজ, depth ৩ মানে সবচেয়ে ধীর পথ, অর্থাৎ পর্যাপ্ত কর্মী থাকলে কত “সারি” সময় লাগে।
একটি function-এর circuit complexity হলো তাকে হিসাব করে এমন সবচেয়ে ছোট circuit-এর size. ছোট n-এ এটি brute force-এ বের করা যায়: ০ gate থেকে শুরু করে প্রতিটি সম্ভাব্য gate যোগ করে দেখা কোন কোন function পাওয়া গেল। নিচের ব্লক প্রথমে ওপরের circuit চালায়, তারপর ২-input-এর সব ১৬টি function আর ৩-input-এর ২৫৬টি function-এর সবচেয়ে ছোট circuit খোঁজে (৩-input-এ ৬ gate পর্যন্ত)। Function-কে লেখা হয়েছে তার truth table-এর output কলাম দিয়ে, input 00…0 থেকে 11…1 ক্রমে।
# A Boolean circuit = a list of gates; each gate reads earlier wires.
from itertools import product
from collections import Counter
def evaluate(n, gates, x):
w = list(x) # wires 0..n-1 are the inputs
for op, a, b in gates:
w.append(1 - w[a] if op == "NOT" else
w[a] & w[b] if op == "AND" else w[a] | w[b])
return w[n:] # every gate's value; last = output
# free delivery = (x1 AND x2) OR (x3 AND NOT x1)
C = [("NOT", 0, 0), ("AND", 0, 1), ("AND", 2, 3), ("OR", 4, 5)]
print("g1..g4 on x = (0,1,1):", evaluate(3, C, (0, 1, 1)))
print("output column:", [evaluate(3, C, x)[-1] for x in product((0, 1), repeat=3)])
def min_sizes(n, limit): # exact minimum gates, functions as bitmasks
N = 2 ** n; FULL = 2 ** N - 1
X = [sum(1 << (N - 1 - r) for r, x in enumerate(product((0, 1), repeat=n)) if x[i])
for i in range(n)]
best, seen = {x: 0 for x in X}, set()
def grow(wires, size):
if frozenset(wires) in seen: return
seen.add(frozenset(wires))
for i, a in enumerate(wires):
for g in [FULL ^ a] + [g for b in wires[i:] for g in (a & b, a | b)]:
if g in wires: continue # a repeated wire never helps
best[g] = min(best.get(g, 99), size + 1)
if size + 1 < limit: grow(wires + [g], size + 1)
grow(X, 0)
return best
b2 = min_sizes(2, 4)
print("n=2:", sorted(Counter(b2.values()).items()), "| XOR 0110 needs", b2[0b0110])
b3 = min_sizes(3, 6)
print("n=3, at most 6 gates:", sorted(Counter(b3.values()).items()))
print("found", len(b3), "of 256; parity 01101001 found:", 0b01101001 in b3)আসল আউটপুট (ব্রাউজারের Python):
g1..g4 on x = (0,1,1): [1, 0, 1, 1]
output column: [0, 1, 0, 1, 0, 0, 1, 1]
n=2: [(0, 2), (1, 4), (2, 8), (4, 2)] | XOR 0110 needs 4
n=3, at most 6 gates: [(0, 3), (1, 9), (2, 28), (3, 44), (4, 37), (5, 82), (6, 35)]
found 238 of 256; parity 01101001 found: False
প্রথম লাইন stepper মেলায়: g1…g4 = 1, 0, 1, 1. দ্বিতীয় লাইন পুরো truth table: x1 = 0 হলে output x3-এর সমান (0, 1, 0, 1), x1 = 1 হলে x2-এর সমান (0, 0, 1, 1). n = 2-এ: দুটি function (x1, x2 নিজেরা) ০ gate-এ, ৪টি ১ gate-এ, ৮টি ২ gate-এ, আর ৩ gate-এ নতুন কিছু নেই; সবচেয়ে কঠিন দুটি, XOR (0110) আর তার উল্টো (1001), ৪ gate নেয়। এমনকি ধ্রুবক 0 (0000)-এর জন্যও ২ gate লাগে: x1 ∧ ¬x1. n = 3-এ ৬ gate পর্যন্ত ২৩৮টি function পাওয়া গেছে, বাকি ১৮টির জন্য আরও বেশি লাগে, আর তাদের মধ্যে আছে PARITY (01101001). একই খোঁজ scratch-এ (সাধারণ CPython 3.14) ৮ gate পর্যন্ত চালালে প্রায় ৩২ সেকেন্ডে ২৫৬টি function-ই পাওয়া যায়: সবচেয়ে কঠিন ৮টি function-এর জন্য ৮ gate লাগে, PARITY তাদের একটি। সংখ্যাগুলো দ্রুত বাড়ে: n = 4-এ এমন সম্পূর্ণ খোঁজ এভাবে আর চলে না, আর এটিই পরের দুই অংশের বিষয়।
২ · প্রতিটি function-এর circuit আছে — DNF থেকে Lupanov
Turing machine-এর জগতে বেশিরভাগ language undecidable (পর্ব ৫১)। Circuit-এর জগতে ছবিটি উল্টো: একটি নির্দিষ্ট n-এর জন্য প্রতিটি function-এরই circuit আছে। প্রশ্ন শুধু আকার নিয়ে।
প্রতিটি f: {0, 1}n → {0, 1}-এর জন্য size O(n · 2n)-এর একটি circuit আছে।
প্রমাণ।
- f(a) = 1 এমন প্রতিটি a ∈ {0, 1}n-এর জন্য একটি minterm ma = ℓ1 ∧ ⋯ ∧ ℓn নিন, যেখানে ai = 1 হলে ℓi = xi, নইলে ℓi = ¬xi. তাহলে ma(x) = 1 ⇔ x = a. — প্রতিটি literal একটি bit মেলায়
- f = ⋁a : f(a) = 1 ma, কারণ বাঁ আর ডান দিক ঠিক একই input-এ 1. এটি f-এর DNF (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৬৯-এ এর বীজগণিত)। — OR মানে “কোনো একটি minterm মেলে”
- Gate গোনা: n-টি ¬-gate একবারই বানিয়ে সব জায়গায় ব্যবহার (fan-out); প্রতিটি minterm-এ n − 1টি ∧; minterm বড়জোর 2nটি, তাদের জুড়তে 2n − 1টি ∨. মোট ≤ n + 2n(n − 1) + 2n = O(n 2n). ∎
এটি সবচেয়ে সরল নির্মাণ, সেরা নয়। O. B. Lupanov ১৯৫৮ সালে দেখান বলে পরিচিত যে প্রতিটি n-input function-এর জন্য (1 + o(1)) · 2n/n gate-ই যথেষ্ট; ধারণাটি হলো input-গুলো দুই ভাগে ভাগ করে ছোট ভাগের সব সম্ভাব্য উপ-function আগে একবার হিসাব করে রাখা, তারপর টেবিল দেখার মতো জোড়া লাগানো। আমরা এর প্রমাণ দেব না (Arora–Barak বা Jukna-র circuit complexity বইয়ে দেখুন)। পরের অংশ দেখাবে, 2n/n-কে একটি ধ্রুবক গুণের বেশি কমানো যায় না, অন্তত বেশিরভাগ function-এর জন্য।
৩ · Shannon-এর গণনা — প্রায় সব function-এর বিশাল circuit লাগে
যুক্তিটি পর্ব ৫৬-এর incompressible string-এর মতো, pigeonhole-এর ওপর দাঁড়ানো: “বস্তু” অনেক, “ছোট বর্ণনা” কম। এখানে বস্তু হলো n bit-এর function, আর ছোট বর্ণনা হলো ছোট circuit.
একটি জেলায় ৬৫ হাজার পরিবার, কিন্তু ছাপাখানায় মাত্র ১২ হাজার আলাদা “দুই অক্ষরের” কোড ছাপা যায়। তাহলে কোনো কোনো পরিবারকে, আসলে বেশিরভাগকেই, লম্বা কোড পেতে হবে। কোন পরিবার, তা গণনা বলে না; শুধু বলে, সবাই ছোট কোড পেতে পারে না।
n-input-এর ঠিক s gate-এর circuit (gate-গুলো g1, …, gs ক্রমে, output = gs) বড়জোর (3(n + s)2)sটি।
প্রমাণ। যেকোনো চক্রহীন circuit-এর gate-গুলোকে topological ক্রমে সাজানো যায়, আর অপ্রয়োজনীয় gate বাদ দিলে output শেষে রাখা যায়। প্রতিটি gate বেছে নেয় তার ধরন (৩টি উপায়: ∧, ∨, ¬) আর দুটি input-তার, যার প্রতিটি n-টি input বা s-টি gate-এর একটি (বড়জোর (n + s)2 উপায়; ¬-এর জন্য দ্বিতীয়টি উপেক্ষিত, এতে শুধু বেশি গোনা হয়)। s-টি gate-এর পছন্দ স্বাধীনভাবে গুণ করলে (3(n + s)2)s. ∎
যথেষ্ট বড় n-এর জন্য, n-input-এর এমন Boolean function আছে, যার প্রতিটি circuit-এর size 2n/(10n)-এর বেশি। আরও শক্ত করে: সব function-এর মধ্যে এমন function-এর অনুপাত, যাদের size ≤ 2n/(10n)-এর circuit আছে, n বাড়লে 0-র দিকে যায়।
প্রমাণ। ধরুন s = 2n/(10n), আর n এত বড় যে s ≥ n (n ≥ 10-এ সত্য)।
- n-input-এর function মোট 22nটি, কারণ truth table-এর 2nটি সারির প্রতিটিতে 0 বা 1. — সরাসরি গণনা
- size ≤ s-এর circuit বড়জোর (s + 1) · (3(n + s)2)s ≤ (s + 1)(12 s2)sটি, কারণ n ≤ s হলে n + s ≤ 2s. প্রতিটি circuit একটিই function হিসাব করে। — লেমা ৩.১, আর size 0 থেকে s যোগ
- log2 নিলে: log2(s + 1) + s(log2 12 + 2 log2 s) ≤ s(5 + 2n), কারণ log2 s ≤ n আর log2(s + 1) ≤ s. — s ≤ 2n
- s(5 + 2n) = 2n(5 + 2n)/(10n) = 2n(0.2 + 0.5/n) ≤ 0.25 · 2n যখন n ≥ 10. — সরল বীজগণিত
- অতএব ছোট circuit দিয়ে হিসাবযোগ্য function বড়জোর 20.25 · 2nটি, যা মোটের 2−0.75 · 2n অংশ, n বাড়লে অতি দ্রুত 0. বাকি সব function-এর size 2n/(10n)-এর বেশি। ∎
ধ্রুবক ১০ বিশেষ কিছু নয়; সূক্ষ্ম হিসাবে প্রায় 2n/n-এর অর্ধেক পর্যন্ত যাওয়া যায়, আর Lupanov-এর upper bound-এর সঙ্গে মিলিয়ে বলা হয়: সবচেয়ে কঠিন n-input function-এর circuit complexity Θ(2n/n). Claude Shannon এই ধরনের গণনা ১৯৪৯ সালে relay (switching) circuit-এর জন্য দেন বলে পরিচিত, “The synthesis of two-terminal switching circuits” প্রবন্ধে। নিচের stepper n = 4-এ সংখ্যাগুলো হাতে গোনে।
1#functions = 2^(2^n)2#circuits(s) ≤ (3(n+s)²)^s3মোট < #functions ?4 → কোনো f-এর লাগে > s5বড় n: s* ≈ 2^n/(2n)
| এই ধাপে | |
| এ পর্যন্ত circuit | |
| সিদ্ধান্ত |
- Function গোনা. n = 4-এ truth table-এর 24 = 16টি সারি, প্রতিটিতে 0 বা 1: মোট 216 = 65,536টি function.
- ০ gate. Output সরাসরি একটি input: x1, x2, x3 বা x4. মাত্র ৪টি function.
- ১ gate. লেমা ৩.১: বড়জোর 3 · (4 + 1)2 = 75টি circuit. মোট এ পর্যন্ত ৭৯.
- ২ gate. বড়জোর (3 · 62)2 = 1082 = 11,664টি; মোট 11,743. এটি 65,536-এর কম, তাই অন্তত 65,536 − 11,743 = 53,793টি function-এর, অর্থাৎ ৮২%-এর বেশির, অন্তত ৩টি gate লাগে।
- ৩ gate. সীমা 1473 = 3,176,523, মোট 3,188,266, যা 65,536-এর অনেক বেশি। এই সীমা খুব ঢিলা (অনেক circuit একই function দেয়), তাই n = 4-এ গণনা এর বেশি কিছু প্রমাণ করে না। ছোট n-এ গণনা দুর্বল।
- বড় n. n = 16-এ একই হিসাব (পরের ব্লক) বলে: কোনো function-এর অন্তত 2,688টি gate লাগে, যা 2n/n ≈ 4,096-এর ০.৬৬ গুণ। n বাড়লে অনুপাত ০.৫-এর দিকে যায়: lower bound প্রায় 2n/(2n).
# Shannon-style counting: functions on n bits vs circuits with s gates.
# A gate picks a type (AND, OR, NOT) and two earlier wires out of n + s:
# at most (3 (n+s)^2)^s circuits with exactly s gates.
from math import log2
def circuits(n, s):
return (3 * (n + s) ** 2) ** s
n = 4 # exact numbers for n = 4
total = n # size 0: the output is an input
for s in range(1, 4):
total += circuits(n, s)
print(f"n=4, s<={s}: at most {total:>9,} circuits vs {2 ** 2 ** n:,} functions")
def log2_count(n, s): # log2 of an upper bound for size <= s
return log2(s + 1) + s * log2(3 * (n + s) ** 2)
print(" n log2(#functions) s* (some f needs >= s*) 2^n/n s*/(2^n/n)")
for n in (8, 16, 32, 64):
lo, hi = 1, 2 ** n # binary search for the first s
while lo < hi: # whose count reaches 2^(2^n)
mid = (lo + hi) // 2
lo, hi = (mid + 1, hi) if log2_count(n, mid) < 2 ** n else (lo, mid)
s = lo
print(f"{n:4} {2 ** n:17.3g} {s:21.4g} {2 ** n / n:10.3g} {s / (2 ** n / n):8.3f}")
for n in (16, 32): # what fraction is computable cheaply?
s = 2 ** n // (10 * n)
print(f"n={n}: size <= 2^n/(10n) = {s:,} covers at most "
f"2^({log2_count(n, s) - 2 ** n:.4g}) of all functions")আসল আউটপুট (ব্রাউজারের Python):
n=4, s<=1: at most 79 circuits vs 65,536 functions
n=4, s<=2: at most 11,743 circuits vs 65,536 functions
n=4, s<=3: at most 3,188,266 circuits vs 65,536 functions
n log2(#functions) s* (some f needs >= s*) 2^n/n s*/(2^n/n)
8 256 23 32 0.719
16 6.55e+04 2688 4.1e+03 0.656
32 4.29e+09 7.943e+07 1.34e+08 0.592
64 1.84e+19 1.592e+17 2.88e+17 0.552
n=16: size <= 2^n/(10n) = 409 covers at most 2^(-5.774e+04) of all functions
n=32: size <= 2^n/(10n) = 13,421,772 covers at most 2^(-3.638e+09) of all functions
প্রথম তিন লাইন stepper-এর সংখ্যা: ২ gate পর্যন্ত বড়জোর ১১,৭৪৩টি circuit, ৬৫,৫৩৬টি function-এর অনেক কম। সারণিতে s* হলো প্রথম s, যেখানে circuit-এর সীমা function-এর সংখ্যা ছোঁয়; তার আগে circuit কম পড়ে, তাই কোনো function-এর অন্তত s*টি gate লাগে। n = 64-এ এই সংখ্যা প্রায় 1.6 × 1017, আর শেষ কলাম ০.৭২ থেকে ০.৫৫-এ নামছে, ০.৫-এর দিকে। শেষ দুই লাইন উপপাদ্য ৩.২-এর “প্রায় সব” অংশ: n = 16-এ 409টি gate দিয়ে বড়জোর 2−57,740 (প্রায়) অংশ function হিসাব করা যায়। সংখ্যাটি এত ছোট যে এলোমেলোভাবে একটি function বাছলে তার ছোট circuit থাকার সম্ভাবনা কার্যত শূন্য।
গণনা কোনো নির্দিষ্ট কঠিন function দেখায় না। যুক্তিটি non-constructive: “কঠিন function আছে” বলে, কিন্তু কোনটি, তা বলে না। আমরা জানতে চাই SAT-এর মতো একটি নির্দিষ্ট, NP-এর function কঠিন কি না। সেখানে আমাদের জ্ঞান প্রায় শূন্য (অংশ ৭)। “প্রায় সব function কঠিন, অথচ একটিও দেখাতে পারি না” — এই অবস্থাকে প্রায়ই খড়ের গাদায় খড় খোঁজার সঙ্গে তুলনা করা হয়।
৪ · Circuit family, P/poly আর advice
একটি circuit একটি নির্দিষ্ট n-এর জন্য। একটি language L ⊆ {0, 1}∗ সব দৈর্ঘ্যের string নিয়ে, তাই তার জন্য প্রতিটি n-এ একটি করে circuit লাগে।
একটি circuit family হলো একটি অনুক্রম (C0, C1, C2, …), যেখানে Cn-এর n-টি input. Family-টি L-কে decide করে, যদি প্রতিটি w-এর জন্য w ∈ L ⇔ C|w|(w) = 1. Family-র size-complexity s(n) = size(Cn). SIZE(s(n)) = যেসব language-এর জন্য size O(s(n))-এর family আছে, আর
P/poly = ⋃k SIZE(nk)
সংজ্ঞায় একটি কথা নেই: Cn-গুলো কীভাবে পাওয়া যাবে। প্রতিটি n-এর circuit সম্পূর্ণ আলাদা হতে পারে, কোনো algorithm সেগুলো লিখতে না পারলেও। এর একটি চমকপ্রদ ফল আছে।
P/poly-তে একটি undecidable language আছে।
প্রমাণ।
- Turing machine-গুলোকে তাদের encoding-এর shortlex ক্রমে M1, M2, …-এ সাজান, আর U = {1n : Mn ফাঁকা input-এ থামে}. ⟨M⟩ থেকে তার ক্রমিক n হিসাব করা যায়, তাই “M ফাঁকা input-এ থামে কি?” প্রশ্নটি U-তে mapping reduce হয়; প্রশ্নটি undecidable (পর্ব ৫২-এর ধাঁচে HALTTM থেকে), তাই U undecidable. — direction: জানা কঠিন সমস্যা ≤m U
- প্রতিটি n-এ U-তে দৈর্ঘ্য n-এর বড়জোর একটি string, 1n. যদি 1n ∈ U, Cn = x1 ∧ ⋯ ∧ xn (n − 1টি gate); নইলে Cn = x1 ∧ ¬x1 (ধ্রুবক 0, ২টি gate). — প্রতিটি n-এর জন্য “সঠিক” circuit আছে
- size(Cn) ≤ n + 1, তাই U ∈ SIZE(n) ⊆ P/poly. কোন n-এ কোন circuit, তা কেউ হিসাব করতে পারে না, কিন্তু সংজ্ঞা শুধু অস্তিত্ব চায়। ∎
এই “অ-অভিন্নতা” (non-uniformity) সারানোর উপায় হলো চাওয়া যে circuit-গুলো নিজেই সহজে বানানো যাবে। একটি family uniform (এখানে P-uniform), যদি একটি polynomial-সময়ের Turing machine 1n পেয়ে ⟨Cn⟩ লিখে দেয়। পরের অংশের প্রমাণ থেকেই বেরোবে: P-uniform polynomial-size family ঠিক P-এর language-গুলো decide করে। P/poly তাই P-এর একটি “অ-অভিন্ন” সম্প্রসারণ।
৪.১ Advice — circuit ছাড়া একই শ্রেণি
Karp আর Lipton ১৯৮০ সালে P/poly-কে আরেকভাবে দেখান: polynomial সময়ের যন্ত্র, যাকে প্রতিটি input দৈর্ঘ্যের জন্য একটি “পরামর্শ” দেওয়া হয়।
L ∈ P/poly ⇔ একটি polynomial-সময়ের Turing machine M, একটি polynomial p আর string-এর একটি অনুক্রম a0, a1, … আছে, |an| ≤ p(n), যাতে প্রতিটি w-এর জন্য w ∈ L ⇔ M(w, a|w|) accept করে।
প্রমাণের রূপরেখা। (⇒) advice an = ⟨Cn⟩, polynomial দৈর্ঘ্যের; M হলো circuit-evaluator, যা gate-গুলো topological ক্রমে হিসাব করে, polynomial সময়ে (এই circuit value problem P-এর মধ্যে, আর পর্ব ৬৬-এ দেখেছেন এটি P-complete). (⇐) পরের অংশের উপপাদ্য ৫.১ M-এর জন্য দৈর্ঘ্য n + |an|-এর input-এ polynomial size-এর circuit দেয়; advice-এর input-তারগুলোতে an-এর bit ধ্রুবক হিসেবে বসালে Cn পাওয়া যায়। ∎
বাজারঘরের উপমা: প্রতিটি দৈর্ঘ্যের অর্ডার-কোডের জন্য হেড অফিস একটি ছোট “চিট শিট” পাঠায়, আর দোকানের কর্মী একটি দ্রুত নিয়ম আর সেই শিট মিলিয়ে সিদ্ধান্ত নেন। শিটটি কীভাবে বানানো হয়েছে, কর্মীর জানার দরকার নেই, আর শিটটি input-এর ওপর নয়, শুধু input-এর দৈর্ঘ্যের ওপর নির্ভর করে।
৫ · P ⊆ P/poly — tableau থেকে circuit
পর্ব ৬০-এ Cook–Levin প্রমাণের কেন্দ্রে ছিল tableau: একটি গণনার configuration-গুলো সারির পর সারি, যেখানে প্রতিটি ঘর ঠিক হয় ওপরের সারির কাছের তিনটি ঘর দেখে। সেখানে এই স্থানীয়তা একটি CNF সূত্র দিয়েছিল; এখানে দেবে একটি circuit.
t(n) ≥ n হলে TIME(t(n)) ⊆ SIZE(t(n)2). বিশেষত P ⊆ P/poly.
ঘরের জন্য এখানে Sipser-এর রীতি: একটি ঘরে হয় একটি tape-চিহ্ন γ ∈ Γ, নয়তো একটি জোড়া (q, γ), যার মানে “head এই ঘরে, state q”. উদাহরণ যন্ত্র M বিজোড় সংখ্যক 1 আছে এমন binary string চেনে: state q0 (এ পর্যন্ত জোড়), q1 (বিজোড়), সবসময় ডানে সরে, ␣ পেলে q1-এ accept, q0-এ reject. Input 100, সময় t = 4, তাই ৫টি সারি আর ৫টি ঘর।
1সারি ১ ← input-তার2ঘর(i+1, j) = g(ওপরের ৩ ঘর)3output = শেষ সারিতে q_acc?4size = (t+1)² · |g|
| সারি | |
| circuit-এ |
- সারি ১. শুরুর configuration q0100. প্রথম ঘর (q0, x1), পরের ঘর x2, x3, বাকি ␣. Circuit-এ এগুলো input-তার আর ধ্রুবক; প্রতিটি ঘর b = ⌈log2|C|⌉ bit-এ লেখা, যেখানে C = Γ ∪ (Q × Γ). এখানে |C| = 3 + 4 · 3 = 15, তাই ৪ bit.
- সারি ২. M (q0, 1) পড়ে 1 লেখে, q1-এ যায়, ডানে সরে। ঘর ১ হয় 1, ঘর ২ হয় (q1, 0). প্রতিটি নতুন ঘর একটি স্থির function g-এর ফল: g(ওপরের বাঁ, ওপরের, ওপরের ডান), যা শুধু δ-এর ওপর নির্ভর করে, n-এর ওপর নয়।
- সারি ৩. একই g আবার: (q1, 0) থেকে 0 থেকে যায়, head ডানে, state q1. Circuit-এ সারি ৩-এর প্রতিটি ঘর সারি ২-এর তিনটি ঘর থেকে g-বাক্স দিয়ে আসে, ঠিক একই নকশায়।
- সারি ৪. Head ␣-এ পৌঁছায়, state q1 (এ পর্যন্ত একটি 1, বিজোড়)। g-বাক্স ১২ bit (৩টি ঘর) নিয়ে ৪ bit দেয়; অংশ ২ অনুযায়ী এমন যেকোনো function-এর একটি ধ্রুবক size-এর circuit আছে।
- সারি ৫ আর output. δ(q1, ␣) = (qaccept, ␣, R): শেষ সারিতে (qacc, ␣). Output gate = শেষ সারির ঘরগুলোর “এটি কি qaccept-এর জোড়া?” পরীক্ষার OR. থামা configuration পরের সারিতে হুবহু কপি হয়, তাই আগে থামলেও শেষ সারিতে ধরা পড়ে।
- Size. (t + 1)2 = 25টি ঘর, যার ২০টিতে একটি করে g-বাক্স। সাধারণভাবে size ≤ cM · (t(n) + 1)2 = O(t(n)2), আর t(n) = nk হলে O(n2k), polynomial. Scratch-এ দৈর্ঘ্য ৬ পর্যন্ত সব input-এ যাচাই: স্থানীয় নিয়ম প্রতিটি ঘর মেলায়, আর accept ⇔ বিজোড় সংখ্যক 1.
প্রমাণ (উপপাদ্য ৫.১)। ধরুন এক-tape decider M, L-কে t(n) সময়ে decide করে।
- দৈর্ঘ্য n-এর input-এ M বড়জোর t(n) ধাপ চলে আর বড়জোর t(n) + 1টি ঘর ছোঁয়। তাই (t(n) + 1) × (t(n) + 1) আকারের tableau যথেষ্ট; থামার পর configuration কপি হয়। — সময় থেকে জায়গা (পর্ব ৬৪)
- সারি i + 1-এর ঘর j নির্ভর করে শুধু সারি i-এর ঘর j − 1, j, j + 1-এর ওপর, কারণ head এক ধাপে এক ঘর সরে। সীমার ঘরে অনুপস্থিত প্রতিবেশীকে একটি স্থির চিহ্ন ধরা হয় (বাঁ প্রান্তে বাঁয়ে সরলে head থেকে যায়, পর্ব ৪৩-এর রীতি)। তাই একটি স্থির function g: C3 → C আছে। — স্থানীয়তা
- g-এর প্রতিটি output-bit একটি 3b-bit function; অংশ ২ অনুযায়ী তার circuit আছে, যার size একটি ধ্রুবক cM-এর বেশি নয় (M স্থির, n নয়)। — উপপাদ্য ২.১
- Circuit Cn: সারি ১-এর ঘর input-তার আর ধ্রুবক থেকে, প্রতিটি পরের ঘর একটি g-বাক্স, আর output শেষ সারির accept-পরীক্ষার OR. আরোহে সারি i = M-এর (i − 1) ধাপ পরের configuration, তাই Cn(w) = 1 ⇔ M w accept করে। — সারি ধরে আরোহ
- size(Cn) ≤ cM(t(n) + 1)2 + O(t(n)) = O(t(n)2). ∎
নির্মাণটি এত নিয়মিত যে একটি polynomial-সময়ের যন্ত্র 1n থেকে Cn লিখে দিতে পারে, তাই family-টি P-uniform; উল্টো দিকে P-uniform family-কে “বানাও, তারপর চালাও” দিয়ে polynomial সময়ে অনুকরণ করা যায়। এভাবেই অংশ ৪-এর দাবি: P-uniform polynomial-size = P.
৫.১ CIRCUIT-SAT NP-complete
একই নির্মাণ NP-এর জন্য একটি নতুন NP-complete সমস্যা দেয়, যা অনেক reduction-এর সুবিধাজনক শুরুর বিন্দু।
CIRCUIT-SAT = {⟨C⟩ : C একটি Boolean circuit (0, 1 ধ্রুবক-তারসহ), আর কোনো input x-এ C(x) = 1} NP-complete.
প্রমাণ।
- CIRCUIT-SAT ∈ NP: certificate হলো x; gate-গুলো topological ক্রমে হিসাব করা polynomial সময়ের কাজ। — verifier (পর্ব ৫৮)
- ধরুন L ∈ NP, যার verifier V(w, c) polynomial সময়ে চলে আর |c| = p(|w|). V-এর জন্য উপপাদ্য ৫.১-এর circuit বানান, input দৈর্ঘ্য n + p(n). — tableau থেকে circuit
- f(w) = সেই circuit, যেখানে প্রথম n-টি input-তারে w-এর bit ধ্রুবক হিসেবে বসানো; বাকি p(n)টি তার খোলা, নাম Cw(c). তাহলে w ∈ L ⇔ ∃c: V(w, c) accept ⇔ Cw satisfiable. — ⇔ দুই দিকই
- f polynomial সময়ে হিসাবযোগ্য, কারণ circuit-টি নিয়মিত আর polynomial আকারের। তাই L ≤p CIRCUIT-SAT, আর CIRCUIT-SAT NP-hard. ∎
এখান থেকে SAT-এ যাওয়া সহজ: প্রতিটি gate-এর জন্য একটি নতুন চলক, আর gate-এর নিয়মকে কয়েকটি clause-এ লেখা। g = a ∧ b হয় (¬g ∨ a) ∧ (¬g ∨ b) ∧ (g ∨ ¬a ∨ ¬b); g = a ∨ b হয় (g ∨ ¬a) ∧ (g ∨ ¬b) ∧ (¬g ∨ a ∨ b); g = ¬a হয় (¬g ∨ ¬a) ∧ (g ∨ a); শেষে output-চলকটি একা একটি clause. এটিই Tseitin রূপান্তর: CNF-এর আকার circuit-এর রৈখিক, আর প্রতিটি clause-এ বড়জোর তিনটি literal, তাই CIRCUIT-SAT ≤p 3SAT. Cook–Levin-এর একটি বিকল্প পথ তাই: NP → CIRCUIT-SAT → 3SAT. নিচের ব্লক দুটি circuit-এ এটি brute force-এ যাচাই করে।
# CIRCUIT-SAT by brute force, and the gate-by-gate CNF (Tseitin) check.
from itertools import product
def run(n, gates, x):
w = list(x)
for op, a, b in gates:
w.append(1 - w[a] if op == "NOT" else w[a] & w[b] if op == "AND" else w[a] | w[b])
return w
def tseitin(n, gates): # variable v+1 = wire v; one new variable per gate
cnf = []
for i, (op, a, b) in enumerate(gates):
g, a, b = n + i + 1, a + 1, b + 1
if op == "NOT": cnf += [[-g, -a], [g, a]]
elif op == "AND": cnf += [[-g, a], [-g, b], [g, -a, -b]]
else: cnf += [[g, -a], [g, -b], [-g, a, b]]
return cnf + [[n + len(gates)]] # the output gate must be 1
def sat_count(cnf, nvars):
return sum(all(any((v[abs(l) - 1] == 1) == (l > 0) for l in c) for c in cnf)
for v in product((0, 1), repeat=nvars))
C1 = [("NOT", 0, 0), ("AND", 0, 1), ("AND", 2, 3), ("OR", 4, 5)] # free delivery
C2 = [("OR", 0, 1), ("NOT", 0, 0), ("NOT", 1, 0), ("AND", 2, 3), ("AND", 5, 4)]
for name, n, C in (("C1", 3, C1), ("C2", 2, C2)):
good = [x for x in product((0, 1), repeat=n) if run(n, C, x)[-1] == 1]
cnf = tseitin(n, C)
print(f"{name}: {len(C)} gates | satisfying inputs: {good}")
print(f" CNF: {n + len(C)} variables, {len(cnf)} clauses, "
f"satisfying assignments = {sat_count(cnf, n + len(C))}")
print("C1 clauses:", tseitin(3, C1))আসল আউটপুট (ব্রাউজারের Python):
C1: 4 gates | satisfying inputs: [(0, 0, 1), (0, 1, 1), (1, 1, 0), (1, 1, 1)]
CNF: 7 variables, 12 clauses, satisfying assignments = 4
C2: 5 gates | satisfying inputs: []
CNF: 7 variables, 14 clauses, satisfying assignments = 0
C1 clauses: [[-4, -1], [4, 1], [-5, 1], [-5, 2], [5, -1, -2], [-6, 3], [-6, 4], [6, -3, -4], [7, -5], [7, -6], [-7, 5, 6], [7]]
C1 হলো অংশ ১-এর ফ্রি-ডেলিভারি circuit: ৮টি input-এর ৪টিতে output 1, তাই C1 ∈ CIRCUIT-SAT. তার CNF-এ ৩টি input-চলক আর ৪টি gate-চলক, ২ + ৩ + ৩ + ৩ + ১ = ১২টি clause, আর satisfying assignment ঠিক ৪টি: প্রতিটি satisfying input-এর জন্য একটি, কারণ input ঠিক করলে gate-চলকগুলোর মান বাধ্যতামূলক। C2 = (x1 ∨ x2) ∧ ¬x1 ∧ ¬x2 কখনো 1 হয় না, আর তার ১৪টি clause-এর CNF-ও unsatisfiable. শেষ লাইনে C1-এর clause, DIMACS-এর মতো সংখ্যায়: 4 মানে g1, −1 মানে ¬x1; যেমন [-4, -1] আর [4, 1] মিলে বলে g1 = ¬x1. Satisfying assignment-এর সংখ্যা মেলা “equisatisfiable”-এর চেয়েও শক্ত দাবি, কিন্তু এখানে তা-ই ঘটেছে।
৬ · গভীরতা — NC, AC0 আর PARITY
Size মোট কাজ মাপে; depth মাপে সমান্তরাল সময়। যথেষ্ট প্রসেসর থাকলে একই স্তরের সব gate একসঙ্গে চলে, তাই depth-ই সময়। Computer Architecture কোর্সের পর্ব ১১-এর adder একটি পরিচিত উদাহরণ: ripple-carry adder-এ carry একটির পর একটি যায়, depth n-এর সমানুপাতিক; carry-lookahead adder একই যোগ O(log n) depth-এ করে, বেশি gate খরচ করে।
- NCi = যেসব language-এর polynomial size আর O(logi n) depth-এর fan-in 2 circuit family আছে (সাধারণত uniform ধরে); NC = ⋃i NCi.
- ACi = একই, কিন্তু ∧ আর ∨ gate-এর fan-in সীমাহীন। AC0 মানে স্থির depth (n-এর ওপর নির্ভর করে না) আর polynomial size.
সীমাহীন fan-in-এর একটি gate-কে fan-in 2-এর gate-এর O(log n) depth-এর গাছে ভাঙা যায়, তাই ACi ⊆ NCi+1 ⊆ ACi+1. জানা অন্তর্ভুক্তি (কয়েকটির প্রমাণ এই পর্বের বাইরে):
AC0 ⊊ NC1 ⊆ L ⊆ NL ⊆ AC1 ⊆ NC2 ⊆ ⋯ ⊆ NC ⊆ P
প্রথম ⊊ নিচে আসছে। NC1 ⊆ L-এর প্রমাণ Borodin-এর (১৯৭৭ বলে পরিচিত): log-depth circuit-কে depth-first ভাবে log জায়গায় হিসাব করা যায়। NC = P কি না, অর্থাৎ প্রতিটি দক্ষ algorithm কি অতি সমান্তরাল করা যায়, খোলা প্রশ্ন; বেশিরভাগ গবেষক মনে করেন না, আর পর্ব ৬৬-এর P-complete সমস্যাগুলো (যেমন circuit value) সবচেয়ে সম্ভাব্য প্রমাণ যে কিছু কাজ “স্বভাবত ক্রমিক”। “NC” নামটি Nick Pippenger-এর নামে, Stephen Cook রেখেছিলেন বলে পরিচিত।
৬.১ PARITY — গাছে সহজ, চ্যাপ্টা circuit-এ কঠিন
PARITY(x1, …, xn) = x1 ⊕ ⋯ ⊕ xn, অর্থাৎ 1 যদি বিজোড় সংখ্যক xi = 1. বাজারঘরের sensor-লাইনের “জোড় সংখ্যক 1” পরীক্ষা (মডিউল ১) এরই উল্টো। দুইভাবে বানানো যাক:
- গাছ: a ⊕ b = (a ∨ b) ∧ ¬(a ∧ b), ৪টি gate, depth ৩. এমন XOR-বাক্সের একটি সুষম গাছ: n − 1টি বাক্স, তাই 4(n − 1) gate, আর depth 3⌈log2 n⌉. অতএব PARITY ∈ NC1.
- চ্যাপ্টা (depth ২): DNF, অর্থাৎ ∧-গুলোর একটি ∨. অংশ ২-এর নির্মাণে বিজোড় input-এর প্রতিটির জন্য একটি minterm: 2n−1টি পদ।
PARITY-র প্রতিটি DNF-এ অন্তত 2n−1টি পদ।
প্রমাণ।
- DNF-এর একটি পদ T (কয়েকটি literal-এর ∧) সত্য হলে পুরো DNF সত্য, তাই T সত্য এমন প্রতিটি input-এ PARITY = 1 হতে হবে। — ∨-এর অর্থ
- ধরুন T-তে কোনো চলক xi নেই, আর a একটি input যেখানে T সত্য। a-র শুধু i-তম bit উল্টে a′ পাই: T(a′) = T(a) = 1, কিন্তু PARITY(a′) ≠ PARITY(a). দুটির একটিতে PARITY = 0, যা ধাপ ১-এর বিরোধী। (T কোথাও সত্য না হলে T বাদ দেওয়া যায়।) — একটি bit উল্টানো
- অতএব প্রতিটি পদে n-টি চলকই আছে, তাই প্রতিটি পদ ঠিক একটি input-এ সত্য। বিজোড় input 2n−1টি, প্রতিটিকে কোনো পদ ঢাকতে হবে, তাই পদ ≥ 2n−1. ∎
# PARITY two ways: a balanced tree of XOR blocks vs a DNF (OR of ANDs).
from itertools import product, combinations
def xor_tree(n): # XOR(a,b) = (a OR b) AND NOT(a AND b): 4 gates
gates, layer, depth = [], list(range(n)), 0
while len(layer) > 1:
nxt = []
for i in range(0, len(layer) - 1, 2):
a, b = layer[i], layer[i + 1]; k = n + len(gates)
gates += [("OR", a, b), ("AND", a, b), ("NOT", k + 1, 0), ("AND", k, k + 2)]
nxt.append(k + 3)
if len(layer) % 2: nxt.append(layer[-1])
layer, depth = nxt, depth + 3 # one XOR block = 3 levels
return gates, depth
def run(n, gates, x):
w = list(x)
for op, a, b in gates:
w.append(1 - w[a] if op == "NOT" else w[a] & w[b] if op == "AND" else w[a] | w[b])
return w[-1]
print(" n tree gates tree depth correct DNF terms 2^(n-1) DNF literals")
for n in (2, 3, 4, 8, 12):
g, d = xor_tree(n) # check on all 2^n inputs
ok = all(run(n, g, x) == sum(x) % 2 for x in product((0, 1), repeat=n))
print(f"{n:2} {len(g):11} {d:11} {str(ok):7} {2 ** (n - 1):18,} {n * 2 ** (n - 1):13,}")
# Why the DNF cannot be smaller: no term with fewer than n literals is safe.
for n in (3, 4, 5):
short_ok = 0
for k in range(1, n): # terms fixing k of the n variables
for vars_ in combinations(range(n), k):
for vals in product((0, 1), repeat=k):
fixed = dict(zip(vars_, vals))
inside = [x for x in product((0, 1), repeat=n) if all(x[v] == b for v, b in fixed.items())]
short_ok += all(sum(x) % 2 == 1 for x in inside)
print(f"n={n}: short terms that imply PARITY = {short_ok}")আসল আউটপুট (ব্রাউজারের Python):
n tree gates tree depth correct DNF terms 2^(n-1) DNF literals
2 4 3 True 2 4
3 8 6 True 4 12
4 12 6 True 8 32
8 28 9 True 128 1,024
12 44 12 True 2,048 24,576
n=3: short terms that imply PARITY = 0
n=4: short terms that imply PARITY = 0
n=5: short terms that imply PARITY = 0
গাছের gate 4(n − 1): n = 12-এ ৪৪টি, আর depth 3⌈log2 n⌉: n = 12-এ ১২. প্রতিটি সারিতে গাছটি সব 2n input-এ PARITY-র সঙ্গে মিলেছে (n = 12-এ ৪,০৯৬টি)। DNF-এ একই n-এ ২,০৪৮টি পদ আর ২৪,৫৭৬টি literal: gate বেশি, কিন্তু depth মাত্র ২ (সীমাহীন fan-in ধরে)। শেষ তিন লাইন উপপাদ্য ৬.২-এর মূল ধাপ ২ brute force-এ যাচাই করে: n = 3, 4, 5-এ n-এর কম literal-এর এমন কোনো পদ নেই, যা সত্য হলে PARITY নিশ্চিত 1.
Depth ২ থেকে বেশি স্থির depth-এ গেলে কী হয়? উত্তরটি circuit complexity-র প্রথম বড় সাফল্য।
যেকোনো স্থির d-এর জন্য, PARITY-র depth-d, সীমাহীন fan-in-এর circuit-এর size n-এর কোনো polynomial দিয়ে সীমিত নয়। আরও শক্ত রূপে (Håstad): size অন্তত 2Ω(n1/(d−1)).
প্রমাণ এই পর্বের বাইরে; মূল ধারণাটি “random restriction”: বেশিরভাগ চলকে এলোমেলো 0/1 বসালে একটি ছোট AC0 circuit প্রায় নিশ্চিতভাবে একটি ধ্রুবক বা খুব সরল function-এ নেমে যায়, অথচ PARITY যেকোনো ধরনের বসানোর পরেও বাকি চলকগুলোর PARITY (বা তার উল্টো) থেকে যায়। ফলটি Furst, Saxe আর Sipser (১৯৮১ সালের সম্মেলন-প্রবন্ধ, ১৯৮৪ সালে journal) আর আলাদাভাবে Ajtai (১৯৮৩) দেন বলে পরিচিত; Yao আর পরে Håstad (১৯৮৬, “switching lemma”) একে exponential-এ নিয়ে যান। ফল: AC0 ⊊ NC1, একটি প্রমাণিত কঠোর পৃথকীকরণ।
৭ · Karp–Lipton আর lower bound-এর সীমান্ত
Circuit-এ আগ্রহের মূল কারণ P বনাম NP. P ⊆ P/poly, তাই
NP ⊄ P/poly ⇒ P ≠ NP
অর্থাৎ SAT-এর জন্য superpolynomial circuit lower bound প্রমাণ করলেই P ≠ NP. এই পথের আকর্ষণ (পর্ব ৬৩): circuit একটি স্থির, সসীম বস্তু, Turing machine-এর অসীম আচরণ বা oracle-এর জটিলতা নেই; আর অংশ ৩ বলে কঠিন function-এ জগৎ ভরা। কিন্তু উল্টো দিক সাবধানে পড়ুন: NP ⊆ P/poly হলেও P = NP প্রমাণ হতো না, কারণ P/poly-র circuit বানানোর algorithm না-ও থাকতে পারে। তবু সেটি একটি বড় “ধস” ঘটাত।
NP ⊆ P/poly হলে polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ে: PH = Σ2p.
প্রমাণের রূপরেখা। পর্ব ৬৮ অনুযায়ী Π2p ⊆ Σ2p দেখানোই যথেষ্ট। Π2-এর একটি প্রশ্ন: “∀y ∃z: φ(x, y, z)”. SAT-এর ছোট circuit থাকলে একটি Σ2-যন্ত্র প্রথমে ∃ দিয়ে একটি circuit C অনুমান করে, যা দাবি করে “φ(x, y, ·) satisfiable কি না বলি”. তারপর ∀y-তে যাচাই করে, আর SAT-এর self-reducibility (পর্ব ৬২) দিয়ে C-এর উত্তর থেকে একটি z বানিয়ে φ(x, y, z) নিজে পরীক্ষা করে। এতে ∀∃ হয়ে যায় ∃∀: Π2 ⊆ Σ2. পর্ব ৬৮-এ উল্লেখ আছে, Σ2-এ ধসের এই রূপটি মূল প্রবন্ধে Sipser-এর অবদান বলে লেখা। ∎
যেহেতু বেশিরভাগ গবেষক মনে করেন PH ধসে পড়ে না, তাঁরা এটিও মনে করেন যে SAT-এর polynomial size-এর circuit নেই। আরেকটি সম্পর্কিত ফল randomness থেকে: Adleman ১৯৭৮ সালে দেখান যে randomized শ্রেণি RP ⊆ P/poly, আর Bennett ও Gill (১৯৮১) amplification দিয়ে একই যুক্তি BPP-তে খাটান (পর্ব ৬৯)। ধারণা: ভুলের সম্ভাবনা 2−2n-এর নিচে নামালে দৈর্ঘ্য n-এর সব 2n input-এ একসঙ্গে ঠিক উত্তর দেয় এমন একটি random string আছে; সেটিই advice. অর্থাৎ advice দিয়ে randomness সরানো যায়, যদিও কোন string, তা জানা নেই।
৭.১ আমরা আসলে কতটুকু জানি
| Model | জানা সেরা ফল (পরিচিত সূত্র অনুযায়ী) | অবস্থা |
|---|---|---|
| সাধারণ circuit, NP-এর explicit function | প্রায় 3n থেকে 3.1n gate (Blum ১৯৮৪-এর 3n; পরে Find, Golovnev, Hirsch, Kulikov ২০১৬; Li ও Yang ২০২২ প্রায় 3.1n) | Superpolynomial: খোলা |
| Boolean formula (fan-out 1) | প্রায় n3 (Håstad ১৯৯৮, পরে Tal-এর উন্নতি) | Superpolynomial: খোলা |
| Monotone circuit (শুধু ∧, ∨) | CLIQUE-এর জন্য superpolynomial (Razborov ১৯৮৫), পরে exponential (Alon–Boppana) | প্রমাণিত |
| AC0 | PARITY-র জন্য exponential (Håstad ১৯৮৬) | প্রমাণিত |
| ACC0 (AC0 + mod-m gate) | NEXP ⊄ ACC0 (Ryan Williams ২০১১) | প্রমাণিত, কিন্তু NP-এর জন্য খোলা |
অর্থাৎ যেখানে circuit-কে কোনোভাবে দুর্বল করা হয়েছে (depth স্থির, বা ¬ নেই), সেখানে শক্ত lower bound আছে; সাধারণ circuit-এ আমরা SAT-এর জন্য 3.1n-এর মতো একটি রৈখিক সীমার বেশি কিছু প্রমাণ করতে পারি না, অথচ অংশ ৩ বলে প্রায় সব function-এর লাগে 2n/n-এর ক্রমে। Kannan ১৯৮২ সালে দেখান বলে পরিচিত যে প্রতিটি স্থির k-এর জন্য Σ2p ⊄ SIZE(nk); কিন্তু “একটি k-এর জন্য” আর “সব polynomial-এর জন্য” একসঙ্গে বলা আলাদা ব্যাপার।
কেন এত কঠিন? পর্ব ৬৩-এর natural proofs বাধা: Razborov আর Rudich দেখান, PARITY ∉ AC0-এর মতো প্রায় সব জানা প্রমাণ একটি “সহজে পরীক্ষাযোগ্য আর বেশিরভাগ function-এর আছে” এমন ধর্ম ব্যবহার করে। শক্ত pseudorandom function থাকলে এমন ধর্ম দিয়ে P/poly-র বিরুদ্ধে lower bound পাওয়া যায় না। মজার ব্যাপার, ঠিক Shannon-এর গণনার মতো “বেশিরভাগ function কঠিন” অনুভূতিই এখানে বাধা হয়ে দাঁড়ায়।
৭.২ Hardware আর neural network
বাস্তবের combinational circuit এই model-এরই প্রতিচ্ছবি: chip-নকশার সফটওয়্যার (logic synthesis) একটি function-এর ছোট আর অগভীর circuit খোঁজে, আর অংশ ১-এর brute force দেখায় কেন সঠিক সর্বনিম্ন খোঁজা দ্রুত অসম্ভব হয়ে যায়। একটি truth table দেখে তার সবচেয়ে ছোট circuit-এর size একটি সীমার নিচে কি না (MCSP নামে পরিচিত সমস্যা) NP-তে আছে, কিন্তু NP-complete কি না, আজও জানা নেই বলে পরিচিত।
একটি feed-forward neural network, স্থির input দৈর্ঘ্য আর স্থির ওজনে, একটি circuit-ই, শুধু gate হলো threshold gate (“ওজনসহ যোগফল একটি সীমা পেরোলে 1”). স্থির depth আর polynomial size-এর threshold circuit-এর শ্রেণির নাম TC0; একটি threshold gate একাই সীমাহীন fan-in-এর PARITY-র কাছাকাছি কাজ (সংখ্যা গোনা) করতে পারে, তাই AC0 ⊆ TC0, আর PARITY ∈ TC0. কিছু গবেষণা দেখায় যে নির্দিষ্ট precision-এর transformer-এর গণনা uniform TC0-এর মতো শ্রেণিতে পড়ে (Merrill আর Sabharwal, ২০২৩ বলে পরিচিত), যা তাদের কী শেখা সম্ভব তার একটি তাত্ত্বিক সীমার ইঙ্গিত দেয়; ফলগুলো model-এর অনুমানের ওপর নির্ভর করে, তাই সাবধানে পড়তে হয়। এই বিষয়ে পর্ব ৭৯ (formal language আর machine learning) বিস্তারিত বলবে। TC0-এর বিরুদ্ধে NP-এর lower bound-ও খোলা।
আরও গভীরে: Razborov আর Smolensky ১৯৮৭ সালের দিকে দেখান যে mod-3 gate যোগ করা AC0-ও PARITY পারে না, polynomial-পদ্ধতিতে। Williams-এর NEXP ⊄ ACC0 প্রমাণ একটি নতুন ধারা খোলে: একটি circuit শ্রেণির জন্য brute force-এর চেয়ে সামান্য দ্রুত SAT algorithm পেলে সেই শ্রেণির lower bound আসে, যা natural proofs বাধা এড়ায় বলে মনে করা হয়। পরে Murray আর Williams (২০১৮) ফলটি nondeterministic quasi-polynomial সময়ে নামিয়েছেন বলে প্রকাশিত। “Hardness vs randomness”-এর সূত্রে (পর্ব ৬৯) circuit lower bound আর derandomization গভীরভাবে যুক্ত।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Circuit-এর size আর depth কী? Size = gate-সংখ্যা (মোট কাজ), depth = দীর্ঘতম input-output পথ (সমান্তরাল সময়)।
- প্রায় সব function-এর বড় circuit লাগে, প্রমাণ করুন। Function 22n, s-gate circuit ≤ (3(n + s)2)s; s = 2n/(10n)-এ দ্বিতীয়টি অনেক কম।
- P ⊆ P/poly কেন? t(n)-সময়ের tableau-র প্রতিটি ঘর ওপরের তিনটি ঘরের স্থির function, তাই O(t(n)2) size-এর circuit.
- P/poly = P? না; P/poly-তে undecidable unary language আছে।
- PARITY কোথায়? NC1-এ (XOR গাছ), AC0-এ নয় (Furst–Saxe–Sipser, Ajtai, Håstad).
৮ · AI-এর যুগে circuit complexity
AI assistant এই বিষয়ে প্রায়ই আত্মবিশ্বাসী কিন্তু ভুল উত্তর দেয়, বিশেষ করে কী প্রমাণিত আর কী খোলা, সেখানে। নিচের ভুলগুলো বারবার দেখা যায়।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “Shannon প্রমাণ করেছেন SAT-এর exponential circuit লাগে” | গণনা non-constructive; কোনো নির্দিষ্ট NP function-এর জন্য superpolynomial lower bound জানা নেই |
| “P/poly = P” বা “P/poly-র সব language decidable” | Unary undecidable language-এর উদাহরণ চান; uniformity-র শর্ত কোথায়, জিজ্ঞাসা করুন |
| Karp–Lipton উল্টো: “PH ধসে পড়লে NP ⊆ P/poly” | বক্তব্য: NP ⊆ P/poly ⇒ PH = Σ2p; উল্টোটি এই উপপাদ্য বলে না |
| Size আর depth গুলিয়ে ফেলা, বা fan-in-এর রীতি না বলা | AC (সীমাহীন fan-in) আর NC (fan-in 2) আলাদা; প্রতিটি দাবিতে model লিখতে বলুন |
| “PARITY NC1-এ নেই” বা “AC0-এ আছে” | XOR গাছ চালিয়ে দেখুন: depth O(log n); AC0-এ নেই, এটি প্রমাণিত |
| Circuit-এর gate গুনতে ভুল, বা একটি ছোট circuit দাবি করে যা ভুল function দেয় | সব 2n input-এ circuit চালিয়ে truth table মেলান |
AI-কে কাজে লাগানোর ভালো উপায়: একটি নির্দিষ্ট function-এর circuit চাওয়া, সঙ্গে এমন script, যা সব input-এ circuit চালিয়ে truth table মেলায় আর size ও depth ছাপে; আর প্রতিটি theorem-এর সঙ্গে “প্রমাণিত নাকি খোলা” আলাদা করে লিখতে বলা।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Shannon-এর গণনা বলে প্রায় সব function-এর জন্য exponential circuit লাগে, অথচ ৭০ বছরেও NP-এর একটিও function-এর জন্য 3.1n-এর বেশি lower bound কেউ প্রমাণ করতে পারেননি। এই বৈপরীত্যের ব্যাখ্যা কী?
গণনার যুক্তি একটি অস্তিত্বের প্রমাণ। এটি কঠিন function-এর সংখ্যা গোনে, কিন্তু কোনো একটিকে নাম দেয় না। একটি এলোমেলোভাবে বাছা function প্রায় নিশ্চিতভাবে কঠিন, কিন্তু এমন function-এর বর্ণনাই প্রায় 2n bit লম্বা, তাই সেটি NP-এর মতো কোনো “দক্ষভাবে বর্ণনাযোগ্য” শ্রেণিতে নেই। আমাদের দরকার এমন একটি function, যা একদিকে সহজে বর্ণনা ও যাচাই করা যায় (NP-তে), অন্যদিকে ছোট circuit-এ হিসাব করা যায় না। এই দুই শর্ত একসঙ্গে মেলানোই কঠিন।
Diagonalization-এর পথও এখানে সরাসরি কাজ করে না। পর্ব ৫১ বা ৬৭-এর diagonal যুক্তিতে একটি যন্ত্র অন্য সব যন্ত্রকে অনুকরণ করে উল্টো উত্তর দেয়। Circuit-এর ক্ষেত্রে প্রতিটি n-এ polynomial size-এর circuit অসংখ্য, আর তাদের সবাইকে অনুকরণ করতে exponential সময় লাগে; তাই এই কৌশল দেয় EXP বা Σ2p-এর মতো বড় শ্রেণির জন্য lower bound (যেমন Kannan-এর ১৯৮২ সালের ফল: প্রতিটি স্থির k-এর জন্য Σ2p ⊄ SIZE(nk)), NP-এর জন্য নয়।
১৯৮০-এর দশকে আশা ছিল ভিন্ন। AC0-এ PARITY আর monotone circuit-এ CLIQUE-এর lower bound দ্রুত এসেছিল, আর অনেকে ভেবেছিলেন সাধারণ circuit-এও শিগগিরই আসবে। Razborov নিজেই পরে দেখান যে তাঁর monotone কৌশল সাধারণ circuit-এ খাটে না। ১৯৯৪ সালে Razborov আর Rudich natural proofs বাধা দেন: জানা কৌশলগুলোর “বেশিরভাগ function-এর আছে এমন সহজ ধর্ম” কাঠামোই শক্ত pseudorandom function থাকলে NP-এর বিরুদ্ধে কাজ করতে পারে না। বিদ্রূপের ব্যাপার, Shannon-এর গণনার “বেশিরভাগ কঠিন” ভাবনাই এখানে বাধা।
সাধারণ circuit-এ জানা সেরা explicit সীমা Blum-এর ১৯৮৪ সালের প্রায় 3n থেকে শুরু করে কয়েক দশকে মাত্র প্রায় 3.1n-এ পৌঁছেছে বলে পরিচিত। এটি দেখায়, একটি নির্দিষ্ট function-এর জন্য প্রতিটি gate-এর lower bound কতটা পরিশ্রমে আসে।
মূল উপলব্ধি: “কঠিন function আছে” আর “এই নির্দিষ্ট, সহজে বর্ণনাযোগ্য function কঠিন” সম্পূর্ণ আলাদা দাবি; প্রথমটি গণনা থেকে সহজে আসে, দ্বিতীয়টির জন্য নতুন ধরনের কৌশল লাগবে, যা natural proofs-এর মতো বাধা এড়াতে পারে।
প্র ০২P/poly-তে undecidable language আছে, তাহলে এটি কি একটি “অবাস্তব” model? তবু complexity তাত্ত্বিকেরা আর cryptographer-রা এই model এত গুরুত্ব দেন কেন?
P/poly সত্যিই অবাস্তব শক্তিশালী: প্রতিটি n-এর জন্য একটি “জাদুকরী” circuit, যা কেউ বানাতে না-ও পারে। Unary halting language U-র উদাহরণ দেখায়, এই শক্তি দিয়ে এমন প্রশ্নের উত্তর দেওয়া যায় যা কোনো algorithm পারে না। তাহলে model-টি “algorithm”-এর মডেল নয়, বরং “প্রতিটি আকারের জন্য সেরা সম্ভাব্য hardware”-এর মডেল।
এই শক্তিই lower bound-এর জন্য সুবিধা। কোনো সমস্যা P/poly-র বাইরে প্রমাণ করলে তা P-এর বাইরে, আর আরও বেশি: কোনো আকারের জন্য কোনো বিশেষ chip, কোনো precomputed টেবিল বা কোনো advice দিয়েও দক্ষভাবে সমাধান হয় না। দুর্বল প্রতিপক্ষের বিরুদ্ধে জেতার চেয়ে শক্ত প্রতিপক্ষের বিরুদ্ধে জেতা বড় দাবি। আর অংশ ৫-এর প্রমাণ দেখায়, Turing machine-এর গণনাকে circuit-এ আনা যায় মাত্র বর্গ খরচে, তাই lower bound-এর লড়াই সম্পূর্ণ সংযুক্তিমূলক (combinatorial) একটি প্রশ্নে নামে, যেখানে অসীম আচরণ বা থামার প্রশ্ন নেই।
Cryptography-তে non-uniformity স্বাভাবিক। একজন আক্রমণকারী একটি নির্দিষ্ট key-দৈর্ঘ্যের, ধরা যাক 128 bit-এর, জন্য বছরের পর বছর গবেষণা করে একটি বিশেষ যন্ত্র বা বিশাল precomputed টেবিল বানাতে পারে। তাই নিরাপত্তার অনেক আনুষ্ঠানিক সংজ্ঞা polynomial size-এর circuit-প্রতিপক্ষ ধরে লেখা হয়, শুধু polynomial-সময়ের algorithm নয়। One-way function বা pseudorandom generator-এর সংজ্ঞাও প্রায়ই এভাবে দেওয়া হয় (পর্ব ৭৬-এ এর বিস্তার)।
Uniformity দিয়ে দুই জগৎ জোড়া যায়। P-uniform polynomial-size circuit ঠিক P; log-space-uniform NC1, NC ইত্যাদি সমান্তরাল গণনার বাস্তবসম্মত মডেল। কোন uniformity শর্ত বাছা হবে, তা প্রশ্নের ওপর নির্ভর করে, আর ছোট শ্রেণিতে (যেমন AC0) uniformity-র সূক্ষ্ম রূপ (DLOGTIME-uniform ইত্যাদি) গুরুত্বপূর্ণ হয়ে ওঠে।
মূল উপলব্ধি: P/poly algorithm-এর মডেল নয়, “আকার-ভিত্তিক সেরা hardware”-এর মডেল; এর অতিরিক্ত শক্তিই একে lower bound আর cryptographic নিরাপত্তার জন্য শক্ত মানদণ্ড বানায়, আর uniformity দিয়ে দরকার হলে বাস্তব algorithm-এর জগতে ফেরা যায়।
প্র ০৩PARITY একটি XOR গাছে log-depth-এ সহজ, অথচ স্থির depth-এ exponential size লাগে। বাস্তব hardware আর সমান্তরাল গণনায় “depth” এত গুরুত্বপূর্ণ কেন, আর এই lower bound কী শেখায়?
Depth হলো সমান্তরাল সময়। একটি chip-এ প্রতিটি gate-এর একটি delay আছে, আর circuit-এর মোট delay তার দীর্ঘতম পথের (critical path) delay. তাই clock কত দ্রুত চলবে, তা মূলত depth ঠিক করে (Computer Architecture কোর্সে এর বিস্তারিত)। Ripple-carry বনাম carry-lookahead adder-এর তুলনা এর আদর্শ উদাহরণ: দ্বিতীয়টি বেশি gate খরচ করে depth O(n) থেকে O(log n)-এ নামায়, আর প্রায় সব আধুনিক প্রসেসর এমন কৌশল ব্যবহার করে।
PARITY-র ফল একটি গভীর সত্য দেখায়: depth আর size-এর মধ্যে আপস অনিবার্য। Depth ২-এ PARITY-র জন্য 2n−1টি পদ লাগে, আমরা পুরো প্রমাণ দেখেছি। Håstad-এর ফল বলে, depth d-তে size অন্তত 2Ω(n1/(d−1)): প্রতিটি অতিরিক্ত স্তর size কমায়, কিন্তু স্থির depth-এ কখনো polynomial-এ নামে না। মাত্র log n depth দিলে size রৈখিক হয়ে যায়। অর্থাৎ “গোনা” বা “যোগ করা” স্বভাবত একটু ক্রমিক; কয়েক স্তরে করা যায় না।
ইতিহাসেও এটি বিশেষ। Furst, Saxe আর Sipser ১৯৮১ সালে, আর স্বাধীনভাবে Ajtai ১৯৮৩ সালে, প্রথম দেখান PARITY ∉ AC0; তাঁদের প্রেরণার একটি অংশ ছিল oracle আর polynomial hierarchy নিয়ে প্রশ্ন (পর্ব ৬৮-এ এর উল্লেখ আছে): স্থির-depth circuit-এর lower bound থেকে এমন oracle পাওয়া যায়, যার সামনে PH ⊊ PSPACE. Yao ১৯৮৫ আর Håstad ১৯৮৬ সালে bound-কে exponential করেন; Håstad-এর “switching lemma” আজও pseudorandomness আর learning theory-তে ব্যবহৃত একটি হাতিয়ার।
Machine learning-এর সঙ্গেও যোগ আছে: স্থির-depth network-এর কী শেখা সম্ভব, সেই আলোচনায় PARITY একটি পরিচিত কঠিন উদাহরণ, যদিও threshold gate-এর (TC0) জন্য PARITY সহজ, আর বাস্তব শেখার কঠিনতা circuit-size থেকে আলাদা প্রশ্ন।
মূল উপলব্ধি: Depth সমান্তরাল সময় আর hardware-এর গতি ঠিক করে; PARITY ∉ AC0 একটি প্রমাণিত সত্য যে কিছু সরল কাজ স্থির সংখ্যক স্তরে দক্ষভাবে করা অসম্ভব, আর log depth-এ সেই অসম্ভবতা মিলিয়ে যায়।
প্র ০৪Karp–Lipton উপপাদ্য P বনাম NP প্রশ্নকে সরাসরি স্পর্শ করে না, তবু গবেষকেরা এটিকে “NP-এর ছোট circuit নেই” বিশ্বাসের প্রধান সমর্থন মনে করেন। কেন? আর Adleman-এর ফল এর পাশে কী বলে?
NP ⊆ P/poly মানে প্রতিটি n-এর জন্য SAT-এর একটি polynomial-size circuit আছে, যদিও তা খুঁজে পাওয়া কঠিন হতে পারে। এটি P = NP-এর চেয়ে দুর্বল দাবি, তাই সরাসরি অসম্ভব বলার কারণ নেই। Karp আর Lipton ১৯৮০ সালে দেখান, এই দুর্বল দাবিরও একটি ভারী পরিণাম আছে: polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ে।
PH ধসে পড়ে না, এই অনুমান complexity-তে P ≠ NP-এর একটি স্বাভাবিক সাধারণীকরণ হিসেবে ব্যাপকভাবে ব্যবহৃত হয় (পর্ব ৬৮): ∃∀ প্রশ্ন ∀∃ প্রশ্নের চেয়ে মৌলিকভাবে আলাদা, প্রতিটি অতিরিক্ত quantifier পালা নতুন শক্তি দেয়। এর বিরুদ্ধে কোনো প্রমাণ নেই, আর অনেক স্বাভাবিক প্রশ্ন (যেমন MIN-FORMULA-র মতো “সবচেয়ে ছোট সমতুল্য সূত্র আছে কি”) Σ2-এর মতো উঁচু স্তরে বসে বলে মনে হয়। তাই Karp–Lipton একটি সেতু: যে PH-এর অসীমতায় বিশ্বাস করে, সে SAT-এর ছোট circuit-এর অনুপস্থিতিতেও বিশ্বাস করতে বাধ্য। পরে এই ফল আরও শক্ত করা হয়েছে, যেমন ধস আরও নিচের শ্রেণিতে নামানো যায় বলে জানা।
Adleman-এর ১৯৭৮ সালের ফল (RP-র জন্য, পরে Bennett ও Gill BPP-তে বাড়ান) উল্টো দিকের একটি শিক্ষা দেয়: ছোট circuit থাকা “অসম্ভব শক্তির” লক্ষণ নয়। BPP ⊆ P/poly: প্রতিটি দৈর্ঘ্যের জন্য একটি “ভালো” random string আছে, যা সেই দৈর্ঘ্যের সব input-এ ঠিক উত্তর দেয়, কারণ ভুলের সম্ভাবনা 2−2n-এর নিচে নামালে union bound-এ সব input-এর মোট ভুল-সম্ভাবনা 2n · 2−2n < 1. তাই randomness-কে advice দিয়ে প্রতিস্থাপন করা যায়। এখানে কোনো ধস নেই; বরং এটি derandomization-এর আশাকে সমর্থন করে, যার uniform রূপ P = BPP এখনো প্রমাণিত নয় (পর্ব ৬৯)।
এই দুটি ফল মিলিয়ে একটি সূক্ষ্ম ছবি: P/poly-তে থাকা নিজে কোনো অসম্ভবতা নয় (BPP সেখানে আছে), কিন্তু NP সেখানে থাকলে quantifier-এর গোটা কাঠামো ভেঙে পড়ে।
মূল উপলব্ধি: Karp–Lipton “NP-এর ছোট circuit” আর “PH-এর ধস”-কে বেঁধে দেয়, তাই PH-এর অসীমতার বিশ্বাস NP ⊄ P/poly-র বিশ্বাস হয়ে যায়; Adleman দেখায় advice randomness সরাতে পারে, যা P/poly-কে অস্বাভাবিক নয়, বরং প্রাকৃতিক শ্রেণি করে।
প্র ০৫একটি প্রশিক্ষিত neural network বা একটি chip, দুটিই শেষ পর্যন্ত circuit. Circuit complexity-র কোন ফল এদের সম্পর্কে কিছু বলে, আর কোথায় সাবধান থাকা দরকার?
Chip-এর ক্ষেত্রে সম্পর্ক সরাসরি। প্রতিটি combinational অংশ একটি Boolean circuit, আর logic synthesis tool একটি truth table বা বর্ণনা থেকে ছোট আর অগভীর circuit খোঁজে। Shannon-এর গণনা বলে, এলোমেলো একটি function-এর জন্য বিশাল circuit লাগবেই, তাই বাস্তবে নকশাকারীরা গঠনযুক্ত function (যোগ, তুলনা, mux) নিয়েই কাজ করেন। সবচেয়ে ছোট circuit খোঁজা কঠিন: অংশ ১-এ মাত্র ৩টি input-এর সব function-এর জন্য scratch-এ আধা মিনিট লেগেছে, আর MCSP (truth table থেকে সর্বনিম্ন circuit size) NP-তে থাকলেও NP-complete কি না অজানা বলে পরিচিত। তাই শিল্পে heuristic আর স্থানীয় উন্নতি ব্যবহৃত হয়।
Neural network-এর ক্ষেত্রে মিল আছে, কিন্তু সাবধানে। স্থির input দৈর্ঘ্য আর স্থির ওজনে একটি feed-forward network একটি threshold circuit; layer-এর সংখ্যা মোটামুটি depth, neuron-এর সংখ্যা মোটামুটি size. এখান থেকে কিছু তাত্ত্বিক সীমা আসে: যেমন নির্দিষ্ট precision-এর transformer uniform TC0-এর মতো শ্রেণিতে পড়ে বলে দেখানো হয়েছে (Merrill ও Sabharwal ২০২৩ বলে পরিচিত), তাই TC0 ≠ NC1 হলে (যা খোলা কিন্তু বিশ্বাস করা হয়) এমন model কিছু ক্রমিক কাজ একবারের হিসাবে করতে পারবে না। “Chain of thought” বা ধাপে ধাপে লেখা সেই সীমা কিছুটা পেরোতে দেয় বলে আলোচিত।
সাবধানতা তিনটি। প্রথম, এসব ফল model-এর অনুমানের (precision, attention-এর ধরন, uniformity) ওপর নির্ভর করে, তাই “transformer X পারে না” কথাটি সবসময় শর্তসহ বলতে হয়। দ্বিতীয়, circuit-size প্রকাশক্ষমতা মাপে, শেখার সহজতা নয়: একটি function-এর ছোট network থাকলেও gradient descent সেটি খুঁজে পাবে, তার নিশ্চয়তা নেই। তৃতীয়, TC0 নিজেই NP-এর বিরুদ্ধে lower bound-এর অজানা অঞ্চল: আমরা জানি না SAT TC0-এ নেই কি না।
পর্ব ৭৯-এ formal language আর machine learning-এর এই সম্পর্ক বিস্তারিত আসবে।
মূল উপলব্ধি: Chip আর neural network দুটিই circuit, তাই size, depth আর গণনার যুক্তি তাদের সীমা নিয়ে কথা বলে; কিন্তু প্রতিটি দাবি model-এর অনুমান আর “প্রকাশ বনাম শেখা”-র পার্থক্যসহ পড়তে হয়, আর বড় lower bound প্রশ্নগুলো এখনো খোলা।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। circuit_min_size.py-র evaluate দিয়ে নিজের circuit যাচাইও করতে পারেন।
-
নকশা: বাজারঘরের একটি অর্ডার “ঝুঁকিপূর্ণ” ধরা হয়, যদি তিনটি সংকেতের (নতুন গ্রাহক, রাতের অর্ডার, ঠিকানা অসম্পূর্ণ) অন্তত দুটি 1 হয়। এই 3-bit majority function MAJ(x1, x2, x3)-এর জন্য ∧, ∨ (fan-in 2) আর ¬ দিয়ে ৪ gate-এর একটি circuit নকশা করুন। Size আর depth বলুন, আর সঠিকতা যুক্তি দিয়ে দেখান।
g1 = x2 ∨ x3, g2 = x1 ∧ g1, g3 = x2 ∧ x3, g4 = g2 ∨ g3. Size ৪, depth ৩ (x2 → g1 → g2 → g4). সঠিকতা: x1 = 1 হলে আর একটি 1 লাগে, অর্থাৎ x2 ∨ x3 (g2); x1 = 0 হলে x2 আর x3 দুটিই লাগে (g3); আর x1 = 1-এ g3 = 1 হলে g2-ও 1, তাই কোনো অতিরিক্ত 1 ঢোকে না। MAJ = x1(x2 ∨ x3) ∨ x2x3.
Scratch-এ সব ৮টি input-এ চালিয়ে truth table 00010111 মিলেছে, আর অংশ ১-এর brute force দেখায় MAJ-এর সবচেয়ে ছোট circuit-এ ঠিক ৪টি gate লাগে, তাই এই নকশা সর্বনিম্ন।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: P ≠ NP. প্রমাণ: Shannon-এর গণনা অনুযায়ী প্রায় সব n-input function-এর জন্য 2n/(10n)-এর বেশি gate লাগে। SAT একটি n-input function, আর এটি খুব জটিল, তাই এটিও প্রায় সব function-এর মতো কঠিন। অতএব SAT ∉ P/poly, আর P ⊆ P/poly বলে SAT ∉ P. ∎” ভুল কোথায়?
ভুলটি “এটিও প্রায় সব function-এর মতো কঠিন” ধাপে। গণনা বলে বেশিরভাগ function কঠিন, কিন্তু কোনো নির্দিষ্ট function সম্পর্কে কিছু বলে না; একটি নির্দিষ্ট function “বেশিরভাগের” মধ্যে পড়ে, তা প্রমাণ ছাড়া মানা যায় না। আসলে SAT এলোমেলো function-এর মতো নয়: একে polynomial সময়ে যাচাই করা যায়, এর গঠন আছে, আর P-এর অনেক “জটিল দেখতে” function-এর polynomial circuit আছে। “খুব জটিল” একটি অনুভূতি, প্রমাণ নয়।
শেষের দুই ধাপ ঠিক: SAT ∉ P/poly প্রমাণিত হলে P ⊆ P/poly থেকে SAT ∉ P, আর P ≠ NP আসত। কিন্তু SAT ∉ P/poly খোলা প্রশ্ন, আর natural proofs বাধা দেখায় এমন সরল “বেশিরভাগের ধর্ম” যুক্তি দিয়ে তা প্রমাণ করা কঠিন।
-
Trace আর আগাম অনুমান: অংশ ১-এর circuit (g1 = ¬x1, g2 = x1 ∧ x2, g3 = x3 ∧ g1, g4 = g2 ∨ g3) input (1, 0, 1)-এ চালালে
evaluate(3, C, (1, 0, 1))কী ছাপবে? তারপর বলুন: n = 16-এর জন্য XOR-বাক্সের সুষম গাছে PARITY-র size আর depth কত, আর PARITY-র সবচেয়ে ছোট DNF-এ কয়টি পদ?g1 = ¬1 = 0, g2 = 1 ∧ 0 = 0, g3 = 1 ∧ 0 = 0, g4 = 0 ∨ 0 = 0. ছাপবে
[0, 0, 0, 0]: ঢাকায় কিন্তু ছোট অর্ডার, কুপন থাকলেও ফ্রি ডেলিভারি নেই। truth table-এর সারি 101-এর output 0-র সঙ্গে মেলে।n = 16: ১৫টি XOR-বাক্স, তাই 4 · 15 = 60টি gate; গাছের উচ্চতা log2 16 = 4, প্রতিটি বাক্স ৩ স্তর, তাই depth 12. DNF-এ অন্তত 215 = 32,768টি পদ (উপপাদ্য ৬.২), প্রতিটিতে ১৬টি literal.
-
প্রমাণ: দেখান যে {1}∗-এর যেকোনো উপসেট U (decidable হোক বা না হোক) P/poly-তে আছে। তারপর ব্যাখ্যা করুন, এটি কেন বোঝায় যে P/poly অগণনীয় (uncountable) সংখ্যক language ধারণ করে, অথচ P গণনীয়।
প্রতিটি n-এর জন্য দৈর্ঘ্য n-এর input-এ U-র সদস্য বড়জোর একটি, 1n. 1n ∈ U হলে Cn = x1 ∧ ⋯ ∧ xn (n − 1টি gate), নইলে Cn = x1 ∧ ¬x1 (২টি gate; n = 0-এর জন্য একটি ধ্রুবক রীতি)। তাহলে প্রতিটি w-এর জন্য C|w|(w) = 1 ⇔ w = 1|w| ∈ U. Size ≤ n + 1, তাই U ∈ SIZE(n) ⊆ P/poly. ∎
{1}∗-এর উপসেট আর ℕ-এর উপসেট একই সংখ্যক (1n ↔ n), আর Cantor-এর উপপাদ্য (পর্ব ০২) অনুযায়ী তারা অগণনীয়। প্রতিটি P/poly-তে, তাই P/poly অগণনীয়। কিন্তু P-এর প্রতিটি language একটি Turing machine দিয়ে, আর Turing machine গণনীয় সংখ্যক। তাই P ⊊ P/poly, আর পার্থক্যটি বিশাল।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রম“প্রায় সব function-এর বড় circuit লাগে” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- n-input function-এর সংখ্যা গোনা: 22n
- s gate-এর circuit-এর সংখ্যার সীমা: (3(n + s)2)s
- s = 2n/(10n) বসিয়ে log2 নেওয়া
- Circuit-এর সংখ্যা function-এর তুলনায় নগণ্য দেখানো
- Pigeonhole: বেশিরভাগ function-এর কোনো ছোট circuit নেই
একটি circuit-এ g1 = x1 ∧ x2, g2 = ¬g1, g3 = g2 ∨ x3 (output). Gate গোনা হলে (¬-সহ) এর size আর depth কত?
- size 6, depth 3
- size 3, depth 2
- size 3, depth 3
- size 3, depth 1
P/poly সম্পর্কে নিচের কোনটি প্রমাণিত সত্য?
- P/poly = P
- P/poly-তে একটি undecidable language আছে
- NP ⊆ P/poly
- NP ⊄ P/poly
n-টি input-এর আলাদা Boolean function f: {0, 1}n → {0, 1} মোট কয়টি?
- 2n
- n2
- n!
- 22n
PARITY(x1, …, xn) সম্পর্কে কোনটি সঠিক?
- এটি NC1-এ আছে কিন্তু AC0-এ নেই
- এটি AC0-এ আছে
- এটি NC1-এ নেই
- এর প্রতিটি circuit-এ exponential size লাগে
Karp–Lipton উপপাদ্য কী বলে?
- NP ⊆ P/poly হলে P = NP
- PH ধসে পড়লে NP ⊆ P/poly
- NP ⊆ P/poly হলে PH = Σ2p
- BPP ⊆ P/poly
সাধারণ Boolean circuit (fan-in 2) মডেলে NP-এর একটি explicit function-এর জন্য জানা lower bound-এর অবস্থা কী?
- SAT-এর জন্য 2Ω(n) প্রমাণিত
- জানা সেরা সীমা রৈখিক (প্রায় 3.1n); superpolynomial সীমা খোলা
- Natural proofs প্রমাণ করেছে এমন lower bound অসম্ভব
- Razborov-এর monotone ফল থেকে সাধারণ circuit-এও superpolynomial প্রমাণিত
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Boolean circuit = ∧, ∨ (fan-in 2), ¬ gate-এর চক্রহীন জাল; size = gate-সংখ্যা, depth = দীর্ঘতম পথ; একটি circuit একটি নির্দিষ্ট n-এর জন্য।
- প্রতিটি function DNF-এ O(n 2n) gate-এ হয় (Lupanov: প্রায় 2n/n); Shannon-এর গণনায় প্রায় সব function-এর Ω(2n/n) লাগে, কিন্তু কোনটি, তা বলে না।
- P/poly = polynomial-size circuit family = polynomial সময় + polynomial advice; P ⊆ P/poly (tableau থেকে O(t2) circuit), আর P/poly-তে undecidable language-ও আছে।
- CIRCUIT-SAT NP-complete, আর Tseitin রূপান্তরে CIRCUIT-SAT ≤p 3SAT. PARITY ∈ NC1 কিন্তু PARITY ∉ AC0 (প্রমাণিত)।
- NP ⊆ P/poly হলে PH = Σ2p (Karp–Lipton); NP-এর জন্য superpolynomial circuit lower bound খোলা, জানা সেরা সাধারণ সীমা প্রায় 3.1n.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬০ · Cook–Levin theorem — SAT কেন NP-completeফিরে দেখুনTableau আর স্থানীয় window, যা এখানে circuit হয়েছে।
- পর্ব ৬৩ · P বনাম NP — প্রশ্ন, তাৎপর্য আর বাধাসংযোগRelativization, natural proofs আর algebrization.
- পর্ব ৬৮ · Oracle, relativization আর polynomial hierarchyসংযোগΣ2p, ধসের উপপাদ্য আর Karp–Lipton-এর প্রেক্ষাপট।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৭১-এ approximation আর PCP.
- Computer Architecture · পর্ব ০৮ — Logic gate আর transistorপাশের ট্র্যাকGate কীভাবে transistor দিয়ে বানানো হয়, delay আর fan-in.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৬৯ — Boolean algebra-র গণিতপাশের ট্র্যাকBoolean function, DNF আর minimization-এর বীজগণিত।