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

Time complexity আর class P

Time Complexity and the Class P — Measuring Turing Machine Time, TIME Classes, Model Dependence, Polynomial Time, Problems in P, Pseudo-Polynomial Traps and EXP

Taught in Bangla, this lesson defines the running time of a Turing machine and the classes TIME(t(n)), P and EXP. It counts the steps of three machines for {0^k1^k} at O(n^2), O(n log n) and O(n), proves that PATH, RELPRIME and every context-free language are in P, and explains why trial division and the subset-sum DP are only pseudo-polynomial. In-page Python (Pyodide) and JavaScript blocks measure step counts, Euclid's steps against bit length and growth rates.

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

  • Turing machine-এর running time-এর সংজ্ঞা আর O, o দিয়ে তা প্রকাশ করা
  • {0k1k}-এর তিনটি যন্ত্রের ধাপ গোনা আর প্রমাণসহ বিশ্লেষণ
  • TIME(t(n)) শ্রেণি, এক-tape বনাম বহু-tape বনাম NTM-এর দাম
  • Class P-এর সংজ্ঞা, কেন polynomial, আর P-তে থাকা চারটি গুরুত্বপূর্ণ সমস্যার প্রমাণ
  • Unary বনাম binary encoding, pseudo-polynomial ফাঁদ, আর EXP-এর সঙ্গে সম্পর্ক

১ · “দ্রুত” মানে কী — Turing machine-এ সময় মাপা

মডিউল ৯ একটি প্রশ্নের উত্তর দিয়েছে: কোন সমস্যা আদৌ algorithm দিয়ে সমাধান করা যায়। উত্তর ছিল দুই ভাগে: decidable আর undecidable (পর্ব ৫০, পর্ব ৫২)। কিন্তু decidable হলেই কাজের হয় না। যে algorithm উত্তর দিতে মহাবিশ্বের বয়সের চেয়ে বেশি সময় নেয়, বাস্তবে সেটি না থাকার মতোই। এই মডিউল থেকে প্রশ্ন বদলায়: কত সম্পদে সমাধান করা যায়? প্রথম সম্পদ সময়। এই বিষয়কে বলে computational complexity.

রেলস্টেশনের টিকিট কাউন্টারের কথা ভাবুন। একজন কর্মীর গতি কত, তা বলতে কেউ “আজ সকালে ১২ মিনিট লেগেছে” বলেন না, কারণ লাইনে কতজন ছিল, তা না জানলে সংখ্যাটির মানে নেই। কাজের কথা হলো: লাইনে n জন থাকলে সময় কীভাবে বাড়ে? প্রতিজনে এক মিনিট হলে সময় n মিনিট। কিন্তু কর্মী যদি প্রতিজনের জন্য পুরো লাইনের সবার নাম আবার মিলিয়ে দেখেন, তাহলে n2 মিনিট। ২০ জনে পার্থক্য সামান্য; ২০০০ জনে প্রথমজন দেড় দিনে শেষ করেন, দ্বিতীয়জনের লাগে প্রায় আট বছর। Complexity তত্ত্ব ঠিক এই “লাইন বড় হলে কী হয়” প্রশ্নটিকে গাণিতিক রূপ দেয়।

মাপার যন্ত্র হিসেবে আমরা আগের মতো Turing machine নিই, সাধারণ এক-tape deterministic যন্ত্র (পর্ব ৪৩)। প্রতিটি transition একটি ধাপ। একটি input-এর সময় মানে থামা পর্যন্ত ধাপের সংখ্যা। কিন্তু একই দৈর্ঘ্যের বিভিন্ন input-এ সময় আলাদা হতে পারে, তাই আমরা সবচেয়ে খারাপটি ধরি।

সংজ্ঞা ১.১ (Running time)

ধরুন M একটি deterministic Turing machine, যা প্রতিটি input-এ থামে (একটি decider). M-এর running time বা time complexity হলো একটি function f: ℕ → ℕ, যেখানে

f(n) = max { M-এর ধাপসংখ্যা w-এর ওপর : |w| = n }

অর্থাৎ দৈর্ঘ্য n-এর সব input-এর মধ্যে সর্বোচ্চ ধাপসংখ্যা। তখন বলা হয়, M একটি f(n)-সময়ের যন্ত্র।

তিনটি সিদ্ধান্ত এই সংজ্ঞায় লুকিয়ে আছে। এক, সময় মাপা হয় input-এর দৈর্ঘ্য n দিয়ে, input-এ লেখা সংখ্যার মান দিয়ে নয়। এই পার্থক্য অংশ ৬ আর ৭-এ বড় হয়ে ফিরবে। দুই, শুধু decider-এর সময় সংজ্ঞায়িত; যে যন্ত্র কোনো input-এ loop করে, তার running time নেই। তিন, worst case নেওয়া হয়েছে। Average case-ও গুরুত্বপূর্ণ, কিন্তু তার জন্য input-এর একটি সম্ভাবনা-বণ্টন লাগে, যা এই কোর্সে পর্ব ৭৬-এ ফিরবে।

বাজারঘরের ভাষায়: প্রতিদিন রাতে সার্ভার সব অর্ডার-লগ পরীক্ষা করে। লগের দৈর্ঘ্য n অক্ষর। Programmer-এর আসল প্রশ্ন, “আগামী বছর লগ দশগুণ হলে রাতের কাজ কি সকালের আগে শেষ হবে?” এর উত্তর দেয় f(n)-এর বৃদ্ধির হার, কোনো একদিনের মাপা সময় নয়।

২ · Asymptotic ভাষা — O, o আর বৃদ্ধির হার

সঠিক ধাপসংখ্যা, যেমন f(n) = 6n2 + 20n + 5, প্রায়ই জটিল আর যন্ত্রের খুঁটিনাটির ওপর নির্ভরশীল: একটি state বেশি বা কম রাখলে গুণক বদলায়। তাই আমরা শুধু সবচেয়ে বড় পদটি রাখি আর গুণক বাদ দিই। এই ভাষা DSA কোর্সের পর্ব ০৪-এ বিস্তারিত আছে; এখানে শুধু সংজ্ঞা দুটি মনে করিয়ে দেওয়া হলো।

সংজ্ঞা ২.১ (O আর o)

f, g: ℕ → ℝ+ দুটি function.
১. f(n) = O(g(n)), যদি এমন ধ্রুবক c > 0 আর n0 থাকে, যাতে সব n ≥ n0-এ f(n) ≤ c · g(n).
২. f(n) = o(g(n)), যদি limn→∞ f(n)/g(n) = 0; অর্থাৎ প্রতিটি c > 0-এর জন্য এমন n0 আছে, যাতে সব n ≥ n0-এ f(n) < c · g(n).

O মানে “বড়জোর এই হারে”, o মানে “এই হারের চেয়ে কঠোরভাবে ধীরে”। উদাহরণ: 6n2 + 20n + 5 = O(n2), কিন্তু o(n2) নয়; n log n = o(n2); √n = o(n). Logarithm-এর ভিত্তি লেখা হয় না, কারণ loga n = logb n / logb a, অর্থাৎ শুধু একটি ধ্রুবক গুণের পার্থক্য। দুই দিকের আঁটসাঁট সীমা Θ (f = O(g) আর g = O(f)) মাঝে মাঝে কাজে লাগবে।

দুই ধরনের সীমা বিশেষ নাম পায়। nc (c > 0 একটি ধ্রুবক) আকারের সীমা polynomial. 2nδ (δ > 0) আকারের সীমা exponential. এদের মধ্যে ফারাক শুধু পরিমাণের নয়, চরিত্রের। n দ্বিগুণ হলে n3 আটগুণ হয়, একটি স্থির গুণক। কিন্তু 2n বর্গ হয়ে যায়: 22n = (2n)2. নিচের JavaScript ব্লকটি চালিয়ে দেখুন। এটি ধরে নেয়, যন্ত্র প্রতি সেকেন্ডে 109 ধাপ চালায়।

// Growth of step counts, at an assumed 10^9 steps per second.
const fns = [["n log n", n => n * Math.log2(n)], ["n^2", n => n ** 2],
             ["n^3", n => n ** 3], ["2^n", n => 2 ** n]];
const time = s => {                    // seconds -> readable text
  const units = [["year", 3.156e7], ["day", 86400], ["hour", 3600],
                 ["min", 60], ["s", 1], ["ms", 1e-3], ["us", 1e-6]];
  for (const [u, k] of units) if (s >= k) return (s / k).toPrecision(3) + " " + u;
  return (s * 1e9).toPrecision(3) + " ns";
};
for (const n of [20, 40, 60, 100, 1000]) {
  console.log(`n = ${n}`);
  for (const [name, f] of fns) {
    const steps = f(n);
    console.log(`  ${name.padEnd(8)} ${steps.toExponential(2).padStart(9)}` +
                `  ${time(steps / 1e9)}`);
  }
}
// Doubling n: polynomial grows by a fixed factor, 2^n squares.
const r = (f, n) => (f(2 * n) / f(n)).toPrecision(3);
console.log("factor when n doubles 50 -> 100:",
            fns.map(([name, f]) => `${name}: x${r(f, 50)}`).join(", "));

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

n = 20
  n log n    8.64e+1  86.4 ns
  n^2        4.00e+2  400 ns
  n^3        8.00e+3  8.00 us
  2^n        1.05e+6  1.05 ms
n = 40
  n log n    2.13e+2  213 ns
  n^2        1.60e+3  1.60 us
  n^3        6.40e+4  64.0 us
  2^n       1.10e+12  18.3 min
n = 60
  n log n    3.54e+2  354 ns
  n^2        3.60e+3  3.60 us
  n^3        2.16e+5  216 us
  2^n       1.15e+18  36.5 year
n = 100
  n log n    6.64e+2  664 ns
  n^2        1.00e+4  10.0 us
  n^3        1.00e+6  1.00 ms
  2^n       1.27e+30  4.02e+13 year
n = 1000
  n log n    9.97e+3  9.97 us
  n^2        1.00e+6  1.00 ms
  n^3        1.00e+9  1.00 s
  2^n      1.07e+301  3.40e+284 year
factor when n doubles 50 -> 100: n log n: x2.35, n^2: x4.00, n^3: x8.00, 2^n: x1.13e+15

n = 40 পর্যন্ত চারটিই চোখের পলকে শেষ। n = 60-এ 2n ধাপে লাগে প্রায় ৩৬ বছর, অথচ n3 লাগে এক মিলিসেকেন্ডের এক-পঞ্চমাংশ। n = 100-এ 2n প্রায় 4 × 1013 বছর, মহাবিশ্বের বয়সের কয়েক হাজার গুণ। শেষ লাইন নিয়মটি দেখায়: n দ্বিগুণ হলে n2 চারগুণ, n3 আটগুণ, কিন্তু 2n বাড়ে প্রায় 1015 গুণ। দ্রুততর যন্ত্র কিনে polynomial algorithm-কে বড় input-এ ঠেলে নেওয়া যায়; exponential algorithm-কে যায় না।

৩ · একটি language, তিনটি যন্ত্র — {0k1k}-এর n2, n log n আর n

এবার একটি পরিচিত language নিয়ে সত্যিকারের ধাপ গোনা যাক: A = {0k1k : k ≥ 0}. পর্ব ১৭-এ দেখেছেন, A regular নয়। পর্ব ৪৪-এ এমন language-এর জন্য crossing-off যন্ত্র বানানো হয়েছিল। এখানে প্রশ্ন একটাই: কত ধাপে? Sipser-এর বইয়ের অনুসরণে তিনটি যন্ত্র দেখব। প্রতিটি “sweep” মানে head বাঁ প্রান্ত থেকে ডানের blank পর্যন্ত গিয়ে আবার ফিরে আসা, অর্থাৎ 2(n + 1) ধাপ।

M1 (এক tape, zig-zag). “M1 = input w-এর ওপর:
১. Tape একবার পড়া; কোনো 1-এর ডানে 0 পেলে reject.
২. যতক্ষণ tape-এ 0 আর 1 দুটোই আছে: একটি sweep-এ একটি 0 আর একটি 1 কেটে x করা।
৩. শেষে কোনো 0 বা 1 বাকি থাকলে reject, নইলে accept.”

উপপাদ্য ৩.১

M1 A-কে decide করে, আর এর running time O(n2).

প্রমাণ।

  1. ধাপ ১ একটি sweep: O(n). — head একবার ডানে, একবার বাঁয়ে
  2. ধাপ ২-এর প্রতিটি পুনরাবৃত্তি দুটি চিহ্ন কাটে, তাই বড়জোর n/2 বার চলে; প্রতিটি একটি sweep, O(n). মোট O(n) · O(n) = O(n2). — প্রতিবার দুটি ঘর স্থায়ীভাবে x হয়
  3. ধাপ ৩ আরেকটি sweep: O(n). — ধাপ ১-এর মতো
  4. যোগফল O(n) + O(n2) + O(n) = O(n2). সঠিকতা: ধাপ ১ নিশ্চিত করে w ∈ 0∗1∗; ধাপ ২ 0 আর 1 জোড়ায় জোড়ায় কাটে, তাই শেষে কিছু বাকি না থাকা মানে দুটির সংখ্যা সমান। ∎

O(n2)-এর চেয়ে ভালো করা যায় কি? প্রতি sweep-এ মাত্র একটি জোড়া কাটা অপচয়। পরের যন্ত্র প্রতি sweep-এ বাকি চিহ্নের অর্ধেক কাটে।

M2 (এক tape, অর্ধেক করা)। “M2 = input w-এর ওপর:
১. Tape পড়া; কোনো 1-এর ডানে 0 পেলে reject.
২. যতক্ষণ tape-এ 0 আর 1 দুটোই আছে:
৩.   একটি sweep-এ বাকি 0 আর 1-এর মোট সংখ্যা জোড় না বিজোড়, তা দেখা; বিজোড় হলে reject.
৪.   আরেকটি sweep-এ প্রথম 0 থেকে শুরু করে একটি বাদে একটি 0 কাটা, তারপর প্রথম 1 থেকে শুরু করে একটি বাদে একটি 1 কাটা।
৫. কোনো 0 বা 1 বাকি না থাকলে accept, নইলে reject.”

নিচের stepper input 000111-এ M2-এর প্রতিটি sweep দেখায়। এখানে n = 6, তাই প্রতি sweep 2(6 + 1) = 14 ধাপ।

11-এর ডানে 0? তাহলে reject20 আর 1 দুটোই বাকি থাকলে:3  মোট সংখ্যা বিজোড়? reject4  একটি বাদে একটি 0, তারপর 1 কাটা5কিছু বাকি নেই? accept
Tape আর হিসাব
tape
বাকি 0, 1
মোট সংখ্যা
sweep
ধাপ এ পর্যন্ত
  1. Sweep ১, ক্রম পরীক্ষা। Head বাঁ থেকে ডানে যায়। কোনো 1-এর পরে 0 নেই, তাই w ∈ 0∗1∗. ফিরে আসা পর্যন্ত ১৪ ধাপ।
  2. Sweep ২, জোড়-বিজোড়। বাকি তিনটি 0 আর তিনটি 1, মোট ৬, জোড়। Reject নয়। ধাপ এ পর্যন্ত ২৮.
  3. Sweep ৩, অর্ধেক কাটা। প্রথম 0 থেকে শুরু করে একটি বাদে একটি: ঘর ১ আর ৩-এর 0 কাটা। একইভাবে ঘর ৪ আর ৬-এর 1. Tape x0xx1x; বাকি একটি করে।
  4. Sweep ৪, জোড়-বিজোড়। বাকি একটি 0 আর একটি 1, মোট ২, জোড়। লক্ষ করুন, 3-কে binary-তে লিখলে 11; প্রতিটি দফায় বাকি সংখ্যার জোড়-বিজোড় সেই binary অঙ্কগুলো নিচ থেকে পড়ে।
  5. Sweep ৫, আবার অর্ধেক। একমাত্র 0 আর একমাত্র 1 কাটা হলো: xxxxxx. এখন আর 0 বা 1 নেই, তাই ধাপ ২-এর লুপ শেষ।
  6. Sweep ৬, শেষ পরীক্ষা। কিছু বাকি নেই: ACCEPT. মোট ৬টি sweep, 6 × 14 = 84 ধাপ। একই input-এ M1-এর লাগে ৫টি sweep, অর্থাৎ ৭০ ধাপ; ছোট input-এ M2 ভালো নয়, তার জয় বড় n-এ।
উপপাদ্য ৩.২

M2 A-কে decide করে, আর এর running time O(n log n).

প্রমাণ।

  1. সময়: ধাপ ৪-এর প্রতিটি পুনরাবৃত্তি বাকি 0-গুলোর অন্তত অর্ধেক কাটে (c থেকে ⌊c/2⌋ বাকি থাকে), 1-এর ক্ষেত্রেও তা-ই। তাই লুপ বড়জোর 1 + log2 n বার চলে। — c ≥ 1 হলে ⌊c/2⌋ ≤ c/2
  2. প্রতিটি পুনরাবৃত্তি দুটি sweep, O(n); ধাপ ১ আর ৫ আরও দুটি। মোট O(n) · O(log n) = O(n log n). — ধাপ ১-এর গণনা
  3. সঠিকতা, “⇐”: w = 0k1k হলে প্রতিটি দফায় দুটি সংখ্যা সমান থাকে (একই c থেকে একই ⌊c/2⌋), তাই মোট সবসময় জোড়, কখনো reject হয় না, আর শেষে দুটিই 0: accept. — আরোহ
  4. সঠিকতা, “⇒”: ধরুন w = 0a1b, a ≠ b. দফা i-এর শুরুতে বাকি সংখ্যা ⌊a/2i⌋ আর ⌊b/2i⌋; এদের জোড়-বিজোড় হলো a আর b-এর binary রূপের i-তম অঙ্ক। a ≠ b বলে কোনো অবস্থানে অঙ্ক আলাদা; প্রথম এমন অবস্থানে, যদি দুটি সংখ্যাই তখনো শূন্য না হয়, মোট বিজোড়: reject. আর যদি একটি আগেই শূন্য হয়ে যায়, লুপ থামে আর অন্যটির চিহ্ন বাকি থাকে, ধাপ ৫-এ reject. ∎

M3 (দুই tape). “M3 = input w-এর ওপর: ১. tape ১-এ 0-গুলো পেরোনোর সময় প্রতিটির একটি কপি tape ২-এ লেখা। ২. tape ১-এ 1-গুলো পেরোনোর সময় tape ২-এ প্রতিটি 1-এর জন্য একটি 0 বাঁয়ে সরে মেলানো। ৩. দুটি একসঙ্গে ফুরোলে, আর 1-এর পরে কোনো 0 না থাকলে, accept.” প্রতিটি ধাপে দুই head একসঙ্গে সরে; মোট ধাপ n + O(1), অর্থাৎ O(n). দুই-tape যন্ত্রের সংজ্ঞা পর্ব ৪৫-এ আছে।

এবার Python-এ তিনটি যন্ত্র চালিয়ে ধাপ গোনা যাক। Code implementation-স্তরের: tape একটি list, আর প্রতিটি sweep-কে 2(n + 1) ধাপ ধরা হয়েছে; একটি পূর্ণ δ-সারণির যন্ত্রে শুধু ধ্রুবক গুণক বদলাবে। প্রথমে দৈর্ঘ্য ১২ পর্যন্ত ৮১৯১টি string-এ তিনটি যন্ত্রকে A-এর সংজ্ঞার সঙ্গে মেলানো হয়, তারপর দেখা হয় n = 12-এ worst case আসলেই 0616 কি না, শেষে বড় n-এ ধাপসংখ্যাকে n2, n log n আর n দিয়ে ভাগ করা হয়।

from itertools import product; from math import log2
def M1(w):                            # one tape, zig-zag (Sipser's M1)
    t, sweeps = list(w), 1            # sweep = to the blank and back
    if "10" in w: return False, sweeps                 # stage 1
    while "0" in t and "1" in t:                       # stage 2
        t[t.index("0")] = "x"; t[t.index("1")] = "x"; sweeps += 1
    return "0" not in t and "1" not in t, sweeps + 1   # stage 3
def M2(w):                            # one tape, halving (Sipser's M2)
    t, sweeps = list(w), 1
    if "10" in w: return False, sweeps
    while "0" in t and "1" in t:
        sweeps += 1                                    # parity sweep
        if (t.count("0") + t.count("1")) % 2: return False, sweeps
        sweeps += 1                                    # cross every other
        for c in "01":
            for i in [i for i, x in enumerate(t) if x == c][::2]: t[i] = "x"
    return "0" not in t and "1" not in t, sweeps + 1
def M3(w):                            # two tapes: one step = one joint move
    i = z = s = 0
    while i < len(w) and w[i] == "0": i += 1; z += 1; s += 1   # copy 0s
    s += 1                                             # tape-2 head back
    while i < len(w) and w[i] == "1" and z: i += 1; z -= 1; s += 1
    return i == len(w) and z == 0, s + 1
def steps(M, w):                      # a sweep costs 2(n + 1) steps
    ok, k = M(w); return ok, (k if M is M3 else k * 2 * (len(w) + 1))
words = ["".join(p) for n in range(13) for p in product("01", repeat=n)]
inA = lambda w: w == "0" * (len(w) // 2) + "1" * (len(w) // 2)
print("correct on", len(words), "strings:",
      all(steps(M, w)[0] == inA(w) for M in (M1, M2, M3) for w in words))
print("n=12 worst = 0^6 1^6:", all(max(steps(M, w)[1] for w in words
      if len(w) == 12) == steps(M, "0"*6 + "1"*6)[1] for M in (M1, M2, M3)))
print("    n   M1 steps  /n^2   M2 steps  /nlogn  M3 /n")
for n in (64, 256, 1024, 4096):
    a, b, c = (steps(M, "0"*(n//2) + "1"*(n//2))[1] for M in (M1, M2, M3))
    print(f"{n:5} {a:10} {a/n**2:5.2f} {b:9} {b/(n*log2(n)):6.2f} {c:4} {c/n:4.2f}")

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

correct on 8191 strings: True
n=12 worst = 0^6 1^6: True
    n   M1 steps  /n^2   M2 steps  /nlogn  M3 /n
   64       4420  1.08      1820   4.74   66 1.03
  256      66820  1.02      9252   4.52  258 1.01
 1024    1053700  1.00     45100   4.40 1026 1.00
 4096   16797700  1.00    213044   4.33 4098 1.00

প্রথম দুই লাইন ভিত্তি পাকা করে: তিনটি যন্ত্রই ৮১৯১টি string-এ ঠিক A-কে decide করে, আর n = 12-এ সবচেয়ে বেশি ধাপ লাগে 0616-এ, তাই আমরা worst case-ই মাপছি। সারণিতে n চারগুণ হলে M1-এর ধাপ প্রায় ষোলোগুণ (n2), আর অনুপাত /n^2 স্থির হয়ে 1.00-এ বসে: আসলে ধাপ ঠিক (n + 1)(n + 4). M2-এর /nlogn অনুপাত 4.74 থেকে ধীরে 4-এর দিকে নামছে, কারণ প্রতি দফায় দুটি sweep আর দফা প্রায় log2 n টি। n = 4096-এ M2 M1-এর চেয়ে প্রায় ৭৯ গুণ কম ধাপ নেয়। M3-এর ধাপ n + 2, দুই tape-এর সুবিধা। মনে রাখবেন, এমন মাপ বৃদ্ধির হার দেখায়, প্রমাণ করে না; প্রমাণ ছিল উপরের উপপাদ্যে।

৪ · Model-এর ওপর নির্ভরতা আর TIME শ্রেণি

অংশ ৩-এর শিক্ষা অস্বস্তিকর: একই language-এর “সময়” এক-tape যন্ত্রে n log n, দুই-tape যন্ত্রে n. Computability-তে এমন সমস্যা ছিল না; সেখানে সব যুক্তিসংগত model একই language decide করে (পর্ব ৪৭)। Complexity-তে model-এর পছন্দ ফলাফল বদলায়, তাই একটি model ঠিক করে নিতে হয়। প্রচলিত রীতি হলো এক-tape deterministic Turing machine.

সংজ্ঞা ৪.১ (Time complexity class)

t: ℕ → ℝ+ একটি function হলে

TIME(t(n)) = { L : কোনো O(t(n))-সময়ের এক-tape deterministic Turing machine L-কে decide করে }

এই সংজ্ঞায় A ∈ TIME(n log n). আরও আছে, যা এখানে প্রমাণ করা হবে না: Trakhtenbrot আর Hartmanis-এর ১৯৬০-এর দশকের কাজ থেকে জানা যায় বলে পরিচিত যে এক-tape যন্ত্রে o(n log n) সময়ে decide হওয়া প্রতিটি language regular. A regular নয়, তাই এক-tape যন্ত্রে M2-এর চেয়ে asymptotically ভালো করা অসম্ভব। অথচ দুই tape-এ O(n). তাহলে model-এর ফারাক কতটা বড় হতে পারে? দুটি উপপাদ্য উত্তর দেয়, দুটিই আগের পর্বে প্রমাণিত।

উপপাদ্য ৪.২ (বহু-tape থেকে এক-tape, পর্ব ৪৫)

t(n) ≥ n হলে, প্রতিটি t(n)-সময়ের multi-tape Turing machine-এর একটি সমতুল্য O(t2(n))-সময়ের এক-tape Turing machine আছে।

উপপাদ্য ৪.৩ (NTM থেকে DTM, পর্ব ৪৬)

t(n) ≥ n হলে, প্রতিটি t(n)-সময়ের nondeterministic এক-tape decider-এর একটি সমতুল্য 2O(t(n))-সময়ের deterministic এক-tape decider আছে।

দুটির পার্থক্যই এই মডিউলের মূল সুর। পর্ব ৪৫-এর প্রমাণে এক-tape যন্ত্র সব tape-এর বিষয়বস্তু পাশাপাশি রাখে আর প্রতি ধাপে পুরো ব্যবহৃত অংশ পড়ে; ব্যবহৃত অংশ বড়জোর O(t(n)) লম্বা, তাই প্রতি ধাপে O(t(n)), মোট O(t2). দাম polynomial. পর্ব ৪৬-এর simulation computation tree-র সব শাখা খোঁজে; শাখা bt(n) পর্যন্ত, তাই দাম exponential. ভালো কোনো simulation আছে কি না, তা জানা নেই। এটিই P বনাম NP প্রশ্নের একটি রূপ।

Simulationদামধরন
k-tape → এক-tapet → O(t2)polynomial
দুই দিকে অসীম tape, multi-track → এক-tapet → O(t) বা O(t2)polynomial
RAM (log-cost) → Turing machinet → tO(1)polynomial
NTM → DTMt → 2O(t)exponential (ভালো কিছু অজানা)

RAM হলো সাধারণ কম্পিউটারের মতো model: memory-র যেকোনো ঘরে এক ধাপে পৌঁছানো যায়। “log-cost” মানে বড় সংখ্যার ওপর একটি operation-এর দাম তার bit-সংখ্যা ধরে গোনা হয়। এই শর্ত না মানলে বিপদ: একটি RAM যদি প্রতি ধাপে একটি সংখ্যাকে নিজের সঙ্গে গুণ করে এক ধাপ ধরে, তাহলে n ধাপে 22n আকারের সংখ্যা বানায়, যা লিখতেই exponential জায়গা লাগে। তাই যুক্তিসংগত model মানে যে model-এ এক ধাপে polynomial-এর বেশি কাজ লুকানো যায় না।

৫ · Class P — কেন polynomial

সারণির প্রথম তিন সারি একটি সুসংবাদ দেয়: deterministic model বদলালে সময় বদলায়, কিন্তু polynomial থেকে polynomial-এ। তাই যদি আমরা গুণক আর ঘাতের খুঁটিনাটি বাদ দিয়ে শুধু “polynomial কি না” জিজ্ঞাসা করি, উত্তর model-এর ওপর নির্ভর করে না।

সংজ্ঞা ৫.১ (Class P)

P = ⋃k ≥ 1 TIME(nk)

অর্থাৎ P হলো সেইসব language-এর শ্রেণি, যাদের কোনো এক-tape deterministic Turing machine polynomial সময়ে decide করে।

Polynomial কেন? তিনটি কারণ, গুরুত্বের ক্রমে।

  1. Robustness: এক-tape, বহু-tape, RAM, যেকোনো সাধারণ programming ভাষা, সবগুলোতে P একই শ্রেণি। ফলে একটি algorithm Python-ধাঁচের pseudo-code-এ লিখে “প্রতিটি ধাপ polynomial, ধাপ polynomial সংখ্যক” দেখালেই প্রমাণ হয় যে সমস্যাটি P-তে। Turing machine-এর state আঁকার দরকার পড়ে না।
  2. Composition-এ বদ্ধ: polynomial-এর polynomial polynomial. একটি polynomial-সময়ের algorithm যদি আরেকটিকে polynomial বার subroutine হিসেবে ডাকে, পুরো জিনিসটি polynomial থাকে। (n2 বার একটি n3 subroutine, যার input বড়জোর n2 লম্বা: মোট বড়জোর n2 · (n2)3 = n8.) এই ধর্মই পর্ব ৫৯-এর reduction-কে কাজের করবে।
  3. বাস্তবের সঙ্গে মোটামুটি মিল: অংশ ২-এর সারণির মতো, exponential algorithm সাধারণত ছোট n-এই অচল হয়, আর polynomial algorithm সাধারণত বড় n-এও চলে।

এই ধারণাকে বলে Cobham–Edmonds thesis: “দক্ষভাবে সমাধানযোগ্য” = P-তে আছে। এটি একটি thesis, উপপাদ্য নয়, আর এর সীমাও স্পষ্ট। n100 সময়ের algorithm তত্ত্বে polynomial, বাস্তবে অচল। অন্যদিকে কিছু exponential worst case-এর algorithm বাস্তবের input-এ ভালো চলে, যেমন linear programming-এর simplex পদ্ধতি। তবু অভিজ্ঞতায় দেখা গেছে, একটি স্বাভাবিক সমস্যা একবার P-তে প্রমাণিত হলে তার ঘাত প্রায়ই পরে ছোট হয়ে আসে। ভাবনার প্রশ্ন ১-এ বিস্তারিত।

১৯৬৫ সালে Juris Hartmanis আর Richard Stearns-এর প্রবন্ধ “On the computational complexity of algorithms” Turing machine-এ সময় মাপার নিয়ম আর TIME শ্রেণির ধারণা দেয়; এর জন্য তাঁরা ১৯৯৩ সালে Turing Award পান। একই বছর, আলাদাভাবে, Alan Cobham একটি প্রবন্ধে polynomial সময়ের function-এর একটি model-নিরপেক্ষ শ্রেণির প্রস্তাব দেন, আর Jack Edmonds graph-এর matching-এর algorithm-এর প্রবন্ধে polynomial সময়কে “ভালো algorithm”-এর মাপকাঠি বলেন বলে পরিচিত। P নামটি পরে প্রচলিত হয়।

P নিয়ে প্রমাণ লেখা সহজ, কারণ এটি অনেক operation-এ বদ্ধ। একটি উদাহরণ:

উপপাদ্য ৫.২ (P-এর closure)

A, B ∈ P হলে A ∪ B, A ∩ B, A̅ আর AB (concatenation) সবই P-তে।

প্রমাণ। ধরুন MA আর MB যথাক্রমে O(na) আর O(nb) সময়ের decider.

  1. A̅: MA চালিয়ে উত্তর উল্টে দেওয়া। সময় একই। — decider সবসময় থামে বলে উল্টানো নিরাপদ
  2. A ∪ B আর A ∩ B: w-এর ওপর আগে MA, তারপর MB, উত্তর দুটি OR বা AND করা। সময় O(na + nb). — দুটি polynomial-এর যোগফল polynomial
  3. AB: |w| = n হলে w-কে xy-তে ভাঙার n + 1টি উপায়। প্রতিটির জন্য MA(x) আর MB(y) চালানো; কোনোটিতে দুটিই accept করলে accept. সময় O((n + 1)(na + nb)). — polynomial সংখ্যক polynomial কাজ
  4. প্রতিটি ক্ষেত্রে সময় polynomial, তাই ভাষাটি P-তে। (Multi-tape বা pseudo-code-এ লেখা যন্ত্রকে উপপাদ্য ৪.২ এক-tape-এ আনে, polynomial দামে।) ∎

Kleene star-ও P-তে বদ্ধ, কিন্তু সরল “সব ভাঙন চেষ্টা” সেখানে exponential হয়ে যায় (2n−1টি ভাঙন); dynamic programming লাগে। অনুশীলনের জন্য সেটি ভালো একটি প্রশ্ন।

৬ · P-তে কয়েকটি সমস্যা — PATH, RELPRIME, ACFG আর PRIMES

একটি সমস্যা P-তে প্রমাণ করার ছক সবসময় একই: (১) input কীভাবে যুক্তিসংগতভাবে encode হয় আর তার দৈর্ঘ্য n কত, তা বলা (পর্ব ০৫); (২) algorithm-কে ধাপে ভাগ করা; (৩) দেখানো যে ধাপের সংখ্যা n-এর polynomial আর প্রতিটি ধাপ polynomial সময়ের। Graph-কে adjacency matrix বা adjacency list, যেকোনোভাবে লিখলে দৈর্ঘ্য দুটি পরস্পরের polynomial, তাই উত্তর বদলায় না। কিন্তু সংখ্যা লিখতে হবে binary-তে (বা যেকোনো ভিত্তিতে, যা ≥ 2). এই শর্তের গুরুত্ব নিচে স্পষ্ট হবে।

৬.১ PATH

PATH = { ⟨G, s, t⟩ : G একটি directed graph, যেখানে s থেকে t-এ একটি directed পথ আছে }

বাজারঘরের প্রশ্ন: “ঢাকার গুদাম থেকে একমুখী কুরিয়ার-রুট ধরে চট্টগ্রামে মাল পৌঁছানো যায় কি?” সব পথ একটি একটি করে চেষ্টা করা brute force: m-টি vertex থাকলে সম্ভাব্য পথ mm পর্যন্ত, exponential. তার বদলে চিহ্ন দেওয়া (marking), যা আসলে BFS-এর reachability পরীক্ষা।

বাজারঘরের একমুখী কুরিয়ার-রুট

s = ঢাকা, t = চট্টগ্রাম। তীর একমুখী রুট। বরিশাল থেকে চট্টগ্রামে রুট আছে, কিন্তু বরিশালে ঢোকার কোনো রুট নেই।

PATH instance: one-way courier routes from Dhaka ঢাকা গাজীপুর নরসিংদী ময়মন. রংপুর সিলেট চট্ট. বরিশাল s t
ছবি ৫৭.১ — সবুজ পথ ঢাকা → নরসিংদী → সিলেট → চট্টগ্রাম, তাই ⟨G, ঢাকা, চট্টগ্রাম⟩ ∈ PATH. “ময়মন.” = ময়মনসিংহ, “চট্ট.” = চট্টগ্রাম। হলুদ বরিশাল থেকে চট্টগ্রামে যাওয়া যায়, কিন্তু ঢাকা থেকে বরিশালে নয়: তীরের দিক গুরুত্বপূর্ণ।

Algorithm MPATH: “১. s-কে চিহ্নিত করা। ২. নতুন কোনো vertex চিহ্নিত না হওয়া পর্যন্ত: সব edge (a, b) দেখা; a চিহ্নিত আর b চিহ্নিত নয় হলে b-কে চিহ্নিত করা। ৩. t চিহ্নিত হলে accept, নইলে reject.” নিচের stepper-এ প্রতি round-এ শুধু round শুরুর আগে চিহ্নিত vertex থেকে বেরোনো edge দেখা হয়, তাই round k-তে ঠিক s থেকে k দূরত্বের vertex-গুলো চিহ্নিত হয়, BFS-এর স্তরের মতো।

1s = ঢাকা চিহ্নিত2প্রতিটি edge (a, b): a চিহ্নিত, b নয় → b চিহ্নিত3নতুন কিছু নেই → থামা4t চিহ্নিত? accept, নইলে reject
চিহ্নের হিসাব
round
নতুন চিহ্নিত
মোট চিহ্নিত
t চিহ্নিত?
  1. Round ০. শুধু s = ঢাকা চিহ্নিত। আটটি vertex-এর মধ্যে একটি।
  2. Round ১. ঢাকা থেকে বেরোনো edge দুটি: গাজীপুর আর নরসিংদী চিহ্নিত। মোট ৩.
  3. Round ২. গাজীপুর → ময়মনসিংহ, নরসিংদী → সিলেট। মোট ৫.
  4. Round ৩. সিলেট → চট্টগ্রাম আর ময়মনসিংহ → রংপুর। t = চট্টগ্রাম চিহ্নিত হলো। মোট ৭.
  5. Round ৪. রংপুর → গাজীপুর আর চট্টগ্রাম → ঢাকা, দুটির মাথাই আগে থেকে চিহ্নিত। নতুন কিছু নেই, তাই থামা। t চিহ্নিত: ACCEPT. বরিশাল কখনো চিহ্নিত হয়নি, কারণ তার edge শুধু বাইরের দিকে।
উপপাদ্য ৬.১

PATH ∈ P.

প্রমাণ। G-এর m-টি vertex আর e-টি edge থাকলে, যুক্তিসংগত encoding-এ input-এর দৈর্ঘ্য n ≥ m আর n ≥ e.

  1. ধাপ ১ আর ৩ একবার চলে, প্রতিটি O(n). — একটি চিহ্ন বসানো বা খোঁজা
  2. ধাপ ২-এর প্রতিটি round (শেষটি ছাড়া) অন্তত একটি নতুন vertex চিহ্নিত করে, তাই round বড়জোর m + 1টি। — চিহ্নিত vertex কখনো চিহ্ন হারায় না
  3. প্রতিটি round e-টি edge দেখে, প্রতিটি দেখা polynomial সময়ে (চিহ্ন খোঁজা)। তাই প্রতিটি round polynomial. — encoding-এর দৈর্ঘ্য
  4. সঠিকতা: s থেকে দূরত্ব d-এর প্রতিটি vertex round d-এর মধ্যে চিহ্নিত হয় (d-এর ওপর আরোহ), আর শুধু s থেকে পৌঁছানো যায় এমন vertex-ই চিহ্নিত হয়। মোট সময় (m + 1) × polynomial = polynomial. ∎

৬.২ RELPRIME আর Euclid

RELPRIME = { ⟨x, y⟩ : x আর y সহমৌলিক, অর্থাৎ gcd(x, y) = 1 }

এখানে সবচেয়ে সাধারণ ভুলটি ঘটে। সরল algorithm: d = 2, 3, …, min(x, y) পর্যন্ত প্রতিটি দেখা, কোনোটি দুটিকেই ভাগ করে কি না। ধাপসংখ্যা প্রায় x-এর মানের সমানুপাতিক, যা দেখতে “রৈখিক”। কিন্তু input-এর দৈর্ঘ্য x-এর মান নয়; binary-তে x লিখতে লাগে প্রায় log2 x bit. দৈর্ঘ্য n bit হলে মান 2n পর্যন্ত, তাই এই algorithm-এর সময় n-এর exponential. একই কথা খাটে মৌলিকতা পরীক্ষার trial division-এ, যা √N পর্যন্ত ভাগ করে। নিচের stepper দেখায়, input এক bit লম্বা হলে কাজ কীভাবে বাড়ে।

1b = N-এর bit-সংখ্যা = input-এর দৈর্ঘ্য2d = 2, 3, …, ⌊√N⌋ দিয়ে ভাগ3ভাগ যায়? তাহলে যৌগিক4সবচেয়ে খারাপে ভাগ ≈ √N < 2^(b/2)
Input-এর দৈর্ঘ্য বনাম কাজ
b (bit)
সর্বোচ্চ ভাগ
সময় (10⁹ ভাগ/সেকেন্ড)
  1. ৮ bit. N = 221 (binary 11011101). √221 ≈ 14.9, তাই d = 2 থেকে 14 পর্যন্ত বড়জোর ১৩টি ভাগ; d = 13-এ ভাগ যায় (221 = 13 × 17), যৌগিক। ৮ bit-এর যেকোনো N-এ ভাগ ১৬-র কম।
  2. ১৬ bit. Input দ্বিগুণ লম্বা, কিন্তু সবচেয়ে খারাপে ভাগ প্রায় 28 = 256, ১৬ গুণ। প্রতি সেকেন্ডে 109 ভাগ ধরলে ২৫৬ ন্যানোসেকেন্ড।
  3. ৩২ bit. 216 = 65,536 ভাগ, প্রায় ৬৫ মাইক্রোসেকেন্ড। Input আবার দ্বিগুণ, কাজ আবার বর্গ।
  4. ৬৪ bit. 232 ≈ 4.29 × 109 ভাগ, প্রায় ৪ সেকেন্ড। একটি সাধারণ 64-bit পূর্ণসংখ্যা, যা কম্পিউটারের একটি register-এ ধরে।
  5. ১২৮ bit. 264 ≈ 1.84 × 1019 ভাগ: প্রায় ৫৮৫ বছর। Input মাত্র ১২৮ অক্ষর লম্বা!
  6. ২৫৬ bit. প্রায় 1.08 × 1022 বছর, মহাবিশ্বের আনুমানিক বয়সের (প্রায় 1.4 × 1010 বছর) বহু গুণ। অর্থাৎ সময় ≈ 2b/2, input-এর দৈর্ঘ্যের exponential, যদিও “√N” দেখতে নিরীহ।

সমাধান দুই হাজার বছরেরও বেশি পুরোনো: Euclid-এর algorithm, gcd(x, y) = gcd(y, x mod y), যতক্ষণ না y = 0.

উপপাদ্য ৬.২

RELPRIME ∈ P. আরও নির্দিষ্টভাবে, Euclid-এর algorithm O(n) সংখ্যক mod operation করে, যেখানে n হলো ⟨x, y⟩-এর bit-দৈর্ঘ্য।

প্রমাণ। ধরুন x ≥ y (নইলে প্রথম ধাপেই দুটি অদলবদল হয়)।

  1. Lemma: x ≥ y > 0 হলে x mod y < x/2. কারণ, y ≤ x/2 হলে x mod y < y ≤ x/2; আর y > x/2 হলে x mod y = x − y < x/2. — দুই ক্ষেত্রে ভাগ
  2. দুই ধাপে জোড়াটি (x, y) → (y, x mod y) → (x mod y, ·); অর্থাৎ প্রতি দুই ধাপে প্রথম সংখ্যা অর্ধেকের কম হয়। — Lemma
  3. তাই ধাপসংখ্যা বড়জোর 2 log2 x + O(1) = O(n). — x-এর bit-সংখ্যা ≤ n
  4. প্রতিটি mod operation n-bit সংখ্যায় স্কুলের ভাগের নিয়মে O(n2) bit-ধাপ। মোট O(n3), polynomial; শেষে gcd = 1 কি না দেখে accept বা reject. ∎
import random
def euclid(x, y):                     # returns gcd and number of mod steps
    steps = 0
    while y: x, y = y, x % y; steps += 1
    return x, steps
def naive_relprime(x, y):             # try every d = 2 .. min(x, y)
    for d in range(2, min(x, y) + 1):
        if x % d == 0 and y % d == 0: return False, d - 1
    return True, min(x, y) - 1
print(euclid(864, 210), naive_relprime(864, 210), naive_relprime(899, 493))
fib = [1, 2]                          # consecutive Fibonacci = Euclid's worst case
while fib[-1] < 2**256: fib.append(fib[-1] + fib[-2])
print(" bits  Euclid steps  naive trials (= min - 1)")
for b in (8, 16, 32, 64, 128, 256):
    x, y = max((p for p in zip(fib[1:], fib) if p[0] < 2**b))
    print(f"{b:5} {euclid(x, y)[1]:9}      {y - 1:.3e}")
r = naive_relprime(131071, 100003)
print("naive on (131071, 100003):", r[0], f"{r[1]:,} trials")
random.seed(57)
ok = all(euclid(x, y)[1] <= 2 * y.bit_length() + 1 for x, y in
         ((random.getrandbits(64) | 1, random.getrandbits(60) | 1)
          for _ in range(10000)))
print("10000 random pairs: steps <= 2*bits(y)+1:", ok)

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

(6, 4) (False, 1) (False, 28)
 bits  Euclid steps  naive trials (= min - 1)
    8        11      1.430e+02
   16        22      2.866e+04
   32        45      1.836e+09
   64        91      7.540e+18
  128       184      2.057e+38
  256       368      5.847e+76
naive on (131071, 100003): True 100,002 trials
10000 random pairs: steps <= 2*bits(y)+1: True

প্রথম লাইন: gcd(864, 210) = 6, Euclid-এর ৪ ধাপে; সরল পদ্ধতি d = 2-তেই (১টি চেষ্টায়) সাধারণ ভাজক পায়। কিন্তু 899 = 29 × 31 আর 493 = 17 × 29-এ সাধারণ ভাজক 29 পেতে ২৮টি চেষ্টা লাগে। সারণিতে পরপর দুটি Fibonacci সংখ্যা নেওয়া হয়েছে, যা Euclid-এর জন্য সবচেয়ে খারাপ (Lamé ১৮৪৪ সালে এটি দেখান বলে পরিচিত)। তবু ২৫৬ bit-এ মাত্র ৩৬৮ ধাপ: ধাপসংখ্যা bit-সংখ্যার প্রায় ১.৪৪ গুণ, রৈখিক। একই জোড়ায় সরল পদ্ধতির লাগত প্রায় 5.8 × 1076 চেষ্টা; সেটি চালানো হয়নি, শুধু গোনা হয়েছে (সহমৌলিক জোড়ায় চেষ্টা = min − 1). ১৭ bit-এর একটি সহমৌলিক জোড়ায় সরল পদ্ধতি সত্যিই চালানো হয়েছে: ১,০০,০০২টি চেষ্টা। শেষ লাইন ১০,০০০টি এলোমেলো জোড়ায় প্রমাণের সীমাটি মিলিয়েছে।

৬.৩ প্রতিটি context-free language P-তে

পর্ব ৩১-এ CYK algorithm দেখেছেন: Chomsky normal form-এর grammar G আর দৈর্ঘ্য n-এর w নিয়ে, w-এর প্রতিটি টুকরো কোন variable থেকে আসে, তা ছোট থেকে বড় টুকরোর ক্রমে একটি টেবিলে ভরা। টুকরো O(n2)টি, প্রতিটির ভাঙনের বিন্দু O(n)টি, প্রতিটি ভাঙনে grammar-এর নিয়মগুলো দেখা।

উপপাদ্য ৬.৩

প্রতিটি context-free language L-এর জন্য L ∈ P. নির্দিষ্টভাবে, L-এর CNF grammar G স্থির রাখলে CYK O(n3) সময়ে membership ঠিক করে।

প্রমাণের রূপরেখা। L-এর একটি CNF grammar G আগে থেকে ঠিক করা (L স্থির, তাই G-এর আকার একটি ধ্রুবক)। CYK টেবিলের O(n2) ঘরের প্রতিটিতে O(n) ভাঙন × |R| নিয়ম = O(n) কাজ। মোট O(n3). সঠিকতা পর্ব ৩১-এ প্রমাণিত। ∎ লক্ষ করুন, G-কে input-এর অংশ ধরলেও, অর্থাৎ ACFG = {⟨G, w⟩ : G w-কে generate করে}-এর জন্যও, algorithm polynomial থাকে: CNF-এ রূপান্তর G-এর আকারের polynomial (সাবধানী রূপান্তরে), আর CYK O(n3 · |G|).

এর মানে, আপনার বাজারঘরের অর্ডার-কোয়েরি ভাষা context-free হলে তার parsing polynomial সময়ে সম্ভব, grammar যত জটিলই হোক। বাস্তবে LL আর LR parser (পর্ব ৩৮–৩৯) বিশেষ grammar-এ O(n) সময়ে কাজ করে।

৬.৪ PRIMES

PRIMES = {⟨N⟩ : N মৌলিক}. অংশ ৬.২-এর stepper দেখিয়েছে, trial division exponential. বহু দশক ধরে দ্রুত randomized পরীক্ষা জানা ছিল (Miller ১৯৭৬, Rabin ১৯৮০; পর্ব ৬৯), কিন্তু deterministic polynomial algorithm জানা ছিল না। ২০০২ সালে IIT Kanpur-এর Manindra Agrawal, Neeraj Kayal আর Nitin Saxena “PRIMES is in P” প্রবন্ধে একটি deterministic polynomial algorithm দেন (প্রকাশ Annals of Mathematics, ২০০৪)। এর সময় মূল প্রবন্ধে মোটামুটি (log N)12-এর ক্রমে, পরে Lenstra আর Pomerance প্রায় (log N)6-এ নামান বলে পরিচিত। উপপাদ্য: PRIMES ∈ P (প্রমাণ এখানে বাদ; আগ্রহী পাঠক AKS-এর মূল প্রবন্ধ দেখুন)। একটি সূক্ষ্ম কথা: মৌলিকতা পরীক্ষা P-তে, কিন্তু একটি যৌগিক সংখ্যার গুণনীয়ক খুঁজে বের করা polynomial সময়ে যায় কি না, তা অজানা; RSA-র নিরাপত্তা এই অজানার ওপর দাঁড়িয়ে (পর্ব ৭৬)।

৭ · Encoding-এর ফাঁদ — unary, binary আর pseudo-polynomial

বাজারঘরের গুদামে একটি প্রশ্ন: “n-টি পার্সেলের ওজন w1, …, wn গ্রাম। কিছু পার্সেল বেছে ঠিক T গ্রাম করা যায় কি, যাতে একটি ভ্যান পুরো ভরে?” এটি SUBSET-SUM. DSA কোর্সের পর্ব ৫৩-এর ধাঁচের একটি dynamic programming জানা: can[s] = “কোনো উপসেটের যোগফল s”, প্রতিটি পার্সেলের জন্য s = T থেকে নিচে হালনাগাদ। টেবিলে n · (T + 1)টি ঘর, সময় O(n · T). দেখতে polynomial. কিন্তু input-এ T লেখা হয় binary-তে, log2 T bit-এ। T-এর মান তার bit-সংখ্যার exponential, তাই O(n · T) input-দৈর্ঘ্যের polynomial নয়। এমন সময়কে বলে pseudo-polynomial.

import random
def subset_sum_dp(ws, T):             # classic table: cells = n * (T + 1)
    can = [True] + [False] * T        # can[s]: some subset sums to s
    for w in ws:
        for s in range(T, w - 1, -1):
            can[s] = can[s] or can[s - w]
    return can[T], len(ws) * (T + 1)
print(subset_sum_dp([3, 5, 9, 14], 17), subset_sum_dp([3, 5, 9, 14], 13))
random.seed(57)
print("bits  binary len  unary len   DP cells   cells/binary  cells/unary")
for b in (4, 8, 12, 16):          # 6 parcel weights of b bits each
    ws = [random.randrange(2**(b - 1), 2**b) for _ in range(6)]
    T = sum(ws) // 2
    ok, cells = subset_sum_dp(ws, T)
    blen = sum(w.bit_length() for w in ws) + T.bit_length()
    ulen = sum(ws) + T
    print(f"{b:4} {blen:9} {ulen:12,} {cells:11,} {cells/blen:12,.0f}"
          f" {cells/ulen:9.2f}")

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

(True, 72) (False, 56)
bits  binary len  unary len   DP cells   cells/binary  cells/unary
   4        30          102         210            7      2.06
   8        58        1,786       3,576           62      2.00
  12        86       29,266      58,536          681      2.00
  16       114      434,500     869,004        7,623      2.00

প্রথম লাইন: ওজন {3, 5, 9, 14}-এ 17 সম্ভব (3 + 14), 13 সম্ভব নয়; টেবিলে যথাক্রমে ৭২ আর ৫৬টি ঘর। সারণিতে ছয়টি পার্সেল, প্রতিটির ওজন b bit. Binary input-এর দৈর্ঘ্য প্রায় রৈখিকভাবে বাড়ে (৩০ থেকে ১১৪), কিন্তু DP-র ঘর বাড়ে প্রায় ষোলো গুণ করে প্রতি ৪ bit-এ: ঘর/binary দৈর্ঘ্য 7 থেকে 7,623, থামার লক্ষণ নেই। অন্যদিকে ঘর/unary দৈর্ঘ্য স্থির 2.00. অর্থাৎ ওজনগুলো unary-তে (প্রতি গ্রামে একটি 1) লিখলে একই algorithm রৈখিক, আর binary-তে লিখলে exponential. Algorithm বদলায়নি, বদলেছে input-এর দৈর্ঘ্যের মাপ।

ফাঁদটি কোথায়: “O(n · T), তাই polynomial, তাই SUBSET-SUM ∈ P, তাই P = NP” — এই যুক্তি অনলাইনে মাঝে মাঝে দেখা যায়। ভুলটি প্রথম ধাপেই: T input-এর দৈর্ঘ্য নয়। SUBSET-SUM NP-complete (পর্ব ৬১), আর এর কোনো সত্যিকারের polynomial algorithm জানা নেই। উল্টো দিকে, সংখ্যাগুলো ছোট (input-দৈর্ঘ্যের polynomial) হলে DP সত্যিই polynomial; বাস্তবে গ্রামের বদলে কেজিতে ওজন মাপলে T ছোট হয় আর DP দ্রুত চলে। এই পার্থক্য থেকেই পর্ব ৬১-এর “strong” আর “weak” NP-completeness-এর ধারণা।

সাধারণ নিয়ম: সংখ্যাযুক্ত সমস্যায় সবসময় জিজ্ঞাসা করুন, “আমার সময়-সীমায় সংখ্যার মান আছে, নাকি তার bit-সংখ্যা?” মান থাকলে algorithm সম্ভবত pseudo-polynomial. Euclid পরীক্ষায় পাশ করে (ধাপ ∝ bit), trial division ফেল করে (ধাপ ∝ √মান)।

৮ · EXP আর P ⊊ EXP — বড় ছবিটি

অনেক সমস্যার একটি স্বাভাবিক brute-force algorithm আছে: সব সম্ভাব্য উত্তর একটি একটি করে পরীক্ষা। Boolean formula-র সব 2m মান-নির্ধারণ, graph-এর সব vertex-ক্রম, পার্সেলের সব 2n উপসেট। এগুলো exponential সময়ে চলে।

সংজ্ঞা ৮.১ (EXP)

EXP = ⋃k ≥ 1 TIME(2nk)

P ⊆ EXP সরাসরি, কারণ nk ≤ 2n (বড় n-এ)। আসল প্রশ্ন: সমতা কি সম্ভব? উত্তর না, আর এটি প্রমাণিত। Time hierarchy theorem (Hartmanis আর Stearns, ১৯৬৫; পরে শক্ত রূপ) বলে: f যদি time-constructible হয় (অর্থাৎ f(n) একটি যন্ত্র O(f(n)) সময়ে লিখতে পারে; nk, 2n-এর মতো স্বাভাবিক সব function), তাহলে এমন একটি language আছে, যা O(f(n)) সময়ে decide হয় কিন্তু o(f(n)/log f(n)) সময়ে হয় না। প্রমাণ diagonalization দিয়ে, পর্ব ৫১-এর মতো, আর পূর্ণ প্রমাণ পর্ব ৬৭-এ।

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

P ⊊ EXP.

প্রমাণের রূপরেখা। প্রতিটি k-এর জন্য nk = o(2n/n), তাই P ⊆ TIME(2n). Hierarchy theorem f(n) = 22n নিয়ে দেয় TIME(2n) ⊊ TIME(22n) ⊆ EXP, কারণ 2n = o(22n/2n). তাই P ⊆ TIME(2n) ⊊ EXP. ∎

P, NP আর EXP — কী প্রমাণিত, কী অজানা

কঠিন রেখা মানে প্রমাণিত সম্পর্ক, ড্যাশ রেখা মানে সীমানা কোথায়, তা অজানা।

Class map: P inside NP inside EXP EXP NP P PATH, RELPRIME A_CFG, PRIMES {0^k 1^k} SAT HAMPATH প্রমাণিত P-তে P-তে কি না অজানা P ≠ EXP: প্রমাণিত P = NP? NP = EXP? অজানা
ছবি ৫৭.২ — P ⊆ NP ⊆ EXP (দ্বিতীয় অন্তর্ভুক্তি পর্ব ৫৮-এ প্রমাণিত হবে)। দুটি ধাপের অন্তত একটিতে অন্তর্ভুক্তি কঠোর, কারণ P ≠ EXP; কিন্তু কোনটিতে, তা কেউ জানে না। বেশিরভাগ গবেষক মনে করেন দুটিতেই কঠোর, কিন্তু প্রমাণিত নয়।

এই ছবির একটি কৌতূহলী দিক: P ⊊ EXP জানি, তাই অন্তত একটি সমস্যা EXP-তে আছে কিন্তু P-তে নেই। কিন্তু SAT, HAMPATH বা SUBSET-SUM-এর মতো পরিচিত সমস্যার কোনোটি সম্পর্কে এমন কথা প্রমাণিত নয়। এগুলোর জন্য আমরা শুধু জানি “brute force EXP-এ রাখে, polynomial algorithm জানা নেই”। পরের পর্বে এদের শ্রেণি NP-এর সংজ্ঞা আসবে।

আরও গভীরে: Hartmanis আর Stearns-এর linear speedup theorem বলে, multi-tape যন্ত্রে running time-কে যেকোনো স্থির গুণকে কমানো যায় (n-এর চেয়ে দ্রুত বাড়া সময়ের জন্য), তাই O-তে গুণক বাদ দেওয়া শুধু সুবিধার জন্য নয়, তত্ত্বেও যুক্তিসংগত। এক-tape যন্ত্রে palindrome-এর জন্য Ω(n2) নিম্নসীমা প্রমাণিত (Hennie ১৯৬৫ বলে পরিচিত), যা crossing sequence নামের একটি কৌশলে আসে; বহু-tape-এ সেটিই O(n). কিন্তু SAT-এর মতো “স্বাভাবিক” সমস্যার জন্য সাধারণ যন্ত্রে প্রমাণিত সময়-নিম্নসীমাগুলো খুবই দুর্বল, polynomial-এর ধারেকাছেও নয়; P ≠ NP তাই এখনো অপ্রমাণিত।

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

  • Class P-এর সংজ্ঞা দিন; কেন polynomial? P = ⋃k TIME(nk); model-নিরপেক্ষতা, composition-এ বদ্ধতা, বাস্তবের সঙ্গে মিল।
  • {0k1k}-এর জন্য O(n log n) এক-tape TM দিন। জোড়-বিজোড় পরীক্ষা আর একটি বাদে একটি কাটা; log n দফা, প্রতিটি O(n).
  • RELPRIME ∈ P প্রমাণ করুন। Euclid; দুই ধাপে প্রথম সংখ্যা অর্ধেক, তাই ধাপ O(bit-সংখ্যা)।
  • Subset-sum DP O(nT) কেন polynomial নয়? T binary-তে log T bit, তাই T input-দৈর্ঘ্যের exponential; pseudo-polynomial.
  • P আর EXP-এর সম্পর্ক কী? P ⊊ EXP, time hierarchy theorem দিয়ে প্রমাণিত; P বনাম NP খোলা।

৯ · AI-এর যুগে time complexity

AI assistant-কে কোনো algorithm-এর complexity জিজ্ঞাসা করলে উত্তর প্রায় সবসময় আত্মবিশ্বাসী। কিন্তু এই বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়, বিশেষ করে সংখ্যাযুক্ত সমস্যায় আর P বনাম NP-এর প্রশ্নে।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“O(√N) trial division polynomial” বা “subset-sum DP O(nT), তাই polynomial”input-এর দৈর্ঘ্য bit-এ মাপুন; সময়-সীমায় সংখ্যার মান থাকলে pseudo-polynomial
এক-tape আর বহু-tape-এর সময় গুলিয়ে ফেলা, যেমন “এক-tape TM-এ {0k1k} O(n)”Model জিজ্ঞাসা করুন; এক-tape-এ o(n log n)-এ শুধু regular language
Best case বা average case-কে running time বলাসংজ্ঞা ১.১: দৈর্ঘ্য n-এর সব input-এ সর্বোচ্চ
“P = NP প্রমাণিত” বা “P ≠ NP প্রমাণিত”, অথবা “P ≠ EXP অজানা”P ⊊ EXP প্রমাণিত; P বনাম NP খোলা। দাবির উৎস চান
Hierarchy theorem-এর শর্ত (time-constructible) বাদ দেওয়াউপপাদ্যের সব শর্ত Sipser বা Arora–Barak-এ মিলিয়ে নিন
বানানো সাল বা রেফারেন্স (AKS, Cobham, Hartmanis–Stearns)মূল প্রবন্ধের নাম আর সাল নিজে খুঁজে দেখুন

AI-কে কাজে লাগানোর ভালো উপায়: algorithm-এর সঙ্গে input-এর encoding আর দৈর্ঘ্যের সংজ্ঞা চাওয়া, প্রতিটি ধাপের সময়ের যুক্তি চাওয়া, আর একটি ধাপ-গণনার code চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্ব শিখছি। Σ = {0, 1, 2}-এর ওপর L = {0^k 1^k 2^k : k ≥ 0} নিয়ে প্রশ্ন। ১. একটি এক-tape deterministic Turing machine-এর high-level বর্ণনা দাও, যা L-কে O(n log n) সময়ে decide করে, আর প্রতিটি ধাপের সময়ের যুক্তি দাও। ২. একটি দুই-tape যন্ত্রের বর্ণনা দাও, যা O(n) সময়ে decide করে। tape ২-এর বাঁ প্রান্ত কীভাবে চেনা যাবে, তা স্পষ্ট বলো। ৩. "running time"-এর সংজ্ঞা দাও: worst case, input-এর দৈর্ঘ্যের function. ৪. শুধু standard library দিয়ে একটি Python script দাও, যা দুটি যন্ত্রের ধাপ গোনে, দৈর্ঘ্য 12 পর্যন্ত সব string-এ L-এর সংজ্ঞার সঙ্গে মেলায়, আর বড় n-এ steps/(n log n) ও steps/n ছাপে। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১n100 সময়ের algorithm-কে “দক্ষ” আর 1.0001n সময়ের algorithm-কে “অদক্ষ” বলা কি যুক্তিসংগত? Cobham–Edmonds thesis-এর পক্ষে আর বিপক্ষে কী প্রমাণ আছে?

আক্ষরিক অর্থে না। n = 1000-এ n100 হলো 10300 ধাপ, অসাধ্য; আর 1.00011000 প্রায় 1.1, নগণ্য। তবু তত্ত্ববিদরা polynomial-কে দক্ষতার সংজ্ঞা হিসেবে রেখেছেন, কারণ সংজ্ঞাটি একক উদাহরণের জন্য নয়, একটি শ্রেণি-র জন্য, আর শ্রেণি হিসেবে এটি অসাধারণ ভালো কাজ করে।

পক্ষের প্রথম প্রমাণ অভিজ্ঞতা। একটি স্বাভাবিক সমস্যা একবার P-তে প্রমাণিত হলে তার ঘাত প্রায় সবসময় ছোট হয়ে আসে। PRIMES-এর AKS algorithm মূলত মোটামুটি (log N)12-এর ক্রমে ছিল; কয়েক বছরের মধ্যে সেটি প্রায় (log N)6-এ নেমেছে বলে পরিচিত। Linear programming-এর গল্প আরও শিক্ষণীয়। Dantzig-এর simplex পদ্ধতি (১৯৪৭) বাস্তবে দ্রুত, কিন্তু Klee আর Minty ১৯৭২ সালে দেখান, কিছু কৃত্রিম input-এ এটি exponential সময় নেয়। ১৯৭৯ সালে Khachiyan-এর ellipsoid পদ্ধতি LP-কে P-তে আনে; বাস্তবে এটি ধীর ছিল, কিন্তু ১৯৮৪ সালে Karmarkar-এর interior-point পদ্ধতি তত্ত্বে polynomial আর বাস্তবেও প্রতিযোগিতামূলক হয়। অর্থাৎ “P-তে আছে” প্রমাণ প্রায়ই পরে বাস্তবের দ্রুত algorithm-এর পথ খোলে।

দ্বিতীয় প্রমাণ গাণিতিক সৌন্দর্য। Polynomial-এর শ্রেণি যোগ, গুণ আর composition-এ বদ্ধ, আর সব যুক্তিসংগত deterministic model-এ একই। n2 বা n log n-এর মতো সূক্ষ্ম শ্রেণি model বদলালে বদলে যায়, অংশ ৩-এর মতো। একটি গাণিতিক তত্ত্বের জন্য স্থিতিশীল সংজ্ঞা অপরিহার্য।

বিপক্ষের যুক্তিও গুরুতর। SAT NP-complete, অথচ আধুনিক SAT solver বাস্তবের লক্ষ লক্ষ চলকের formula প্রায়ই সমাধান করে (পর্ব ৭৩)। আবার বিশাল data-র যুগে n2-ও প্রায়ই অচল; তাই fine-grained complexity (পর্ব ৭২) polynomial-এর ভেতরের সূক্ষ্ম পার্থক্য নিয়ে কাজ করে। আর worst case-এর বদলে input-এর গঠন বা গড় দেখলে ছবি বদলায়।

মূল উপলব্ধি: Polynomial = দক্ষ একটি কাজের সংজ্ঞা, প্রকৃতির নিয়ম নয়; এর জোর হলো model-নিরপেক্ষতা আর অভিজ্ঞতায় দেখা ঘাত কমে আসার প্রবণতা, আর এর সীমা হলো বড় ঘাত, বড় ধ্রুবক আর worst case-এর হতাশাবাদ।

প্র ০২{0k1k} এক-tape যন্ত্রে n log n, দুই-tape যন্ত্রে n. তাহলে কোন সংখ্যাটি “আসল” সময়? Complexity তত্ত্ব model-এর এই নির্ভরতার সঙ্গে কীভাবে মানিয়ে নেয়, আর extended Church–Turing thesis এখানে কী বলে?

কোনোটিই একমাত্র “আসল” নয়। সময় সবসময় একটি model-এর সাপেক্ষে। এক-tape যন্ত্রের head-কে tape-এর এক প্রান্ত থেকে অন্য প্রান্তে বারবার হাঁটতে হয়, আর এই হাঁটাই n log n-এর উৎস। দুই tape থাকলে একটি tape খাতা হিসেবে কাজ করে, হাঁটা লাগে না। সাধারণ কম্পিউটার আরও শক্তিশালী: memory-র যেকোনো ঘরে এক ধাপে পৌঁছায় (RAM). বাস্তব programmer-এর কাছে RAM-এর হিসাবই সবচেয়ে কাছের, তাই DSA কোর্সে সময় সেভাবে গোনা হয়।

Complexity তত্ত্ব দুই স্তরে মানিয়ে নেয়। সূক্ষ্ম স্তরে (n বনাম n log n বনাম n2) model স্পষ্ট বলে নিতে হয়; fine-grained complexity আর data structure-এর lower bound-এ এই সতর্কতা অপরিহার্য। মোটা দাগের স্তরে (polynomial বনাম exponential) model প্রায় অপ্রাসঙ্গিক, কারণ সব যুক্তিসংগত deterministic model পরস্পরকে polynomial দামে অনুকরণ করে। P, EXP-এর মতো শ্রেণি এই কারণেই সংজ্ঞায়িত হয়। Hartmanis আর Stearns ১৯৬৫ সালে multi-tape যন্ত্র দিয়েই সময় মাপা শুরু করেন, আর এক-tape ও বহু-tape-এর বর্গ-সম্পর্কও সেই যুগের ফল।

Extended (strong) Church–Turing thesis এই পর্যবেক্ষণকে একটি দাবিতে রূপ দেয়: যেকোনো বাস্তবে গড়া যায় এমন গণনা-যন্ত্র একটি (probabilistic) Turing machine দিয়ে polynomial বাড়তি সময়ে অনুকরণ করা যায় (পর্ব ৪৭)। এটি সত্য হলে P-এর মতো শ্রেণি শুধু গাণিতিক নয়, ভৌত জগতের “দক্ষ গণনা”-রও সঠিক মাপ। কিন্তু quantum computer এই thesis-কে চ্যালেঞ্জ করে: Shor ১৯৯৪ সালে দেখান, quantum যন্ত্রে গুণনীয়ক খোঁজা polynomial সময়ে সম্ভব, অথচ সাধারণ যন্ত্রে এমন algorithm জানা নেই। তবে গুণনীয়ক খোঁজা P-তে নেই, তা প্রমাণিত নয়; তাই thesis ভুল প্রমাণিত হয়েছে, এ কথা বলা যায় না (পর্ব ৭৫)।

মূল উপলব্ধি: সূক্ষ্ম সময় model-নির্ভর, তাই model বলে নিতে হয়; polynomial-এর মোটা দাগ model-নিরপেক্ষ, আর extended Church–Turing thesis দাবি করে এটি ভৌত জগতেও সত্য, যা quantum computing-এর কারণে অমীমাংসিত।

প্র ০৩সংখ্যা unary-তে লিখলে subset-sum polynomial হয়ে যায়। তাহলে কি encoding বদলে কঠিন সমস্যা সহজ করা যায়? “যুক্তিসংগত encoding”-এর শর্ত কেন দরকার, আর strong NP-completeness ধারণাটি কোথা থেকে আসে?

Unary-তে লিখলে সমস্যা সহজ হয় না; input কৃত্রিমভাবে লম্বা হয়। 64-bit একটি ওজন unary-তে লিখতে প্রায় 1.8 × 1019টি চিহ্ন লাগে। Algorithm-এর মোট কাজ একই থাকে, শুধু আমরা তাকে একটি বিশাল n দিয়ে ভাগ করে “polynomial” দেখাই। এটি একটি হিসাবের কৌশল, কোনো দ্রুতি নয়। কল্পনা করুন বাজারঘরের সার্ভার প্রতিটি অর্ডার-মূল্য টাকার বদলে “প্রতি টাকায় একটি তারা” দিয়ে পাঠায়: ১০,০০০ টাকার অর্ডার পাঠাতে দশ হাজার অক্ষর। কেউ এমন নকশা করবে না।

এই কারণে পর্ব ০৫-এ “যুক্তিসংগত encoding”-এর শর্ত দেওয়া হয়েছিল: encoding injective, polynomial সময়ে লেখা-পড়া যায়, আর অকারণে লম্বা নয়। যেকোনো দুটি যুক্তিসংগত encoding-এর দৈর্ঘ্য পরস্পরের polynomial (binary বনাম দশমিক: ধ্রুবক গুণ; adjacency matrix বনাম list: বড়জোর বর্গ), তাই P-তে থাকা না থাকা বদলায় না। Unary এই শর্ত ভাঙে, কারণ binary-র তুলনায় এর দৈর্ঘ্য exponential.

তবু unary-র প্রশ্নটি তত্ত্বে একটি গুরুত্বপূর্ণ পার্থক্য ধরিয়ে দেয়। কিছু NP-complete সমস্যা, যেমন SUBSET-SUM আর knapsack, সংখ্যাগুলো ছোট হলে (মান input-দৈর্ঘ্যের polynomial) সহজ, কারণ pseudo-polynomial DP তখন সত্যিকারের polynomial. Garey আর Johnson ১৯৭০-এর দশকে এদের “weakly” NP-complete বলেন। অন্যদিকে 3-PARTITION বা TSP-র মতো কিছু সমস্যা সংখ্যা ছোট হলেও NP-complete থাকে; এরা “strongly” NP-complete, আর P ≠ NP হলে এদের pseudo-polynomial algorithm-ও থাকতে পারে না (পর্ব ৬১)।

বাস্তবে এর অর্থ পরিষ্কার: ওজন গ্রামের বদলে ১০০ গ্রামের একক গুনলে T একশো ভাগ ছোট হয়, DP একশো গুণ দ্রুত চলে, বিনিময়ে উত্তর সামান্য অনির্দিষ্ট হয়। এই “সংখ্যা গোল করা” কৌশলই knapsack-এর approximation scheme-এর মূল ধারণা (পর্ব ৭১)।

মূল উপলব্ধি: Encoding বদলে কাজ কমে না, শুধু মাপকাঠি বদলায়; যুক্তিসংগত encoding-এর শর্ত এই প্রতারণা আটকায়, আর unary-তে সহজ হওয়া না হওয়া থেকে weak আর strong NP-completeness-এর গুরুত্বপূর্ণ পার্থক্য আসে।

প্র ০৪মৌলিকতা পরীক্ষা P-তে, কিন্তু গুণনীয়ক খোঁজা P-তে কি না অজানা। একই সংখ্যা নিয়ে দুটি প্রশ্নের এত পার্থক্য কেন, আর বাস্তবের software এখনো randomized পরীক্ষা কেন ব্যবহার করে?

দুটি প্রশ্ন আলাদা জিনিস চায়। “N কি মৌলিক?” প্রশ্নের উত্তর এক bit. “N-এর একটি গুণনীয়ক দাও” প্রশ্নের উত্তর একটি সংখ্যা। আশ্চর্যের ব্যাপার, গুণনীয়ক না জেনেও “N যৌগিক” প্রমাণ করা যায়। Fermat-এর ছোট উপপাদ্য বলে, N মৌলিক হলে প্রতিটি a-এর জন্য aN−1 ≡ 1 (mod N). কোনো a এই শর্ত ভাঙলে N নিশ্চিত যৌগিক, অথচ তার গুণনীয়ক কী, তা জানা যায় না। Miller–Rabin পরীক্ষা এই ধারণাকে শক্ত করে: একটি এলোমেলো a বেছে একটি শক্ত শর্ত পরীক্ষা করে, আর যৌগিক N-এ প্রতিটি চেষ্টায় ভুলের সম্ভাবনা বড়জোর ১/৪। Gary Miller ১৯৭৬ সালে deterministic রূপটি দেন, যা Riemann hypothesis-এর একটি সাধারণ রূপ সত্য ধরে নেয়; Michael Rabin ১৯৮০ সালে এলোমেলো রূপটি দেন।

২০০২ সালে Agrawal, Kayal আর Saxena প্রথমবারের মতো কোনো অপ্রমাণিত অনুমান ছাড়া deterministic polynomial পরীক্ষা দেন। প্রবন্ধটি বিশেষ আলোচিত হয় এর সরলতার জন্য, আর দুই লেখক তখন স্নাতক পর্যায়ের ছাত্র ছিলেন বলে পরিচিত। মূল ধারণা: N মৌলিক হলে একটি polynomial অভেদ (x + a)N ≡ xN + a (mod N) সত্য, আর এই অভেদ একটি ছোট polynomial-এর modulo-তে কয়েকটি a-এর জন্য পরীক্ষা করাই যথেষ্ট।

তবু বাস্তবের cryptography library মৌলিক সংখ্যা বানাতে সাধারণত Miller–Rabin-ধরনের পরীক্ষা ব্যবহার করে। কারণ এটি অনেক দ্রুত, আর কয়েক ডজন চেষ্টার পরে ভুলের সম্ভাবনা হার্ডওয়্যার-ত্রুটির সম্ভাবনার চেয়েও কম। AKS-এর গুরুত্ব তাত্ত্বিক: PRIMES নিশ্চিতভাবে P-তে।

গুণনীয়ক খোঁজার ক্ষেত্রে সেরা জানা সাধারণ algorithm-গুলো (যেমন number field sieve) bit-সংখ্যার sub-exponential, কিন্তু polynomial নয়। এটি NP-তে এমন একটি সমস্যা, যা NP-complete বলে মনে করা হয় না, আবার P-তেও আছে বলে জানা নেই (পর্ব ৬৩)। RSA-র নিরাপত্তা এই অজানার ওপর দাঁড়িয়ে।

মূল উপলব্ধি: “হ্যাঁ/না” প্রশ্ন সহজ হলেও সংশ্লিষ্ট খোঁজার প্রশ্ন কঠিন থাকতে পারে; PRIMES ∈ P একটি তাত্ত্বিক মাইলফলক, আর বাস্তবে দ্রুত randomized পরীক্ষা আর গুণনীয়ক খোঁজার কাঠিন্য পাশাপাশি সহাবস্থান করে।

প্র ০৫P ⊊ EXP প্রমাণিত, অথচ P ≠ NP প্রমাণ হয়নি। কোনো নির্দিষ্ট পরিচিত সমস্যা, যেমন SAT, P-তে নেই, তা প্রমাণ করা এত কঠিন কেন? Complexity তত্ত্বের জন্মের গল্প এখানে কী বলে?

P ⊊ EXP-এর প্রমাণ diagonalization: এমন একটি language বানানো হয়, যা প্রতিটি polynomial-সময়ের যন্ত্রের সঙ্গে অন্তত একটি input-এ ইচ্ছাকৃতভাবে দ্বিমত করে। ভাষাটি কৃত্রিম, ঠিক halting problem-এর machine D-এর মতো (পর্ব ৫১)। এই কৌশল একটি শ্রেণির অস্তিত্বের কথা বলে, কিন্তু SAT-এর মতো স্বাভাবিক সমস্যাকে ছোঁয় না। তাই আমরা জানি, EXP-এ এমন সমস্যা আছে, যা P-তে নেই, আর কিছু স্বাভাবিক সমস্যা EXP-complete (যেমন n × n বোর্ডের সাধারণীকৃত দাবা, Fraenkel আর Lichtenstein ১৯৮১ সালে দেখান বলে পরিচিত), তাই সেগুলোও প্রমাণিতভাবে P-র বাইরে।

P ≠ NP প্রমাণে diagonalization একা যথেষ্ট নয়, এটি নিজেই প্রমাণিত। Baker, Gill আর Solovay ১৯৭৫ সালে দেখান, এমন “oracle” জগৎ আছে, যেখানে P = NP, আর এমন জগৎ-ও আছে যেখানে P ≠ NP (পর্ব ৬৮)। Diagonalization-এর প্রমাণ সব oracle জগতে সমানভাবে খাটে, তাই সেটি দিয়ে এই প্রশ্নের মীমাংসা হতে পারে না। পরে “natural proofs” (Razborov আর Rudich, ১৯৯৪) circuit-এর নিম্নসীমার আরেক ধরনের কৌশলের সীমা দেখায়।

ইতিহাসেও এই প্রশ্নের শিকড় পুরোনো। ১৯৫৬ সালে Kurt Gödel John von Neumann-কে একটি চিঠিতে জিজ্ঞাসা করেন, একটি গাণিতিক উক্তির n দৈর্ঘ্যের প্রমাণ আছে কি না, তা n বা n2-এর অনুপাতে সময়ে বের করা যায় কি না; চিঠিটি বহু পরে প্রকাশিত হয়ে আজ P বনাম NP-এর একটি আদি রূপ বলে পরিচিত। ১৯৬৫ সালে Hartmanis আর Stearns সময়কে একটি সম্পদ হিসেবে মাপার কাঠামো দেন, আর ১৯৭১–৭৩ সালে Cook আর Levin NP-completeness-এর ধারণা আনেন (পর্ব ৬০)।

আজকের অবস্থা: বেশিরভাগ গবেষক মনে করেন P ≠ NP, কিন্তু প্রমাণিত নয়। Clay Mathematics Institute এটিকে Millennium Prize সমস্যার তালিকায় রেখেছে। স্বাভাবিক সমস্যার নিম্নসীমা প্রমাণের জন্য সম্ভবত সম্পূর্ণ নতুন কৌশল লাগবে।

মূল উপলব্ধি: Diagonalization শ্রেণির মধ্যে কঠোর পার্থক্য প্রমাণ করে (P ⊊ EXP), কিন্তু নির্দিষ্ট স্বাভাবিক সমস্যার কাঠিন্য প্রমাণে এটি প্রমাণিতভাবে অপর্যাপ্ত; তাই P বনাম NP আজও খোলা।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। three_machines.py আর euclid_bits.py-তে নিজের input দিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: L = {0k1k2k : k ≥ 0}-এর জন্য একটি দুই-tape deterministic Turing machine-এর implementation-স্তরের বর্ণনা দিন, যা O(n) সময়ে L decide করে। Tape ২-এর বাঁ প্রান্তে head কীভাবে বুঝবে যে সে শেষ ঘরে? এক-tape যন্ত্রে L-এর জন্য কোন সময় আশা করবেন?

    Tape ২-এর প্রথম ঘরে একটি চিহ্ন $ লিখে শুরু করুন। (১) tape ১-এ 0 পড়তে পড়তে প্রতিটির জন্য tape ২-এ একটি 0 লিখে দুই head ডানে। (২) tape ২-এর head এক ঘর বাঁয়ে, শেষ 0-তে। (৩) tape ১-এ প্রতিটি 1-এর জন্য tape ২-এর head এক ঘর বাঁয়ে; tape ২-এ $ পৌঁছানোর ঠিক সময়ে 1 শেষ হতে হবে, নইলে reject. (৪) tape ২-এর head $ থেকে ডানে, tape ১-এর প্রতিটি 2-এর জন্য এক ঘর; tape ১-এ blank আর tape ২-এ blank একসঙ্গে এলে accept, অন্য যেকোনো অবস্থায় (যেমন 2-এর পরে 0 বা 1) reject. প্রতিটি ধাপে অন্তত tape ১-এর head এক ঘর এগোয় বা ধাপ ২-এর মতো একবার মাত্র ঘটে, তাই মোট n + O(1) ধাপ। $ ছাড়া কাজ হয় না, কারণ Sipser-এর রীতিতে প্রথম ঘরে L move head-কে জায়গায় রাখে, তাই head “বাঁয়ে বেরিয়ে যাওয়া” টের পায় না।

    এক-tape-এ M2-এর ধারণা তিনটি চিহ্নে খাটে (প্রতি দফায় তিনটি সংখ্যার জোড়-বিজোড় মেলানো আর প্রতিটির অর্ধেক কাটা), তাই O(n log n). L regular নয়, তাই o(n log n) সম্ভব নয়। Scratch-এ দুই-tape algorithm-টি দৈর্ঘ্য ১২ পর্যন্ত {0, 1, 2}-এর সব ৭,৯৭,১৬১টি string-এ L-এর সংজ্ঞার সঙ্গে মেলানো হয়েছে, আর ধাপ কখনো n + 2-এর বেশি হয়নি।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: COMPOSITES = {⟨N⟩ : N যৌগিক} P-তে, আর এর সরল algorithm-ই যথেষ্ট। প্রমাণ: d = 2 থেকে √N পর্যন্ত প্রতিটি d দিয়ে N ভাগ করে দেখি। ভাগ √N বার, প্রতিটি ভাগ polynomial. √N < N, আর N input, তাই সময় input-এর রৈখিকের চেয়েও কম। ∎” দাবিটি কি সত্য? প্রমাণে ভুল কোথায়?

    দাবির প্রথম অংশ সত্য: COMPOSITES ∈ P, কারণ PRIMES ∈ P (AKS) আর P complement-এ বদ্ধ (উপপাদ্য ৫.২)। কিন্তু প্রমাণটি ভুল, আর ভুলটি “N input, তাই সময় input-এর রৈখিকের চেয়ে কম” বাক্যে। Input N নয়, ⟨N⟩, অর্থাৎ N-এর binary রূপ, যার দৈর্ঘ্য n ≈ log2 N. তাই √N ≈ 2n/2, input-দৈর্ঘ্যের exponential. Trial division stepper ঠিক এটিই দেখায়: ১২৮ bit-এ প্রায় ৫৮৫ বছর।

    দ্বিতীয় সূক্ষ্ম ভুল: “প্রতিটি ভাগ polynomial” সত্য (n-bit ভাগ O(n2)), কিন্তু polynomial কাজ exponential বার করলে মোট exponential. সঠিক প্রমাণের জন্য AKS-এর মতো algorithm লাগে, যার ধাপসংখ্যা n-এর polynomial.

  3. Trace আর আগাম অনুমান: অংশ ৩-এর M1 আর M2 input 00000111-এ চালালে প্রতিটি কয়টি sweep-এর পরে থামে, আর কী উত্তর দেয়? M2-এর কোন ধাপে সিদ্ধান্ত হয়?

    M2: sweep ১-এ ক্রম ঠিক (আগে 0, পরে 1). Sweep ২: বাকি পাঁচটি 0 আর তিনটি 1, মোট ৮, জোড়। Sweep ৩: একটি বাদে একটি কাটা; পাঁচটি 0-এর তিনটি (১ম, ৩য়, ৫ম) কাটা পড়ে, দুটি বাকি; তিনটি 1-এর দুটি কাটা, একটি বাকি। Sweep ৪: মোট ২ + ১ = ৩, বিজোড়: reject. মোট ৪টি sweep, n = 8-এ 4 × 18 = 72 ধাপ। Binary-তে 5 = 101 আর 3 = 011; নিচ থেকে প্রথম অঙ্ক দুটিরই 1 (মোট জোড়), দ্বিতীয় অঙ্কে 0 বনাম 1 (মোট বিজোড়), সেখানেই ধরা পড়ে।

    M1: sweep ১ ক্রম পরীক্ষা, তারপর তিনটি sweep-এ তিন জোড়া কাটা; তখন 1 শেষ, লুপ থামে। Sweep ৫-এ দুটি 0 বাকি: reject. মোট ৫টি sweep, ৯০ ধাপ। three_machines.py-এর M1 আর M2-তে "00000111" দিলে ঠিক (False, 5) আর (False, 4) আসে।

  4. হিসাব: (ক) Euclid-এর algorithm (89, 55)-এ কয়টি mod ধাপ নেয়? (খ) নিচের প্রতিটি algorithm-এর সময় input-দৈর্ঘ্যের polynomial কি না বলুন: ১. m-vertex graph-এ সব vertex-ক্রম পরীক্ষা করে Hamiltonian পথ খোঁজা; ২. দুটি n-bit সংখ্যা স্কুলের নিয়মে গুণ করা; ৩. N-এর সব ভাজক 1 থেকে N পর্যন্ত গোনা; ৪. দৈর্ঘ্য n-এর string-এ একটি স্থির CFG-এর জন্য CYK.

    (ক) (89, 55) → (55, 34) → (34, 21) → (21, 13) → (13, 8) → (8, 5) → (5, 3) → (3, 2) → (2, 1) → (1, 0): ৯টি ধাপ, gcd = 1. পরপর Fibonacci সংখ্যা, তাই এই আকারের জন্য সবচেয়ে খারাপ; euclid_bits.py-তে euclid(89, 55) দিলে (1, 9) আসে।

    (খ) ১. না: m! ক্রম, আর input-দৈর্ঘ্য m-এর polynomial, তাই exponential. ২. হ্যাঁ: O(n2) bit-ধাপ। ৩. না: N ≈ 2n ধাপ, যেখানে n bit-সংখ্যা; pseudo-polynomial-এর মতো ফাঁদ। ৪. হ্যাঁ: O(n3), grammar স্থির বলে তার আকার ধ্রুবক।

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

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

ক্রম{0k1k}-এর জন্য O(n log n) সময়ের এক-tape যন্ত্র M2-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Tape পড়ে দেখা কোনো 1-এর ডানে 0 আছে কি না; থাকলে reject
  2. 0 আর 1 দুটোই বাকি থাকলে লুপ শুরু
  3. বাকি 0 আর 1-এর মোট সংখ্যা বিজোড় হলে reject
  4. প্রথম থেকে একটি বাদে একটি 0, তারপর একটি বাদে একটি 1 কাটা
  5. লুপ শেষে কোনো 0 বা 1 বাকি না থাকলে accept, নইলে reject

A = {0k1k : k ≥ 0} সম্পর্কে নিচের কোনটি সত্য?

  • এক-tape Turing machine-এ A-এর জন্য O(n2)-এর চেয়ে ভালো কিছু সম্ভব নয়
  • এক-tape Turing machine-এ A O(n) সময়ে decide করা যায়
  • এক-tape-এ O(n log n), দুই-tape-এ O(n) সময়ে A decide করা যায়
  • A regular নয়, তাই A P-তে নেই

একটি algorithm একটি ধনাত্মক পূর্ণসংখ্যা N (binary-তে দেওয়া) নিয়ে d = 2 থেকে ⌊√N⌋ পর্যন্ত প্রতিটি d দিয়ে ভাগ করে দেখে। Input-এর দৈর্ঘ্য n হলে এর সময় কেমন?

  • O(√n), তাই রৈখিকের চেয়েও দ্রুত
  • 2Θ(n)-এর ক্রমে (সবচেয়ে খারাপে), অর্থাৎ exponential
  • O(n2), কারণ প্রতিটি ভাগ O(n2)
  • সময় অসীম হতে পারে, কারণ N যেকোনো বড় হতে পারে

“P-এর সংজ্ঞা এক-tape বা বহু-tape Turing machine, যেটি দিয়েই করা হোক, একই শ্রেণি পাওয়া যায়।” এর কারণ কোনটি?

  • দুই ধরনের যন্ত্রে প্রতিটি language-এর সময় হুবহু সমান
  • দুই ধরনের যন্ত্র একই language decide করে, তাই সময়ের প্রশ্ন ওঠে না
  • NTM-কে DTM দিয়ে অনুকরণ করা যায়
  • বহু-tape যন্ত্রের t(n) ধাপকে এক-tape যন্ত্র O(t(n)2) ধাপে অনুকরণ করে, আর polynomial-এর বর্গও polynomial

Euclid-এর algorithm gcd(x, y) = gcd(y, x mod y) দুটি n-bit সংখ্যায় কতগুলো mod ধাপ নেয়?

  • O(n), কারণ প্রতি দুই ধাপে প্রথম সংখ্যা অর্ধেকের কম হয়
  • O(2n), কারণ সংখ্যার মান 2n পর্যন্ত
  • O(2n/2), trial division-এর মতো
  • O(n3) সংখ্যক mod ধাপ

n-টি ধনাত্মক পূর্ণসংখ্যা আর একটি লক্ষ্য T (সবই binary-তে) নিয়ে subset-sum-এর একটি DP O(n · T) সময়ে চলে। কোন মন্তব্যটি সঠিক?

  • এটি polynomial, তাই এটি P = NP প্রমাণ করে
  • DP ভুল উত্তর দিতে পারে, তাই এটি কাজের নয়
  • এটি pseudo-polynomial: T-এর মান binary দৈর্ঘ্যের exponential হতে পারে, তাই সাধারণভাবে polynomial নয়
  • সময় শুধু n-এর ওপর নির্ভর করে, T-এর ওপর নয়

P, NP আর EXP সম্পর্কে কোন বক্তব্যটি প্রমাণিত সত্য?

  • P ≠ NP
  • P ⊊ EXP
  • NP ⊊ EXP
  • P = EXP

শব্দকোষ

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

মনে রাখুন

  1. Running time = দৈর্ঘ্য n-এর সব input-এ decider-এর সর্বোচ্চ ধাপ; O, o দিয়ে বৃদ্ধির হার, গুণক বাদ।
  2. {0k1k}: এক-tape zig-zag O(n2), অর্ধেক কাটা O(n log n) (এক-tape-এ সর্বোত্তম), দুই-tape O(n). সময় model-নির্ভর।
  3. বহু-tape → এক-tape: t → O(t2), polynomial; NTM → DTM: t → 2O(t). তাই P = ⋃k TIME(nk) model-নিরপেক্ষ, composition আর union, complement, concatenation-এ বদ্ধ।
  4. P-তে: PATH (marking/BFS), RELPRIME (Euclid, O(bit) ধাপ), প্রতিটি CFL (CYK O(n3)), PRIMES (AKS ২০০২)। Input-এর দৈর্ঘ্য bit-এ মাপুন: trial division আর O(nT) DP polynomial নয়।
  5. EXP = ⋃k TIME(2nk); P ⊊ EXP প্রমাণিত (time hierarchy), P বনাম NP খোলা।

পরের পর্বে: NP: certificate আর verifier, “হ্যাঁ” উত্তরের ছোট প্রমাণ যা polynomial সময়ে যাচাই হয়, NTM-এর সংজ্ঞার সঙ্গে তার সমতা, আর P ⊆ NP ⊆ EXP-এর প্রমাণ।

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

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