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

Approximation algorithm আর inapproximability — PCP-র পরিচয়

Approximation Algorithms and Inapproximability — Ratios, Vertex Cover, Set Cover, TSP, Approximation Schemes, Gap Reductions and the PCP Theorem

Taught in Bangla, this lesson defines approximation ratios as proven guarantees and proves the matching 2-approximation for vertex cover, the H(d) bound for greedy set cover and the factor 2 for metric TSP, with Christofides at 1.5. It builds a knapsack FPTAS, maps FPTAS, PTAS and APX, uses a gap reduction to show general TSP has no constant ratio unless P = NP, and states the PCP theorem. In-page Python (Pyodide) measures ratios, and a real desktop networkx run compares Christofides with brute-force optima.

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

  • Optimisation সমস্যা, OPT আর approximation ratio-র নিখুঁত সংজ্ঞা
  • Vertex cover-এর 2-approximation আর greedy set cover-এর H(d) নিশ্চয়তার প্রমাণ
  • Knapsack FPTAS-এর গোল করার কৌশল আর PTAS, FPTAS, APX শ্রেণির মানচিত্র
  • Gap reduction দিয়ে প্রমাণ: সাধারণ TSP-এর কোনো ধ্রুবক-ratio approximation নেই, যদি না P = NP
  • PCP(r(n), q(n))-এর সংজ্ঞা, PCP theorem-এর বক্তব্য, আর তা থেকে MAX-3SAT-এর gap

১ · Optimisation সমস্যা আর approximation ratio

আগের মডিউল একটি কঠিন খবর দিয়ে শেষ হয়েছে: বাজারঘরের প্রায় প্রতিটি পরিকল্পনা-সমস্যা, সব জেলা ঘুরে আসার রুট, delivery slot ভাগ, গুদামে পাহারাদার বসানো, NP-complete. পর্ব ৬৩ বলেছে, P ≠ NP হলে এদের কোনোটির জন্য সব input-এ নির্ভুল আর দ্রুত algorithm নেই। কিন্তু ব্যবসা থেমে থাকে না। প্রশ্নটি তাই বদলে যায়: নিখুঁত উত্তর না পেলে, প্রমাণসহ “যথেষ্ট ভালো” উত্তর কি পাওয়া যায়? আর কতটা ভালো পাওয়া অসম্ভব?

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

পর্ব ০৫ আর পর্ব ৬২-এ optimisation problem আর তার decision রূপের সম্পর্ক দেখেছেন। এখন আনুষ্ঠানিক কাঠামো দরকার।

সংজ্ঞা ১.১ (NP optimisation সমস্যা)

একটি NP optimisation সমস্যা Π-তে থাকে: (১) instance-এর একটি সেট, যা polynomial সময়ে চেনা যায়; (২) প্রতিটি instance x-এর জন্য বৈধ সমাধানের সেট S(x), যার প্রতিটি সমাধান |x|-এর polynomial দৈর্ঘ্যের আর “y ∈ S(x)?” polynomial সময়ে মেলানো যায়; (৩) একটি ধনাত্মক মূল্য c(x, y), polynomial সময়ে হিসাবযোগ্য; (৪) লক্ষ্য: c সর্বনিম্ন করা (minimisation) বা সর্বোচ্চ করা (maximisation). সেরা মূল্যকে লেখা হয় OPT(x). এমন সব সমস্যার শ্রেণির নাম NPO.

লক্ষ করুন, শর্ত (২) আর (৩) ঠিক পর্ব ৫৮-এর certificate আর verifier-এর ভাষা: বৈধ সমাধান মানে ছোট, দ্রুত মেলানো যায় এমন সাক্ষী। তাই প্রতিটি NPO সমস্যার decision রূপ (“c(x, y) ≤ k এমন y আছে?”) NP-তে।

সংজ্ঞা ১.২ (Approximation ratio)

ধরুন A একটি polynomial সময়ের algorithm, যা প্রতিটি instance x-এ একটি বৈধ সমাধান দেয়, যার মূল্য ALG(x). A হলো একটি ρ-approximation algorithm (ρ ≥ 1), যদি প্রতিটি x-এর জন্য

minimisation-এ ALG(x) ≤ ρ · OPT(x),   maximisation-এ OPT(x) ≤ ρ · ALG(x).

ρ-কে বলে approximation ratio. ρ = 1 মানে নির্ভুল। ρ একটি ধ্রুবক হতে পারে (২, ১.৫), বা input-আকারের ফাংশন (ln n).

এই পর্বের পুরো কোর্সে একটিই নিয়ম: ρ সবসময় ১ বা তার বেশি, আর দুই ধরনের সমস্যায় ভগ্নাংশটি এমনভাবে লেখা যাতে “খারাপ” ভাগ “ভালো” দিয়ে। কিছু বই maximisation-এ ALG ≥ α · OPT লেখে, যেখানে α ≤ 1; তখন α = 1/ρ. যেমন MAX-3SAT-এ “7/8 অংশ পাওয়া যায়” মানে এই পর্বের ভাষায় ρ = 8/7.

দুটি সূক্ষ্ম কথা। প্রথমত, নিশ্চয়তাটি প্রতিটি input-এ, worst case-এ; কয়েকটি পরীক্ষায় ভালো ফল কোনো ratio প্রমাণ করে না। দ্বিতীয়ত, OPT নিজেই আমরা জানি না, কারণ তা বের করাই NP-hard. তাহলে ALG ≤ 2 · OPT প্রমাণ হবে কীভাবে? মূল কৌশল: OPT-এর একটি সহজে হিসাবযোগ্য নিম্নসীমা L খুঁজে বের করা (L ≤ OPT), তারপর দেখানো ALG ≤ ρ · L. পরের তিনটি অংশে তিনটি ভিন্ন নিম্নসীমা দেখবেন: একটি matching, একটি “দাম ভাগ”, আর একটি spanning tree.

২ · Vertex cover — maximal matching দিয়ে 2-approximation

বাজারঘরের আটটি গুদাম A থেকে H, আর এগারোটি সরাসরি রাস্তা। প্রতিটি রাস্তার অন্তত এক প্রান্তের গুদামে একজন তদারক কর্মকর্তা থাকতে হবে, আর কর্মকর্তা যত কম তত ভালো। এটি vertex cover-এর optimisation রূপ, যার decision রূপ NP-complete (পর্ব ৫৯)।

Algorithm-টি হাস্যকর রকম সরল। রাস্তাগুলো একটি একটি করে দেখুন; যদি রাস্তাটির দুই প্রান্তই এখনো খালি থাকে, দুই প্রান্তেই কর্মকর্তা বসান। যেসব রাস্তা বাছা হলো, তারা কোনো গুদাম ভাগ করে না, অর্থাৎ একটি matching; আর শেষে আর কোনো রাস্তা যোগ করা যায় না, তাই এটি একটি maximal matching.

উপপাদ্য ২.১

যেকোনো maximal matching M-এর সব প্রান্তের সেট C একটি vertex cover, আর |C| = 2|M| ≤ 2 · OPT. তাই উপরের algorithm vertex cover-এর একটি 2-approximation, সময় O(|V| + |E|).

প্রমাণ:

  1. C একটি cover: ধরুন কোনো edge e = {u, v} C-তে ঢাকা পড়েনি। তাহলে u আর v দুটিই M-এর কোনো edge-এ নেই, তাই M ∪ {e} তখনও একটি matching. এটি M-এর maximal হওয়ার বিরোধী। — maximal-এর সংজ্ঞা
  2. |C| = 2|M|, কারণ M-এর edge-গুলো কোনো vertex ভাগ করে না। — matching-এর সংজ্ঞা
  3. যেকোনো vertex cover C* M-এর প্রতিটি edge-এর অন্তত একটি প্রান্ত রাখে, আর এই প্রান্তগুলো সব আলাদা (আবার, edge-গুলো vertex ভাগ করে না)। তাই |C*| ≥ |M|, বিশেষত OPT ≥ |M|. — এটিই নিম্নসীমা
  4. মিলিয়ে: ALG = |C| = 2|M| ≤ 2 · OPT. ∎

নিচের stepper আট গুদামের graph-এ algorithm চালায়। রাস্তার ক্রম: AB, AC, BC, BD, CE, DE, DF, EG, FG, GH, FH.

Matching-based vertex cover on an 8-vertex graph ABC DEF GH AB বাছা: |M| = 1, cover {A, B} AC, BC, BD বাদ; CE বাছা: |M| = 2 DE বাদ; DF বাছা: |M| = 3 EG, FG বাদ; GH বাছা; FH বাদ |M| = 4, ALG = 8 গুদাম সবুজ: সেরা cover, OPT = 5
  1. প্রথম রাস্তা AB. A আর B দুটিই খালি, তাই AB matching-এ যায়, আর দুই প্রান্তে কর্মকর্তা বসে। |M| = 1, cover {A, B}.
  2. পরের চারটি। AC-তে A আগেই ঢাকা, BC আর BD-তে B ঢাকা, তাই তিনটিই বাদ। CE-র দুই প্রান্ত খালি, তাই CE বাছা হলো। |M| = 2, cover {A, B, C, E}.
  3. DE আর DF. DE-তে E ঢাকা, বাদ। DF-এর দুই প্রান্ত খালি, বাছা। |M| = 3, cover এখন ছয়টি গুদাম।
  4. শেষ চারটি। EG-তে E, FG-তে F ঢাকা, বাদ। GH বাছা। FH-এ F ঢাকা, বাদ। এখন কোনো রাস্তার দুই প্রান্ত একসঙ্গে খালি নেই, তাই M maximal.
  5. ফল। M-এ ৪টি রাস্তা, cover-এ ৮টি গুদাম, অর্থাৎ সবগুলো। প্রতিটি রাস্তা ঢাকা পড়েছে (প্রমাণের ধাপ ১)।
  6. নিম্নসীমা মেলানো। লাল চারটি রাস্তা কোনো গুদাম ভাগ করে না, তাই যেকোনো cover-এ অন্তত ৪ জন লাগে। Brute force-এ OPT = 5, যেমন {A, B, E, F, G}. মিলিয়ে দেখুন: |M| = 4 ≤ OPT = 5, আর ALG = 8 ≤ 2 · 5 = 10. এখানে ratio 8/5 = 1.6.

এখন অনেক random graph-এ একই কাজ। নিচের ব্লক n = 8, 10, 12 vertex-এর ৩০টি করে random graph বানায় (প্রতিটি জোড়ার মধ্যে edge-এর সম্ভাবনা 0.3, seed স্থির), matching-এর উত্তর আর brute-force OPT মেলায়, আর প্রমাণের দুটি অসমতা প্রতিটি graph-এ পরীক্ষা করে।

# Vertex cover: maximal-matching 2-approximation vs exact brute force
import random
from itertools import combinations
rng = random.Random(71)
def random_graph(n, p):
    return [(u, v) for u, v in combinations(range(n), 2) if rng.random() < p]
def matching_cover(edges):            # take both ends of a maximal matching
    cover, m = set(), 0
    for u, v in edges:
        if u not in cover and v not in cover:
            cover |= {u, v}; m += 1
    return len(cover), m
def opt_cover(n, edges):              # smallest k with a k-subset covering all
    masks = [(1 << u) | (1 << v) for u, v in edges]
    for k in range(n + 1):
        for S in combinations(range(n), k):
            s = sum(1 << x for x in S)
            if all(s & e for e in masks):
                return k
print(" n  graphs  avg ALG/OPT  worst  |M|<=OPT always  ALG<=2*OPT always")
for n in (8, 10, 12):
    ratios, lb_ok, ub_ok = [], True, True
    for _ in range(30):
        E = random_graph(n, 0.3)
        if not E: continue
        alg, m = matching_cover(E)
        opt = opt_cover(n, E)
        ratios.append(alg / opt)
        lb_ok &= m <= opt
        ub_ok &= alg <= 2 * opt
    print(f"{n:2}  {len(ratios):6}  {sum(ratios)/len(ratios):11.3f}  "
          f"{max(ratios):5.2f}  {str(lb_ok):15}  {ub_ok}")
# a perfect matching graph: n/2 disjoint edges -> the bound 2 is tight
E = [(2 * i, 2 * i + 1) for i in range(5)]
print("disjoint edges:", matching_cover(E)[0], "vs OPT", opt_cover(10, E))

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

 n  graphs  avg ALG/OPT  worst  |M|<=OPT always  ALG<=2*OPT always
 8      30        1.616   2.00  True             True
10      30        1.639   2.00  True             True
12      30        1.556   2.00  True             True
disjoint edges: 10 vs OPT 5

গড়ে উত্তর সেরার প্রায় ১.৬ গুণ, আর প্রতিটি দলে অন্তত একটি graph-এ ratio ঠিক ২ ছুঁয়েছে, কিন্তু কখনো পেরোয়নি। “True” কলাম দুটি প্রমাণের ধাপ ৩ আর ৪ প্রতিটি graph-এ মেলায়। শেষ লাইন দেখায় সীমাটি tight: পাঁচটি আলাদা edge-এর graph-এ algorithm দশটি vertex নেয়, অথচ প্রতি edge-এ একটি করে পাঁচটিই যথেষ্ট। তাই এই algorithm-এর বিশ্লেষণে ২-এর চেয়ে ভালো সংখ্যা বলা যায় না।

সাবধান: “সবচেয়ে বেশি degree-র vertex আগে নেওয়া” আরও স্বাভাবিক শোনায়, কিন্তু তা 2-approximation নয়। এই greedy-র ratio log n-এর মতো বাড়তে পারে, এমন graph-পরিবার জানা আছে। অন্তর্দৃষ্টি দিয়ে বানানো algorithm-কে ratio-র প্রমাণ ছাড়া বিশ্বাস করবেন না; DSA কোর্সের পর্ব ৬৬-এ algorithm-গুলোর code আর আরও উদাহরণ আছে, এই পর্ব প্রমাণ আর তার সীমার দিকটি দেখায়।

৩ · Greedy set cover আর harmonic সংখ্যা H(d)

বাজারঘর কয়েকটি courier প্রতিষ্ঠানের সঙ্গে চুক্তি করতে চায়। প্রতিটি প্রতিষ্ঠান কিছু জেলায় পৌঁছায়; সব জেলা ঢাকতে সবচেয়ে কম কয়টি চুক্তি লাগবে? এটি set cover: universe U-তে n টি উপাদান, উপসেট S1, …, Sm; সবচেয়ে কম উপসেট বাছতে হবে যাদের মিলন U. Vertex cover এর একটি বিশেষ রূপ (উপাদান = edge, উপসেট = একটি vertex-এর edge-গুলো), তাই set cover-ও NP-hard.

Greedy নিয়ম: প্রতিবার সেই উপসেট নিন, যা এখনো-না-ঢাকা সবচেয়ে বেশি উপাদান ঢাকে। এর নিশ্চয়তা আসে harmonic number H(d) = 1 + 1/2 + … + 1/d থেকে, যেখানে ln(d + 1) < H(d) ≤ 1 + ln d.

উপপাদ্য ৩.১ (Johnson ১৯৭৪, Lovász ১৯৭৫)

সবচেয়ে বড় উপসেটের আকার d হলে greedy set cover-এর উত্তর ALG ≤ H(d) · OPT ≤ (1 + ln n) · OPT.

প্রমাণের রূপরেখা (দাম ভাগের যুক্তি):

  1. Greedy যখন একটি উপসেট নেয়, যা k টি নতুন উপাদান ঢাকে, তখন সেই ১টি উপসেটের খরচ k টি উপাদানের মধ্যে সমান ভাগ করা হয়: প্রত্যেকের “দাম” 1/k. তাই সব দামের যোগফল ঠিক ALG. — হিসাবের কৌশল
  2. OPT-এর যেকোনো একটি উপসেট S নিন, আর তার উপাদানগুলো যে ক্রমে ঢাকা পড়ে সেই ক্রমে সাজান: e1, …, es. ei ঢাকার মুহূর্তে S-এর অন্তত s − i + 1 টি উপাদান তখনো খোলা, তাই S নিজেই অন্তত s − i + 1 টি নতুন উপাদান দিত। Greedy তার চেয়ে কম নয় এমন উপসেট নিয়েছে, তাই ei-এর দাম ≤ 1/(s − i + 1). — greedy নিয়ম
  3. S-এর সব উপাদানের দামের যোগফল ≤ 1/s + 1/(s − 1) + … + 1 = H(s) ≤ H(d).
  4. প্রতিটি উপাদান OPT-এর অন্তত একটি উপসেটে আছে, তাই ALG = মোট দাম ≤ ΣS ∈ OPT H(d) = H(d) · OPT. ∎

সীমাটি কি সত্যিই লগারিদমের মতো বাড়ে, না বিশ্লেষণ দুর্বল? নিচের ব্লক একটি পরিচিত খারাপ পরিবার বানায়: দুই সারিতে 2k − 1 টি করে উপাদান; সেরা উত্তর দুটি সারি নিজেই (OPT = 2), কিন্তু Si নামের উপসেটগুলো প্রতিটি সারি থেকে 2i−1 টি নেয়, আর প্রতি ধাপে একটু বেশি নতুন উপাদান দিয়ে greedy-কে ভুল পথে টানে।

# Greedy set cover: the H(d) guarantee and a family where greedy gets worse
from itertools import combinations
from fractions import Fraction
def greedy(U, sets):
    left, chosen = set(U), []
    while left:
        i = max(range(len(sets)), key=lambda j: len(sets[j] & left))
        chosen.append(i); left -= sets[i]
    return chosen
def opt(U, sets):
    for k in range(1, len(sets) + 1):
        for c in combinations(sets, k):
            if set().union(*c) >= U:
                return k
def H(n): return sum(Fraction(1, i) for i in range(1, n + 1))
# Bad family: two rows of 2^k - 1 elements; S_i takes 2^(i-1) from each row
print(" k   n  greedy  OPT  ratio  H(max set) bound")
for k in range(2, 7):
    top = list(range(2 ** k - 1))
    bot = [x + 100 for x in top]
    U = set(top) | set(bot)
    sets = [set(top), set(bot)]                       # the optimal two
    start = 0
    for i in range(1, k + 1):                         # S_1 .. S_k
        size = 2 ** (i - 1)
        sets.append(set(top[start:start + size]) | set(bot[start:start + size]))
        start += size
    g = len(greedy(U, sets)); o = opt(U, sets)
    d = max(len(s) for s in sets)
    print(f"{k:2} {len(U):3}  {g:6}  {o:3}  {g/o:5.2f}  "
          f"{float(H(d) * o):6.2f}")

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

 k   n  greedy  OPT  ratio  H(max set) bound
 2   6       2    2   1.00    4.17
 3  14       3    2   1.50    5.44
 4  30       4    2   2.00    6.76
 5  62       5    2   2.50    8.12
 6 126       6    2   3.00    9.49

k = 3 থেকে greedy প্রতিবার Sk, Sk−1, … নেয়, কারণ Sk-এ 2k টি নতুন উপাদান, যা একটি সারির 2k − 1-এর চেয়ে একটি বেশি। ফলে k টি উপসেট লাগে, অথচ ২টিই যথেষ্ট: ratio k/2, আর n = 2k+1 − 2 বলে ratio মোটামুটি (log2 n)/2, অর্থাৎ ln n-এর ধ্রুবক গুণিতক হারে বাড়ে। শেষ কলামের H(d) · OPT সীমা কখনো ভাঙেনি। তাই greedy-র ratio কোনো ধ্রুবক নয়; লগারিদমিক ক্ষতি অনিবার্য। অংশ ৭-এ দেখবেন, P ≠ NP ধরে নিলে কোনো polynomial algorithm-ই (1 − ε) ln n-এর চেয়ে ভালো পারে না।

৪ · TSP — metric হলে ২ আর ১.৫, না হলে অসম্ভব

TSP-এর optimisation রূপ: n টি শহরের প্রতিটি জোড়ার দূরত্ব d(u, v) দেওয়া; সব শহর একবার ঘুরে ফেরার সবচেয়ে ছোট tour. বাস্তবের রাস্তার দূরত্ব সাধারণত triangle inequality মানে: d(u, w) ≤ d(u, v) + d(v, w), অর্থাৎ মাঝে থেমে ঘুরে যাওয়া সরাসরি যাওয়ার চেয়ে ছোট হয় না। দূরত্ব প্রতিসম আর এই শর্ত মানলে সমস্যার নাম metric TSP; এটিও NP-hard, কিন্তু approximation-এর দিক থেকে অনেক বন্ধুসুলভ।

2-approximation-এর যুক্তি সংক্ষেপে (algorithm আর code DSA কোর্সের পর্ব ৬৬-এ): সেরা tour থেকে যেকোনো একটি edge মুছলে একটি spanning tree থাকে, তাই minimum spanning tree-এর ওজন MST ≤ OPT; এটিই নিম্নসীমা। MST-কে দুবার ঘুরলে (প্রতিটি edge যেতে-আসতে) দৈর্ঘ্য 2 · MST, আর আগে দেখা শহর এড়িয়ে সরাসরি পরের নতুন শহরে গেলে triangle inequality-র জন্য দৈর্ঘ্য বাড়ে না। তাই ALG ≤ 2 · MST ≤ 2 · OPT.

Christofides algorithm (১৯৭৬; Serdyukov স্বাধীনভাবে প্রায় একই সময়ে, যা বহু বছর পরে পশ্চিমে পরিচিত হয়) MST-এর বিজোড় degree-র vertex-গুলোতে একটি minimum-weight perfect matching যোগ করে Euler circuit বানায় আর শর্টকাট নেয়; ratio ৩/২. প্রায় ৪৫ বছর এর চেয়ে ভালো কিছু জানা ছিল না; ২০২০ সালের দিকে Karlin, Klein আর Oveis Gharan একটি randomized algorithm দেন, যা ৩/২-এর চেয়ে খুবই সামান্য (একটি অতি ক্ষুদ্র ধ্রুবক) ভালো বলে প্রমাণিত।

একটি সত্যিকারের library দিয়ে মিলিয়ে দেখা। uv দিয়ে বানানো ছোট প্রকল্পে networkx (BSD-3-Clause licence; এর কোডে কোনো network বা usage-reporting অংশ নেই, install-এর পর খুঁজে দেখা হয়েছে) দিয়ে ২০টি random Euclidean instance (প্রতিটিতে ৯টি বিন্দু, seed স্থির) চালানো হলো। “Double tree” আমাদের নিজের লেখা MST-দ্বিগুণ-শর্টকাট, আর Christofides networkx-এর নিজের; OPT এসেছে 8! = 40320 টি ক্রম brute force করে।

import networkx as nx
from networkx.algorithms import approximation as approx
# instance(), length(), exact() as in the full file: random points,
# Euclidean weights, brute force over all tours with vertex 0 fixed
def double_tree(G):                        # MST, preorder walk, shortcut
    T = nx.minimum_spanning_tree(G)
    order = list(nx.dfs_preorder_nodes(T, 0))
    return length(G, order + [0])
rng = random.Random(71)
r2, r15 = [], []
for _ in range(20):
    G = instance(9, rng)
    opt = exact(G)
    chris = approx.christofides(G)         # returns a closed tour
    r15.append(length(G, chris) / opt)
    r2.append(double_tree(G) / opt)

সত্যিকারের run (ডেস্কটপ, networkx 3.7, Python 3.12.13; পুরো run প্রায় ৩ সেকেন্ড):

~/bazarghar-toc$ uv run python tsp_ratio.py
python 3.12.13 | networkx 3.7
20 random Euclidean instances, 9 points each
double tree : mean 1.133  worst 1.340  (bound 2)
christofides: mean 1.057  worst 1.200  (bound 1.5)
all within bounds: True

দুটি algorithm-ই প্রমাণিত সীমার অনেক নিচে থেকেছে: Christofides গড়ে সেরার মাত্র ৫.৭% বেশি। এটি একটি সাধারণ অভিজ্ঞতা, worst-case ratio প্রায়ই বাস্তবের চেয়ে অনেক হতাশাজনক। কিন্তু উল্টো দিকটি ভুলবেন না: ২০টি ভালো ফল দিয়ে কোনো ratio প্রমাণ হয় না, আর triangle inequality না থাকলে এই নিশ্চয়তাগুলোর কোনোটিই খাটে না। ঠিক সেটিই এখন প্রমাণ করব।

সাধারণ TSP: কোনো ধ্রুবক ratio নয়

উপপাদ্য ৪.১ (Sahni–Gonzalez ১৯৭৬)

যেকোনো ধ্রুবক ρ ≥ 1-এর জন্য, সাধারণ (triangle inequality ছাড়া) TSP-এর কোনো polynomial সময়ের ρ-approximation algorithm নেই, যদি না P = NP.

প্রমাণ (HAMCYCLE থেকে, যা NP-complete, পর্ব ৬১):

  1. ধরুন A একটি polynomial সময়ের ρ-approximation algorithm. একটি graph G = (V, E), |V| = n, নিন।
  2. f(G): একই n টি শহর; d(u, v) = 1 যদি {u, v} ∈ E, নইলে d(u, v) = ρn + 1. সংখ্যাগুলোর binary দৈর্ঘ্য O(log(ρn)), তাই f polynomial সময়ে হিসাবযোগ্য। — reduction-এর গঠন
  3. G-এ Hamiltonian cycle থাকলে সেটিই একটি tour, যার প্রতিটি edge-এর ওজন 1: OPT = n. তাই A-এর উত্তর ≤ ρn. — approximation-এর সংজ্ঞা
  4. G-এ না থাকলে প্রতিটি tour অন্তত একটি অ-edge ব্যবহার করে, তাই প্রতিটি tour ≥ (n − 1) · 1 + (ρn + 1) = ρn + n > ρn. A-এর উত্তরও একটি tour, তাই > ρn. — tour-এ n টি edge
  5. অতএব “A-এর উত্তর ≤ ρn?” প্রশ্নটি ঠিক “G-এ Hamiltonian cycle আছে?”-এর উত্তর দেয়, polynomial সময়ে। তাহলে HAMCYCLE ∈ P, আর HAMCYCLE NP-complete বলে P = NP (পর্ব ৬৩-এর উপপাদ্য ১.২)। ∎

লক্ষ করুন যুক্তির মূল: gap reduction. “হ্যাঁ” instance-এর OPT ≤ n, আর “না” instance-এর OPT > ρn; মাঝখানের ফাঁকটি এত চওড়া যে একটি approximation algorithm-ও দুই দলকে আলাদা করে ফেলে। এমনকি ρ = 2n নিলেও ওজনের binary দৈর্ঘ্য polynomial থাকে, তাই এই ধরনের ratio-ও অসম্ভব। নিচের stepper n = 5-এ দুটি graph দিয়ে ছবিটি আঁকে, ρ = 2, তাই অ-edge-এর ওজন ρn + 1 = 11.

Gap reduction from Hamiltonian cycle to TSP on five cities 123 45 G1: ৬টি edge, HAMCYCLE-এর input নিরেট = 1, ড্যাশ = 11 OPT = 5, তাই ALG ≤ 10 G2: শহর 4 আর 5-এর edge একটিই OPT = 1+1+11+11+1 = 25 > 10
  1. Input: G1. পাঁচটি শহর, ছয়টি রাস্তা: 12, 23, 34, 45, 51 আর 13. প্রশ্ন: এতে Hamiltonian cycle আছে?
  2. Reduction f. পূর্ণ graph বানানো: G1-এর রাস্তার ওজন 1, বাকি চারটি জোড়ার (14, 24, 25, 35) ওজন ρn + 1 = 2 · 5 + 1 = 11. লক্ষ করুন triangle inequality ভাঙে: d(1, 4) = 11 > d(1, 5) + d(5, 4) = 2.
  3. “হ্যাঁ”-এর দিক। Tour 1-2-3-4-5-1 শুধু ওজন-1 রাস্তা নেয়: OPT = 5. যেকোনো 2-approximation-এর উত্তর তাই 5 থেকে 10-এর মধ্যে।
  4. Input: G2. রাস্তা 12, 13, 14, 15, 23. শহর 4 আর 5 শুধু 1-এর সঙ্গে যুক্ত, কিন্তু cycle-এ প্রতিটি শহরের দুটি প্রতিবেশী লাগে, তাই Hamiltonian cycle নেই। অ-edge পাঁচটি (24, 25, 34, 35, 45), প্রতিটির ওজন 11.
  5. “না”-এর দিক আর সিদ্ধান্ত। সেরা tour-ও দুটি ভারী রাস্তা নেয়: OPT = 25, যা 10-এর অনেক ওপরে। তাই নিয়ম “উত্তর ≤ ρn = 10 হলে হ্যাঁ” দুটি graph-ই ঠিক আলাদা করে। এমন A থাকলে HAMCYCLE polynomial সময়ে মীমাংসা হতো।

নিচের JavaScript ব্লক একই দুটি instance বানায় আর সব tour brute force করে OPT বের করে। একটি ρ-approximation-এর উত্তর কোন পরিসরে পড়তে পারে, তাও দেখায়।

// Gap reduction HAMCYCLE -> TSP: edge weight 1, non-edge weight rho*n + 1
function permutations(a) {
  if (a.length <= 1) return [a];
  return a.flatMap((x, i) =>
    permutations([...a.slice(0, i), ...a.slice(i + 1)]).map(p => [x, ...p]));
}
function gapInstance(n, edges, rho) {
  const has = new Set(edges.map(([u, v]) => u < v ? u + "-" + v : v + "-" + u));
  return (u, v) => has.has(u < v ? u + "-" + v : v + "-" + u) ? 1 : rho * n + 1;
}
function bestTour(n, d) {             // brute force: fix vertex 1, permute the rest
  let best = Infinity, arg = null;
  const rest = Array.from({ length: n - 1 }, (_, i) => i + 2);
  for (const p of permutations(rest)) {
    const t = [1, ...p, 1];
    let len = 0;
    for (let i = 0; i < n; i++) len += d(t[i], t[i + 1]);
    if (len < best) { best = len; arg = t; }
  }
  return [best, arg];
}
const n = 5, rho = 2;
const graphs = {
  G1: [[1, 2], [2, 3], [3, 4], [4, 5], [5, 1], [1, 3]],
  G2: [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3]],
};
console.log(`n = ${n}, rho = ${rho}, non-edge weight = ${rho * n + 1}`);
for (const [name, E] of Object.entries(graphs)) {
  const [opt, tour] = bestTour(n, gapInstance(n, E, rho));
  const verdict = opt <= rho * n ? "has a Hamiltonian cycle" : "has none";
  console.log(`${name}: OPT = ${opt} (tour ${tour.join("-")}), ` +
              `ALG in [${opt}, ${rho * opt}] -> ${verdict}`);
}
console.log(`threshold: a rho-approx answer <= ${rho * n} iff G has one`);

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

n = 5, rho = 2, non-edge weight = 11
G1: OPT = 5 (tour 1-2-3-4-5-1), ALG in [5, 10] -> has a Hamiltonian cycle
G2: OPT = 25 (tour 1-2-3-4-5-1), ALG in [25, 50] -> has none
threshold: a rho-approx answer <= 10 iff G has one

দুটি পরিসর [5, 10] আর [25, 50] কখনো মেশে না; এটিই “gap”. G2-এ OPT ঠিক 25, কারণ শহর 4 আর 5-কে দুটি ভারী রাস্তা লাগে, প্রমাণের ন্যূনতম ρn + n = 15-এর চেয়েও বেশি। rho বদলে 10 বা 100 করে দেখুন: ফাঁক সবসময় থাকে। এখানে brute force চলছে শুধু ছবিটি দেখাতে; প্রমাণে কোনো brute force নেই।

৫ · Approximation scheme — knapsack FPTAS, PTAS আর APX

কিছু সমস্যায় যত কাছে চান তত কাছে যাওয়া যায়, শুধু দাম হিসেবে সময় বাড়ে। দুটি সংজ্ঞা:

সংজ্ঞা ৫.১ (PTAS আর FPTAS)

PTAS (polynomial-time approximation scheme): একটি algorithm, যা input x আর যেকোনো ε > 0 নিয়ে একটি (1 + ε)-approximation দেয়, আর প্রতিটি স্থির ε-এর জন্য সময় |x|-এর polynomial, যেমন O(n1/ε)।

FPTAS (fully polynomial): সময় একসঙ্গে |x| আর 1/ε দুটিরই polynomial, যেমন O(n3/ε)।

সবচেয়ে পরিচিত FPTAS 0/1 knapsack-এর (Ibarra আর Kim, ১৯৭৫): n টি পার্সেল, ওজন wi, মূল্য vi, ট্রাকের সীমা W; সীমার মধ্যে মোট মূল্য সর্বোচ্চ করতে হবে। Decision রূপ NP-complete, কিন্তু একটি pseudo-polynomial dynamic programming আছে: “ঠিক s মূল্য পেতে সবচেয়ে কম কত ওজন লাগে” টেবিল, যার আকার মোট মূল্য V-এর সমানুপাতিক। মূল্যগুলো বড় হলে টেবিল বিশাল। কৌশল: মূল্যগুলো ছোট করে গোল করা।

উপপাদ্য ৫.২

K = ε · vmax / n নিন, v′i = ⌊vi/K⌋ দিয়ে নির্ভুল DP চালান, আর পাওয়া সেট S′ ফেরত দিন। তাহলে আসল মূল্যে val(S′) ≥ (1 − ε) · OPT, আর সময় O(n3/ε).

প্রমাণের রূপরেখা:

  1. ধরে নিন প্রতিটি পার্সেল একা ট্রাকে ধরে (না ধরলে আগেই বাদ), তাই OPT ≥ vmax. — নিম্নসীমা
  2. গোল করায় প্রতিটি মূল্য বড়জোর K কমে: K · v′i ≥ vi − K.
  3. O একটি সেরা সেট হলে, S′ গোল করা মূল্যে সেরা বলে val(S′) ≥ K · v′(S′) ≥ K · v′(O) ≥ val(O) − |O| · K ≥ OPT − nK = OPT − ε · vmax ≥ (1 − ε) · OPT.
  4. প্রতিটি v′i ≤ vmax/K = n/ε, তাই টেবিলের দৈর্ঘ্য ≤ n2/ε, আর n টি পার্সেলের জন্য সময় O(n3/ε). ∎

এই পর্বের ratio-নিয়মে maximisation-এর জন্য OPT ≤ ρ · ALG, যেখানে ρ = 1/(1 − ε) ≈ 1 + ε. নিচের ব্লক ৩০টি পার্সেলের একটি random instance-এ (ওজন 50–300, মূল্য ১,০০০ থেকে ৯৯,৯৯৯ টাকা, W = 1000) চারটি ε-তে FPTAS চালায় আর নির্ভুল DP-র সঙ্গে মেলায়।

# 0/1 knapsack FPTAS: round values down to multiples of K, exact DP on values
import random
rng = random.Random(1)
n, W = 30, 1000
w = [rng.randint(50, 300) for _ in range(n)]          # parcel weight
v = [rng.randint(1000, 99999) for _ in range(n)]      # order value (taka)

def exact():                       # classic DP over capacity
    f = [0] * (W + 1)
    for wi, vi in zip(w, v):
        for c in range(W, wi - 1, -1):
            f[c] = max(f[c], f[c - wi] + vi)
    return f[W]

def fptas(eps):
    K = eps * max(v) / n
    r = [int(x // K) for x in v]                      # rounded-down values
    top = sum(r)
    best = [(0, 0)] + [(W + 1, 0)] * top              # (least weight, item mask)
    for i in range(n):
        for s in range(top, r[i] - 1, -1):
            pw, pm = best[s - r[i]]
            if pw + w[i] < best[s][0]:
                best[s] = (pw + w[i], pm | (1 << i))
    s = max(t for t in range(top + 1) if best[t][0] <= W)
    mask = best[s][1]
    return sum(v[i] for i in range(n) if mask >> i & 1), top + 1

OPT = exact()
print("OPT =", OPT)
print("eps    table cells  FPTAS value  value/OPT  >= 1-eps?")
for eps in (0.9, 0.5, 0.2, 0.05):
    val, cells = fptas(eps)
    print(f"{eps:<5}  {cells:11}  {val:11}  {val/OPT:9.4f}  {val >= (1-eps)*OPT}")

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

OPT = 542504
eps    table cells  FPTAS value  value/OPT  >= 1-eps?
0.9            469       542123     0.9993  True
0.5            854       542123     0.9993  True
0.2           2160       542123     0.9993  True
0.05          8690       542504     1.0000  True

টেবিলের আকার মোটামুটি 1/ε-এর সঙ্গে বাড়ে (469 থেকে 8690), কিন্তু মূল্যের মাপের ওপর নির্ভর করে না: মূল্যগুলো লাখে হলেও টেবিল ছোট থাকে। ε = 0.9-এর নিশ্চয়তা মাত্র “OPT-এর ১০%”, অথচ আসল উত্তর সেরার ৯৯.৯৩%; ε = 0.05-এ সেরাটিই এসেছে। আবারও worst-case নিশ্চয়তা বাস্তবের চেয়ে হতাশাজনক। (অন্য seed-এ প্রায়ই সব ε-তে ঠিক OPT আসে; এই seed বাছা হয়েছে যাতে গোল করার প্রভাব চোখে পড়ে।)

কোন সমস্যার FPTAS থাকতে পারে না? ধরুন একটি সমস্যার মূল্য পূর্ণসংখ্যা, আর OPT ≤ p(n, U), যেখানে U input-এর সবচেয়ে বড় সংখ্যা আর p একটি polynomial. ε = 1/(p + 1) নিলে একটি FPTAS-এর উত্তর ALG ≥ (1 − ε)OPT > OPT − 1, অর্থাৎ ঠিক OPT, আর সময় poly(n, U): একটি pseudo-polynomial নির্ভুল algorithm. সমস্যাটি strongly NP-hard হলে (সংখ্যাগুলো ছোট হলেও NP-hard) তাতে P = NP আসত। তাই strongly NP-hard সমস্যার FPTAS নেই, যদি না P = NP (Garey আর Johnson, ১৯৭৮)। Bin packing, Euclidean TSP এমন সমস্যা।

সংজ্ঞা ৫.৩ (APX আর APX-hard)

APX হলো সেই NPO সমস্যাগুলোর শ্রেণি, যাদের কোনো ধ্রুবক ρ-এর approximation আছে। একটি সমস্যা APX-hard, যদি APX-এর প্রতিটি সমস্যা ratio-রক্ষাকারী এক ধরনের reduction-এ (PTAS reduction) এতে আসে; তখন এর PTAS থাকলে APX-এর সবার PTAS থাকত।

Approximation শ্রেণির সিঁড়ি

প্রতিটি সমস্যা তার সবচেয়ে ভেতরের জানা অঞ্চলে বসানো। সীমানাগুলো আলাদা, যদি না P = NP.

FPTAS inside PTAS inside APX inside NPO, with example problems NPO APX PTAS FPTAS সাধারণ TSP · MAX-CLIQUE SET-COVER (ln n) VERTEX-COVER · MAX-3SAT metric TSP Euclidean TSP KNAPSACK প্রতিটি সীমানা আলাদা, যদি না P = NP P = NP হলে সব সমস্যা নির্ভুল, সব মিশে যায়
ছবি ৭১.১ — FPTAS ⊆ PTAS ⊆ APX ⊆ NPO সংজ্ঞা থেকেই। Knapsack-এর FPTAS আছে; Euclidean TSP-এর PTAS আছে (Arora ১৯৯৬, Mitchell স্বাধীনভাবে) কিন্তু strongly NP-hard বলে FPTAS নেই; vertex cover, MAX-3SAT আর metric TSP APX-hard, তাই PTAS নেই; set cover, MAX-CLIQUE আর সাধারণ TSP-এর কোনো ধ্রুবক ratio নেই। শেষ দুটি “নেই” এসেছে PCP theorem থেকে (অংশ ৬–৭); প্রতিটি “নেই” মানে “P ≠ NP হলে নেই”।

৬ · Gap problem আর PCP theorem — প্রমাণ এক নজরে যাচাই

সাধারণ TSP-এর অসম্ভবতা এসেছে একটি সস্তা কৌশল থেকে: ওজন যত খুশি বড় করা। Vertex cover বা MAX-3SAT-এ এমন স্বাধীনতা নেই। 3SAT থেকে সাধারণ reduction দেয় শুধু “সব clause সত্য” বনাম “অন্তত একটি clause মিথ্যা”, অর্থাৎ m-এর মধ্যে m বনাম m − 1: ফাঁক মাত্র 1/m, যা n বাড়লে শূন্যের দিকে যায়। ধ্রুবক ফাঁক কোথা থেকে আসবে? উত্তর একটি অবাক করা উপপাদ্য, যা প্রমাণ যাচাইয়ের ধারণাই বদলে দেয়।

নামের গোলমাল এড়ান: এখানে PCP মানে probabilistically checkable proof. পর্ব ৫৪-এর Post correspondence problem-এর সংক্ষিপ্ত রূপও PCP, কিন্তু দুটি সম্পূর্ণ আলাদা বিষয়: একটি undecidability-র, অন্যটি complexity-র।

পর্ব ৫৮-এর NP verifier পুরো certificate পড়ে। এখন verifier-কে কৃপণ করুন: সে কয়েকটি random coin ছোড়ে, আর তার ফলে ঠিক করে প্রমাণের কোন কয়েকটি অবস্থান পড়বে।

সংজ্ঞা ৬.১ (PCP(r(n), q(n)))

একটি language L ∈ PCP(r(n), q(n)), যদি একটি polynomial সময়ের randomized verifier V থাকে, যা input x (|x| = n) আর একটি প্রমাণ-string π-তে random-access পায়, বড়জোর r(n) টি random বিট ব্যবহার করে আর π-এর বড়জোর q(n) টি বিট পড়ে, এবং:

  • Completeness: x ∈ L হলে এমন π আছে যাতে V সম্ভাবনা 1-এ গ্রহণ করে।
  • Soundness: x ∉ L হলে প্রতিটি π-এর জন্য V গ্রহণ করে বড়জোর সম্ভাবনা 1/2-এ।

এমন verifier যে প্রমাণ পড়ে, তাকে বলে probabilistically checkable proof.

দুটি সহজ প্রান্ত: PCP(0, 0) = P (কোনো coin নেই, কিছু পড়ে না), আর PCP(0, poly(n)) = NP (coin নেই, পুরো certificate পড়ে)। মাঝের অবস্থাটি কেমন, নিচের stepper বাজারঘরের delivery-slot সমস্যায় দেখায়। ছয়টি অর্ডার, তিনটি slot; দুটি অর্ডারের সংঘাত থাকলে (একই rider, একই সময়) তারা একই slot পেতে পারে না: সংঘাতগুলো e1 = (1,2), e2 = (1,3), e3 = (1,4), e4 = (2,3), e5 = (2,4), e6 = (3,4), e7 = (4,5), e8 = (5,6), e9 = (3,6). অর্ডার 1–4 প্রত্যেকে প্রত্যেকের সঙ্গে সংঘাতে, তাই তিন slot-এ ভাগ অসম্ভব (3-COLOR-এর “না” instance). একজন প্রতারক তবুও একটি “প্রমাণ” দেন।

1π = প্রতিটি অর্ডারের slot2coin দিয়ে সংঘাত e = (u, v) বাছাই3π[u], π[v] পড়া; আলাদা হলে গ্রহণ4k বার স্বাধীনভাবে পুনরাবৃত্তি5PCP: π-কে নতুন করে লেখা
verifier-এর অবস্থা
প্রমাণ π
বাছা সংঘাত
পড়া হলো
ধরার সম্ভাবনা
  1. প্রমাণটি। π বলে অর্ডার 1 থেকে 6-এর slot যথাক্রমে 1, 2, 3, 1, 2, 1. নয়টি সংঘাতের আটটি ঠিক আছে, শুধু e3 = (1,4)-এ দুটিই slot 1. Brute force-এ দেখা যায় এর চেয়ে ভালো প্রতারণা সম্ভব নয়: প্রতিটি ভাগে অন্তত একটি সংঘাত ভাঙে।
  2. প্রথম স্পট-চেক। চারটি coin (9টি সংঘাতের একটি বাছতে যথেষ্ট) e7 = (4,5) বাছে। Verifier শুধু π[4] = 1 আর π[5] = 2 পড়ে; আলাদা, তাই গ্রহণ। পুরো প্রমাণের ছয়টির মধ্যে মাত্র দুটি ঘর দেখা হলো।
  3. ভাগ্য ভালো হলে। Coin e3 = (1,4) বাছলে π[1] = π[4] = 1, তাই প্রত্যাখ্যান। কিন্তু নয়টির মধ্যে এই একটিই খারাপ, তাই এক চেকে প্রতারণা ধরার সম্ভাবনা মাত্র 1/9.
  4. পুনরাবৃত্তি। k টি স্বাধীন চেকে ধরা পড়ার সম্ভাবনা 1 − (8/9)k: k = 6-এ 0.507, k = 40-এ 0.991. সাধারণভাবে m টি সংঘাতে 1/2-এ পৌঁছাতে প্রায় m · ln 2 ≈ 0.69m চেক লাগে, তাই পড়া বিটের সংখ্যা input-এর সঙ্গে বাড়ে। এই সরল verifier PCP(O(log n), O(1))-এর মাপে নয়, কারণ তার soundness 1 − 1/m, ধ্রুবক নয়।
  5. PCP theorem যা দেয়। প্রমাণটিকে একটি লম্বা, error-correcting ধাঁচে নতুন করে লেখা যায় (দৈর্ঘ্য তবুও polynomial), যাতে “না” instance-এর যেকোনো প্রমাণ প্রতি চেকে অন্তত 1/2 সম্ভাবনায় ধরা পড়ে, O(log n) coin আর ধ্রুবক সংখ্যক বিট পড়ে। তখন 10টি চেকেই ধরা পড়ার সম্ভাবনা ≥ 1 − 2−10 ≈ 0.999, input যত বড়ই হোক।
উপপাদ্য ৬.২ (PCP theorem)

NP = PCP(O(log n), O(1)).

অর্থাৎ NP-এর প্রতিটি language-এর জন্য এমন verifier আছে, যা O(log n) random বিট ব্যবহার করে আর প্রমাণের শুধু একটি ধ্রুবক সংখ্যক বিট পড়ে। ধ্রুবকটি সব input-এর জন্য একই।

উপপাদ্যটি ১৯৯২ সালে দুটি প্রবন্ধে প্রমাণিত হয় বলে সাধারণত উল্লেখ করা হয়: Arora আর Safra, এবং Arora, Lund, Motwani, Sudan আর Szegedy (পূর্ণ journal সংস্করণ ১৯৯৮)। এর আগে Feige, Goldwasser, Lovász, Safra আর Szegedy (১৯৯১) interactive proof-এর কৌশল থেকে MAX-CLIQUE-এর inapproximability-র সঙ্গে সংযোগটি দেখান। মূল প্রমাণ বীজগাণিতিক আর দীর্ঘ; Irit Dinur ২০০৬–০৭ সালে “gap amplification” নামে একটি তুলনামূলক combinatorial প্রমাণ দেন। এই পর্বে পূর্ণ প্রমাণ বাদ; Arora–Barak-এর বইয়ে দুটি পথই আছে। কিন্তু একটি দিক সহজ, আর সেটি নিজে প্রমাণ করা যায়।

উপপাদ্য ৬.৩ (সহজ দিক)

PCP(O(log n), O(1)) ⊆ NP.

প্রমাণ:

  1. ধরুন V c · log n টি coin ব্যবহার করে আর q টি বিট পড়ে। সম্ভাব্য coin-ফল 2c log n = nc টি, একটি polynomial. — log-এর জাদু
  2. প্রতিটি coin-ফলে V বড়জোর q টি অবস্থান পড়ে (আগের উত্তর দেখে পরের অবস্থান ঠিক করলেও সম্ভাব্য অবস্থান বড়জোর 2q). তাই সব মিলিয়ে π-এর বড়জোর nc · 2q টি অবস্থান কখনো পড়া হয়, যা polynomial. NP-certificate হলো π-এর ঠিক এই অবস্থানগুলোর বিট। — certificate ছোট
  3. NP verifier: সব nc টি coin-ফল একে একে চালান, প্রতিটিতে V-কে certificate থেকে উত্তর দিন; সব গ্রহণ করলে গ্রহণ। সময় nc · poly(n), polynomial.
  4. x ∈ L: completeness থেকে একটি π-তে সব coin-ফলে গ্রহণ, তাই সেই π-এর অংশটি কাজের certificate. x ∉ L: যেকোনো certificate-কে একটি π-তে বাড়ানো যায়, আর soundness থেকে অন্তত অর্ধেক coin-ফলে প্রত্যাখ্যান, তাই আমাদের verifier প্রত্যাখ্যান করে। ∎

কঠিন দিক NP ⊆ PCP(O(log n), O(1)) হলো আসল বিস্ময়: প্রতিটি গাণিতিক প্রমাণ (যা NP-certificate হিসেবে লেখা যায়) এমনভাবে নতুন করে লেখা যায় যে দৈবভাবে তিন-চারটি জায়গা দেখেই উচ্চ সম্ভাবনায় বোঝা যায় প্রমাণটি সঠিক কি না। ব্যাংকের হাজার পাতার হিসাব-খাতার কথা ভাবুন, যা এমনভাবে লেখা যে একটি ভুলও পুরো খাতার বহু জায়গায় অসংগতি ছড়িয়ে দেয়; তখন নিরীক্ষক কয়েকটি এলোমেলো পাতা দেখেই প্রতারণা ধরেন। Error-correcting code-এর ধারণাটি এখানেই।

৭ · PCP থেকে inapproximability — MAX-3SAT আর gap

MAX-3SAT: একটি 3CNF সূত্র, যার প্রতিটি clause-এ তিনটি আলাদা চলকের literal; লক্ষ্য সর্বোচ্চ সংখ্যক clause সত্য করা। প্রথমে একটি সহজ algorithm. প্রতিটি চলকে স্বাধীনভাবে সমান সম্ভাবনায় সত্য/মিথ্যা বসান। একটি clause মিথ্যা হয় শুধু তিনটি literal-ই মিথ্যা হলে, সম্ভাবনা (1/2)3 = 1/8. তাই প্রত্যাশিত সত্য clause = 7m/8 ≥ 7 · OPT / 8. Conditional expectation পদ্ধতিতে (চলক একে একে বসিয়ে, প্রতিবার যে মানে প্রত্যাশা কমে না সেটি নিয়ে) এটি deterministic করা যায়। তাই MAX-3SAT-এর ratio ρ = 8/7, আর MAX-3SAT ∈ APX.

এখন উল্টো দিক, অর্থাৎ inapproximability. একটি gap problem হলো “প্রতিশ্রুতি”-সহ decision সমস্যা: GAP-3SATs-এ input একটি 3CNF, যা হয় পুরোপুরি satisfiable, নয়তো যার প্রতিটি assignment বড়জোর s অংশ clause সত্য করে; বলতে হবে কোনটি। MAX-3SAT-এর (1/s)-এর চেয়ে ভালো approximation থাকলে GAP-3SATs polynomial সময়ে মীমাংসা হতো (উত্তর > s · m কি না দেখে), ঠিক TSP-এর মতো যুক্তিতে।

উপপাদ্য ৭.১ (PCP-এর gap রূপ)

এমন একটি ধ্রুবক ε > 0 আছে যাতে GAP-3SAT1−ε NP-hard. ফলে MAX-3SAT-এর কোনো PTAS নেই, যদি না P = NP. উল্টোভাবে, এই বক্তব্য থেকে PCP theorem-ও আসে: দুটি সমতুল্য।

প্রমাণের রূপরেখা (PCP ⇒ gap):

  1. L NP-complete হলে PCP theorem থেকে verifier V: c log n coin, q টি বিট। প্রমাণের প্রতিটি বিটকে একটি Boolean চলক ধরুন।
  2. প্রতিটি coin-ফল R-এর জন্য V-এর সিদ্ধান্ত মাত্র q টি চলকের একটি Boolean ফাংশন, যাকে বড়জোর 2q টি clause-এর CNF-এ লেখা যায়, আর তা থেকে (পর্ব ৬০-এর clause-ভাঙার কৌশলে) বড়জোর q · 2q টি 3-clause-এ। মোট clause nc · q · 2q, polynomial; এটিই reduction f(x). — q ধ্রুবক বলে প্রতিটি টুকরো ধ্রুবক আকারের
  3. x ∈ L: সঠিক প্রমাণে সব coin-ফল গ্রহণ করে, তাই f(x) পুরো satisfiable.
  4. x ∉ L: যেকোনো assignment (= যেকোনো π)-এ অন্তত অর্ধেক coin-ফল প্রত্যাখ্যান করে, আর প্রতিটি প্রত্যাখ্যানকারী টুকরোয় অন্তত একটি clause মিথ্যা। তাই মিথ্যা clause-এর অংশ ≥ (1/2) / (q · 2q) =: ε, একটি ধ্রুবক। ∎

উল্টো দিক সংক্ষেপে: GAP-3SAT1−ε NP-hard হলে verifier একটি random clause বাছে (O(log n) coin), তার তিনটি চলক প্রমাণে পড়ে; “না” instance-এ প্রতি চেকে ধরা পড়ার সম্ভাবনা ≥ ε, ধ্রুবক সংখ্যক পুনরাবৃত্তিতে 1/2.

এই ε খুব ছোট। কতটা শক্ত করা যায়? Johan Håstad ২০০১ সালের প্রবন্ধে দেখান, যেকোনো ε > 0-এর জন্য GAP-3SAT7/8+ε NP-hard. অর্থাৎ random assignment-এর 7/8-ই সেরা: ρ = 8/7 − δ-এর কোনো approximation নেই, যদি না P = NP. একটি তুচ্ছ coin-ছোড়া algorithm-ই প্রমাণযোগ্যভাবে সর্বোত্তম, এটি এই তত্ত্বের সবচেয়ে সুন্দর ফলগুলোর একটি।

সমস্যাজানা সেরা ratioএর নিচে NP-hard (P ≠ NP ধরে)
MAX-3SAT8/7 (random assignment)8/7 − δ (Håstad ২০০১)
VERTEX-COVER2 (ছোট lower-order উন্নতি ছাড়া)√2 − δ (২০১৮ সালের 2-to-2 ফল থেকে বলে জানা যায়); UGC ধরে 2 − δ
SET-COVERH(d) ≤ 1 + ln n(1 − δ) ln n (Dinur–Steurer ২০১৪)
metric TSP1.5, সামান্য উন্নতিসহ123/122 (২০১৫ সালের একটি ফল, প্রায়)
সাধারণ TSPকোনো ধ্রুবক নয়যেকোনো ধ্রুবক ρ (উপপাদ্য ৪.১)
MAX-CLIQUEপ্রায় nn1−δ (Håstad ১৯৯৯; Zuckerman ২০০৭-এর পর P ≠ NP ধরেই)

লক্ষ করুন তৃতীয় কলামের প্রতিটি সংখ্যা একটি শর্তসাপেক্ষ বক্তব্য। কয়েকটি ফাঁক আজও খোলা: metric TSP-এ ১.৫ আর ১২৩/১২২-এর মাঝে, vertex cover-এ ২ আর √২-এর মাঝে। এদের সঠিক উত্তর কেউ জানে না।

আরও গভীরে: Subhash Khot ২০০২ সালে Unique Games Conjecture (UGC) প্রস্তাব করেন: একটি বিশেষ ধরনের দুই-চলকের constraint সমস্যায় “প্রায় সব সত্য” আর “প্রায় কিছুই সত্য নয়” আলাদা করা NP-hard. এটি সত্য হলে vertex cover-এ 2 − δ (Khot–Regev ২০০৮) আর MAX-CUT-এ Goemans–Williamson-এর ০.৮৭৮ গুণক সর্বোত্তম হয়, আর Raghavendra (২০০৮) দেখান তখন বহু constraint সমস্যায় একটি নির্দিষ্ট semidefinite programming algorithm-ই সেরা। UGC আজও খোলা; ২০১৮ সালে প্রমাণিত 2-to-2 games theorem এর দিকে একটি বড় পদক্ষেপ বলে গণ্য। আরেকটি দিক: PCP(poly(n), poly(n)) = NEXP (Babai–Fortnow–Lund ১৯৯১-এর ফল থেকে), যা পর্ব ৭৪-এর interactive proof-এর সঙ্গে যুক্ত।

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

  • Approximation ratio-র সংজ্ঞা দিন। Minimisation-এ প্রতিটি input-এ ALG ≤ ρ·OPT, maximisation-এ OPT ≤ ρ·ALG, polynomial সময়ে।
  • Vertex cover-এর 2-approximation প্রমাণ করুন। Maximal matching M-এর প্রান্তগুলো cover; যেকোনো cover-এ |M|-এর প্রতিটি edge-এর আলাদা প্রান্ত, তাই 2|M| ≤ 2·OPT.
  • সাধারণ TSP কেন approximate করা যায় না? HAMCYCLE থেকে gap reduction: edge = 1, অ-edge = ρn + 1; P ≠ NP ধরে।
  • PTAS আর FPTAS-এর পার্থক্য? দুটিই (1 + ε); FPTAS-এর সময় 1/ε-এরও polynomial. Strongly NP-hard হলে FPTAS নেই, যদি না P = NP.
  • PCP theorem লিখুন। NP = PCP(O(log n), O(1)); সমতুল্যভাবে GAP-3SAT একটি ধ্রুবক ফাঁকে NP-hard, তাই MAX-3SAT-এর PTAS নেই, যদি না P = NP.

৮ · AI-এর যুগে approximation আর PCP

AI assistant-কে “এই NP-hard সমস্যার জন্য একটি approximation algorithm দাও” বললে প্রায়ই একটি বিশ্বাসযোগ্য greedy algorithm আর একটি আত্মবিশ্বাসী ratio আসে। Ratio-টি প্রায়ই প্রমাণহীন, কখনো স্পষ্টতই ভুল। কয়েকটি ভুল বারবার দেখা যায়:

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“সবচেয়ে বেশি degree আগে” vertex cover-কে 2-approximation বলাপ্রমাণ চান; ছোট graph-এ brute force OPT-এর সঙ্গে মেলান; জানা খারাপ পরিবার খুঁজুন
Maximisation-এ ratio-র দিক উল্টে লেখা (ALG ≤ ρ·OPT)সংজ্ঞা লিখে ρ ≥ 1 কি না আর কোন দিকে অসমতা, নিজে মেলান
Christofides বা MST-দ্বিগুণকে সাধারণ TSP-তে খাটানোTriangle inequality আছে কি না দেখুন; না থাকলে কোনো ধ্রুবক ratio নেই
“MAX-3SAT-এর 0.9-approximation নেই” লেখা কিন্তু “যদি না P = NP” বাদপ্রতিটি inapproximability-র শর্ত (P ≠ NP, UGC) লিখে নিন
PCP theorem-কে Post correspondence problem-এর সঙ্গে গুলিয়ে ফেলাসংজ্ঞা দেখুন: verifier, coin আর query, না ডমিনো
বানানো ধ্রুবক বা সাল (“vertex cover-এ 1.5 প্রমাণিত”)Vazirani, Williamson–Shmoys, Arora–Barak-এ নিজে খুঁজুন

AI-কে কাজে লাগানোর ভালো উপায়: algorithm-এর সঙ্গে নিম্নসীমাটি আলাদা করে চাওয়া, প্রমাণ ধাপে ধাপে চাওয়া, আর ছোট instance-এ brute force দিয়ে ratio মেলানোর code নিজে চালানো।

আমি গণনার তত্ত্ব শিখছি। Approximation algorithm নিয়ে নিচের কাজগুলো করো। ১. Weighted নয় এমন set cover-এর greedy algorithm লেখো, আর H(d) সীমার প্রমাণ দাও। প্রমাণে OPT-এর কোন নিম্নসীমা বা কোন দাম-ভাগ ব্যবহার করছ, স্পষ্ট বলো। ২. Python-এ একটি ছোট script লেখো, যা ২০টি random instance-এ greedy-র উত্তর brute-force OPT-এর সঙ্গে মেলায় আর H(d) · OPT সীমা ভাঙে কি না দেখায়। কোনো আউটপুট নিজে বানিয়ো না। ৩. সাধারণ TSP-এ কোনো ধ্রুবক ratio কেন অসম্ভব, তার gap reduction লেখো, আর শর্তটি (P ≠ NP) উল্লেখ করো। ৪. PCP theorem-এর বক্তব্য দাও, আর কোন অংশ প্রমাণিত, কোন অংশ অনুমান (যেমন UGC) তা আলাদা করো। কোনো সাল বা ধ্রুবক নিশ্চিত না হলে বলো, বানিয়ো না।

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

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

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

প্র ০১Decision রূপে সব NP-complete সমস্যা “সমান কঠিন”, তবু approximation-এ knapsack প্রায় নির্ভুল আর clique প্রায় আশাহীন। এই ফারাক কোথা থেকে আসে?

পর্ব ৫৯-এর polynomial-time reduction শুধু “হ্যাঁ” আর “না” রক্ষা করে: w ∈ A ⇔ f(w) ∈ B. এটি মূল্যের মাপ রক্ষা করার কোনো প্রতিশ্রুতি দেয় না। তাই দুটি সমস্যা decision-এর অর্থে সমতুল্য হলেও তাদের optimisation রূপের আচরণ সম্পূর্ণ আলাদা হতে পারে।

সবচেয়ে নাটকীয় উদাহরণ vertex cover আর independent set. একটি graph-এ C একটি vertex cover ⇔ V − C একটি independent set, তাই OPTIS = n − OPTVC. Decision-এর দিক থেকে এরা প্রায় একই সমস্যা। কিন্তু vertex cover-এর 2-approximation আছে, আর independent set (সমতুল্যভাবে complement graph-এ clique) n1−δ-এর চেয়ে ভালো approximate করা যায় না, যদি না P = NP. কারণ সরল পাটিগণিত: OPTVC = n/2 − 1 হলে 2-approximation-এর উত্তর n − 2 পর্যন্ত হতে পারে, তখন complement-এ independent set মাত্র ২টি vertex-এর, অথচ সেরাটি n/2 + 1. যোগ-বিয়োগে ratio রক্ষা হয় না।

Knapsack-এর বিশেষত্ব হলো তার কঠিনতা পুরোপুরি বড় সংখ্যায়; সংখ্যাগুলো ছোট হলে pseudo-polynomial DP নির্ভুল। গোল করে সংখ্যা ছোট করলে একটি ছোট, নিয়ন্ত্রিত ক্ষতি হয়: এটিই FPTAS. Clique-এর কঠিনতা সংখ্যায় নয়, গঠনে; সেখানে PCP theorem-ভিত্তিক gap দেখায়, প্রায় পুরো পরিসরই কঠিন।

ঐতিহাসিকভাবে David Johnson ১৯৭৪ সালের প্রবন্ধে প্রথম এই ভিন্নতা পরিষ্কারভাবে দেখান, আর প্রশ্ন তোলেন কোন বৈশিষ্ট্য সমস্যাগুলোকে আলাদা করে। প্রায় দুই দশক পরে PCP theorem তার অনেকটা উত্তর দেয়। এই কারণে approximation-এর জন্য বিশেষ reduction লাগে (L-reduction, PTAS reduction), যা মূল্যের অনুপাতও রক্ষা করে।

মূল উপলব্ধি: NP-completeness শুধু নির্ভুল উত্তরের কঠিনতা মাপে; approximation-এর জগতে সমস্যাগুলো FPTAS থেকে n1−δ পর্যন্ত বিস্তৃত, আর সেই ভিন্নতা ধরতে ratio-রক্ষাকারী reduction আর gap দরকার।

প্র ০২“একটি প্রমাণের মাত্র কয়েকটি বিট পড়েই তার সঠিকতা যাচাই” কথাটি প্রায় অসম্ভব শোনায়। PCP theorem কীভাবে এটি সম্ভব করে, আর ইতিহাসে এটি কোথা থেকে এল?

সাধারণ প্রমাণে একটি ভুল একটি জায়গায় থাকে; একটি লাইন ভুল হলে বাকি সব ঠিক দেখায়, আর random স্পট-চেক তা প্রায় কখনো পায় না। Stepper-এর delivery-slot প্রমাণে নয়টির মধ্যে একটি সংঘাতই ভাঙা ছিল, তাই এক চেকে ধরার সম্ভাবনা 1/9. PCP theorem-এর মূল কৌশল প্রমাণটিকে এমন একটি “অতিরিক্ত” রূপে লেখা, যেখানে একটি স্থানীয় ভুল সারা প্রমাণে অসংগতি ছড়িয়ে দেয়। এটি error-correcting code-এর ধারণা: একটি বার্তাকে এমনভাবে লম্বা করা যে কয়েকটি বিট বদলালেও মূল বার্তা চেনা যায়, আর একটি বৈধ codeword থেকে দূরের কিছু হলে তা অনেক জায়গায় ধরা পড়ে।

ইতিহাসটি interactive proof থেকে আসে (পর্ব ৭৪-এ বিস্তারিত)। ১৯৯০ সালের দিকে Lund, Fortnow, Karloff, Nisan আর Shamir-এর কাজ দেখায়, বহুপদীর random বিন্দুতে মান মেলানো (arithmetization) কতটা শক্তিশালী। Babai, Fortnow আর Lund ১৯৯১ সালে MIP = NEXP প্রমাণ করেন, যা “বড় প্রমাণের অল্প অংশ পড়া”-র প্রথম শক্ত রূপ। একই বছরে Feige, Goldwasser, Lovász, Safra আর Szegedy দেখান, এমন verifier থেকে clique-এর approximation-এর কঠিনতা আসে। ১৯৯২ সালে Arora–Safra আর Arora–Lund–Motwani–Sudan–Szegedy চূড়ান্ত রূপটি প্রমাণ করেন। ২০০১ সালে এই ধারার কয়েকজন গবেষক যৌথভাবে Gödel Prize পান বলে জানা যায়।

প্রমাণটি দীর্ঘ আর বীজগাণিতিক, low-degree polynomial testing আর proof composition-এর ওপর দাঁড়ানো। Irit Dinur-এর ২০০৬–০৭ সালের প্রমাণ অন্য পথে যায়: একটি ছোট gap নিয়ে শুরু করে graph-এর expander গঠন ব্যবহার করে ধাপে ধাপে gap দ্বিগুণ করা, যতক্ষণ না তা ধ্রুবক হয়। এটি অনেক শিক্ষার্থীর কাছে বেশি স্বাভাবিক লাগে।

একটি সতর্কতা: PCP theorem দাবি করে না যে সাধারণ গণিতবিদের লেখা প্রমাণ কয়েক লাইন দেখে যাচাই করা যায়। প্রমাণটিকে আগে একটি formal, encode করা রূপে লিখতে হয়, যা polynomial গুণ লম্বা।

মূল উপলব্ধি: PCP theorem-এর রহস্য redundancy: প্রমাণকে error-correcting ধাঁচে লিখলে প্রতিটি ভুল বহু জায়গায় দৃশ্যমান হয়, আর তখন ধ্রুবক সংখ্যক random চেকই যথেষ্ট।

প্র ০৩Unique Games Conjecture কী, আর একটি অপ্রমাণিত অনুমান কেন approximation তত্ত্বে এত গুরুত্বপূর্ণ হয়ে উঠল?

PCP theorem ও Håstad-এর কাজ কিছু সমস্যায় (MAX-3SAT, MAX-CLIQUE) জানা algorithm আর কঠিনতার সীমা মিলিয়ে দেয়। কিন্তু vertex cover-এ algorithm ২-এ আটকে, আর কঠিনতা অনেক নিচে। MAX-CUT-এ Goemans আর Williamson ১৯৯৪–৯৫ সালে semidefinite programming দিয়ে প্রায় ০.৮৭৮ অংশের নিশ্চয়তা দেন, আর এই অদ্ভুত ধ্রুবকটি সেরা কি না, কেউ জানত না।

Subhash Khot ২০০২ সালে একটি নির্দিষ্ট gap problem প্রস্তাব করেন। “Unique game”-এ প্রতিটি constraint দুটি চলকের মধ্যে, আর একটির মান বসালে অন্যটির মান ঠিক একটিই হয় (একটি permutation). এমন সমস্যায় সবকিছু সত্য হলে তা সহজেই বের করা যায়; অনুমানটি বলে, “প্রায় সব constraint সত্য” আর “প্রায় কিছুই সত্য নয়” আলাদা করা NP-hard. এটি শুনতে নিরীহ, কিন্তু এর পরিণাম বিস্তৃত: vertex cover-এ 2 − δ NP-hard (Khot–Regev ২০০৮), MAX-CUT-এ Goemans–Williamson-এর ধ্রুবকই সেরা (Khot, Kindler, Mossel, O'Donnell ২০০৭), আর Raghavendra (২০০৮) দেখান, সব constraint satisfaction সমস্যায় একটি স্বাভাবিক SDP algorithm-ই সর্বোত্তম।

অর্থাৎ একটি অনুমান একসঙ্গে বহু খোলা প্রশ্নের “উত্তর” দেয়, আর উত্তরগুলো জানা algorithm-এর সঙ্গে নিখুঁতভাবে মেলে। এই সামঞ্জস্যই অনেককে অনুমানটির প্রতি আস্থা দেয়। অন্যদিকে Arora, Barak আর Steurer ২০১০ সালের দিকে unique games-এর জন্য একটি subexponential algorithm দেন, যা দেখায় সমস্যাটি সাধারণ NP-complete সমস্যার মতো “পুরো সূচকীয়” কঠিন নয়; এতে কিছু সংশয়ও জন্মায়। ২০১৮ সালে Khot, Minzer, Safra (Dinur আর Kindler-এর সঙ্গে যৌথ কাজের ধারায়) 2-to-2 games theorem প্রমাণ করেন, যা UGC-র একটি দুর্বল রূপ আর এর প্রতি আস্থা বাড়িয়েছে বলে মনে করা হয়।

পরীক্ষায় বা লেখায় সতর্ক থাকুন: “UGC সত্য হলে” না লিখে 2 − δ-কে প্রমাণিত বলা ভুল।

মূল উপলব্ধি: UGC একটি অপ্রমাণিত কিন্তু ফলপ্রসূ অনুমান: এটি সত্য হলে বহু সমস্যার সঠিক approximation সীমা জানা algorithm-এর সঙ্গে মিলে যায়, আর সেই কারণেই এটি তত্ত্বের কেন্দ্রে।

প্র ০৪বাজারঘরের delivery দলে একজন বলেন “approximation ratio-র কী দরকার, heuristic তো বাস্তবে আরও ভালো উত্তর দেয়।” তত্ত্ব আর বাস্তবের এই টানাপোড়েন কীভাবে মেলাবেন?

কথাটি অর্ধেক সত্য। এই পর্বের networkx run-এ Christofides গড়ে সেরার মাত্র ৫.৭% বেশি দিয়েছে, যেখানে নিশ্চয়তা ৫০%; knapsack FPTAS ε = 0.9-এ ৯৯.৯৩% দিয়েছে। আর বাস্তবের রুটিং সফটওয়্যার প্রায়ই local search (2-opt, Lin–Kernighan ধাঁচের) বা solver ব্যবহার করে, যাদের কোনো worst-case ratio প্রমাণিত নয়, অথচ উত্তর প্রায়ই খুব ভালো।

তবুও ratio-র তিনটি কাজ আছে। প্রথমত, এটি নিশ্চয়তা দেয় যখন instance অপরিচিত, অস্বাভাবিক বা প্রতিপক্ষ-নির্মিত; heuristic-এর খারাপ দিন হঠাৎ আসে আর তা আগে থেকে জানা যায় না। দ্বিতীয়ত, ratio-প্রমাণের নিম্নসীমা নিজেই কাজের। MST ≤ OPT মানে প্রতিটি দিনের রুটের পাশে একটি সংখ্যা রাখা যায়: “আজকের রুট MST-এর ১.২ গুণ, তাই সেরার বড়জোর ২০% বেশি।” Integer programming-এ LP relaxation একই কাজ করে; বাস্তবের solver এভাবেই “optimality gap” জানায়। এটি a posteriori নিশ্চয়তা: প্রতিটি নির্দিষ্ট instance-এ আলাদাভাবে হিসাব করা।

তৃতীয়ত, inapproximability বলে কোথায় চেষ্টা থামাতে হবে। সাধারণ TSP-এর দূরত্ব যদি triangle inequality না মানে (একমুখী রাস্তা, ফেরির সময়সূচি, টোল), তাহলে কোনো algorithm সব instance-এ ধ্রুবক নিশ্চয়তা দিতে পারবে না, যদি না P = NP; তখন সমস্যার কাঠামো বদলানোর কথা ভাবা যুক্তিসংগত, যেমন দূরত্বকে shortest-path দূরত্ব দিয়ে বদলে metric বানানো। একইভাবে MAX-3SAT-এর ক্ষেত্রে random assignment-এর ৭/৮-এর চেয়ে ভালো worst-case নিশ্চয়তা চাওয়া অর্থহীন।

তাই পরিণত পথ হলো দুটি একসঙ্গে: প্রমাণিত algorithm দিয়ে একটি নিরাপদ শুরু আর নিম্নসীমা, তার ওপর heuristic দিয়ে উন্নতি, আর প্রতিটি উত্তরকে নিম্নসীমার সঙ্গে মিলিয়ে দেখা।

মূল উপলব্ধি: Approximation ratio বাস্তবের গড় ফল মাপে না, worst-case বীমা দেয়; তার নিম্নসীমাগুলো প্রতিটি instance-এ মান যাচাইয়ের হাতিয়ার, আর inapproximability বলে কোন লক্ষ্য অর্থহীন।

প্র ০৫Metric TSP-এ Christofides-এর ৩/২ প্রায় ৪৫ বছর অপরাজিত ছিল, অথচ সমতলের TSP-এর PTAS আছে। এই দুই ফলের মাঝে কী পার্থক্য, আর ২০২০-এর উন্নতি কী শেখায়?

Euclidean TSP-এ শহরগুলো সমতলের বিন্দু, দূরত্ব সরলরেখার। Sanjeev Arora ১৯৯৬ সালে, আর Joseph Mitchell স্বাধীনভাবে, এর জন্য PTAS দেন: যেকোনো ε-এর জন্য (1 + ε)-approximation. মূল ধারণা জ্যামিতিক: সমতলকে বারবার চার ভাগে ভাগ করা (quadtree), আর দেখানো যে একটি প্রায়-সেরা tour প্রতিটি বর্গের সীমানা অল্প কয়েকটি নির্দিষ্ট বিন্দু দিয়ে পার হয়; তারপর dynamic programming. Euclidean TSP strongly NP-hard বলে এর FPTAS নেই, যদি না P = NP, তাই PTAS-ই সর্বোচ্চ আশা।

সাধারণ metric-এ এই জ্যামিতি নেই। আর PCP-ভিত্তিক ফল দেখায় metric TSP APX-hard: ২০১৫ সালের একটি কাজ অনুযায়ী ১২৩/১২২-এর চেয়ে ভালো ratio NP-hard, যদি না P = NP. তাই metric TSP-এর PTAS নেই, আর আসল প্রশ্ন হলো ১.৫ আর প্রায় ১.০০৮-এর মাঝে সত্যিকারের সীমা কোথায়। বহু গবেষক অনুমান করেন ৪/৩ সম্ভব হতে পারে, কারণ একটি স্বাভাবিক LP relaxation-এর integrality gap ৪/৩ বলে অনুমান করা হয়, কিন্তু তা প্রমাণিত নয়।

২০২০ সালে Karlin, Klein আর Oveis Gharan একটি randomized algorithm দেন, যার ratio ৩/২-এর চেয়ে একটি অতি ক্ষুদ্র ধ্রুবক কম বলে প্রমাণিত (প্রকাশিত মান প্রায় 10−36 মাপের)। বাস্তবে এই উন্নতির কোনো প্রভাব নেই, কিন্তু তত্ত্বে এটি গুরুত্বপূর্ণ: এটি দেখায় ৩/২ কোনো “প্রাকৃতিক দেয়াল” নয়, আর ব্যবহৃত কৌশল (random spanning tree, polynomial-এর geometry) নতুন পথ খোলে। Serdyukov-এর সমান্তরাল আবিষ্কারের গল্পটিও শিক্ষণীয়: একই ফল সোভিয়েত ইউনিয়নে প্রায় একই সময়ে প্রকাশিত হয়েছিল, কিন্তু ভাষা ও যোগাযোগের বাধায় দীর্ঘদিন পশ্চিমে অজানা ছিল।

মূল উপলব্ধি: সমস্যার কাঠামো (সমতলের জ্যামিতি বনাম সাধারণ metric) approximation-এর সম্ভাবনা বদলে দেয়; metric TSP-এর ১.৫ আর ১২৩/১২২-এর মাঝের ফাঁক আজও খোলা, আর ক্ষুদ্র তাত্ত্বিক উন্নতিও নতুন কৌশলের দরজা খোলে।

অনুশীলন

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

  1. নকশা (reduction): HAMCYCLE থেকে TSP-এ এমন একটি reduction নকশা করুন, যেখানে প্রতিটি দূরত্ব 1 বা 2. দেখান যে এই instance triangle inequality মানে। তারপর এ থেকে প্রমাণ করুন: metric TSP-এর কোনো FPTAS নেই, যদি না P = NP.

    Reduction: d(u, v) = 1 যদি {u, v} ∈ E, নইলে 2. Triangle inequality: যেকোনো তিন শহরে d(u, w) ≤ 2 ≤ 1 + 1 ≤ d(u, v) + d(v, w), কারণ প্রতিটি দূরত্ব অন্তত 1 আর বড়জোর 2. Hamiltonian cycle থাকলে OPT = n; না থাকলে প্রতিটি tour অন্তত একটি 2 নেয়, তাই OPT ≥ n + 1.

    এখন ধরুন একটি FPTAS আছে। ε = 1/(n + 1) নিন; সময় poly(n, 1/ε) = poly(n). উত্তর ≤ (1 + ε) · OPT. Cycle থাকলে উত্তর ≤ n(1 + 1/(n + 1)) = n + n/(n + 1) < n + 1; না থাকলে উত্তর ≥ OPT ≥ n + 1. তাই “উত্তর < n + 1?” HAMCYCLE মীমাংসা করে, ফলে P = NP. ∎ (এটি অংশ ৫-এর সাধারণ যুক্তির বিশেষ রূপ: এখানে OPT ≤ 2n, সংখ্যাগুলো ছোট, তাই সমস্যাটি strongly NP-hard.) লক্ষ করুন, এই reduction ধ্রুবক-ratio-কে বাদ দেয় না, কারণ ফাঁক মাত্র (n + 1)/n.

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: independent set-এর 2-approximation আছে। প্রমাণ: matching algorithm দিয়ে একটি vertex cover C নিন, |C| ≤ 2 · OPTVC. V − C একটি independent set. যেহেতু C সেরার দ্বিগুণের মধ্যে, তার complement-ও সেরার দ্বিগুণের মধ্যে, তাই OPTIS ≤ 2 · |V − C|. ∎” ভুলটি কোথায়? একটি পাল্টা উদাহরণ দিন।

    V − C সত্যিই একটি independent set; ভুল শেষ বাক্যে। Ratio গুণের সম্পর্ক, আর complement নেওয়া বিয়োগ: |V − C| = n − |C| ≥ n − 2 · OPTVC, যা শূন্য বা ঋণাত্মকও হতে পারে। গুণের নিশ্চয়তা বিয়োগে টেকে না।

    পাল্টা উদাহরণ: পাঁচটি আলাদা edge-এর graph (n = 10). matching algorithm দশটি vertex-ই নেয় (vc_ratio.py-র শেষ লাইন), তাই V − C = ∅, আকার 0. অথচ প্রতি edge থেকে একটি করে নিলে আকার ৫-এর independent set আছে। Ratio অসীম। আসলে P ≠ NP হলে independent set-এর n1−δ-এর চেয়ে ভালো approximation নেই (ভাবনার প্রশ্ন ১)।

  3. হিসাব (trace): U = {1, 2, 3, 4, 5, 6}; উপসেট A = {1, 2, 3}, B = {4, 5, 6}, C = {1, 2, 4, 5}. Greedy set cover চালান (সমান হলে তালিকার আগেরটি)। ALG, OPT আর H(d) · OPT সীমা কত? Ratio কত?

    ধাপ ১: A ৩টি, B ৩টি, C ৪টি নতুন উপাদান দেয়; C নেওয়া হয়। বাকি {3, 6}. ধাপ ২: A আর B দুটিই ১টি করে দেয়; সমান, তাই A. বাকি {6}. ধাপ ৩: B. ALG = 3 (C, A, B).

    OPT = 2 ({A, B}); একটি উপসেট দিয়ে হয় না, কারণ কোনোটিই ছয়টি উপাদান রাখে না। d = 4, H(4) = 1 + 1/2 + 1/3 + 1/4 = 25/12 ≈ 2.083, তাই সীমা H(4) · 2 ≈ 4.17, আর ALG = 3 তার মধ্যে। Ratio 3/2 = 1.5. এটি greedy_cover.py-র k = 2 থেকে আলাদা ছোট উদাহরণ, scratch-এ brute force দিয়ে মেলানো।

  4. প্রমাণ: একটি 3CNF সূত্রে m টি clause, প্রতিটিতে তিনটি আলাদা চলকের literal. প্রমাণ করুন এমন একটি assignment আছে যা অন্তত 7m/8 টি clause সত্য করে। এ থেকে দেখান MAX-3SAT ∈ APX, ratio 8/7.

    প্রতিটি চলককে স্বাধীনভাবে সম্ভাবনা 1/2-এ সত্য বসান। একটি clause-এর তিনটি literal আলাদা চলকের, তাই তিনটি একসঙ্গে মিথ্যা হওয়ার সম্ভাবনা (1/2)3 = 1/8; clause সত্য হওয়ার সম্ভাবনা 7/8. Clause i-এর জন্য indicator Xi নিন; প্রত্যাশার রৈখিকতায় E[Σ Xi] = 7m/8. একটি random চলকের প্রত্যাশা 7m/8 হলে তার অন্তত একটি মান ≥ 7m/8 (সব মান কম হলে গড়ও কম হতো)। তাই এমন assignment আছে। ∎

    Algorithm চাই, শুধু অস্তিত্ব নয়: চলক x1, x2, … একে একে বসান; প্রতিবার দুটি মানের জন্য বাকি random অংশের শর্তসাপেক্ষ প্রত্যাশা (প্রতিটি clause-এর জন্য সহজ সূত্র, polynomial সময়ে) হিসাব করে বড়টি নিন। প্রত্যাশা কখনো কমে না, তাই শেষে ≥ 7m/8 টি সত্য clause. যেহেতু OPT ≤ m, তাই OPT ≤ m ≤ (8/7) · ALG: ratio ρ = 8/7, ধ্রুবক, তাই MAX-3SAT ∈ APX. Håstad দেখান P ≠ NP হলে এর চেয়ে ভালো ধ্রুবক নেই।

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

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

ক্রম“সাধারণ TSP-এর কোনো ধ্রুবক ρ-approximation নেই, যদি না P = NP” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ধরে নেওয়া হয় একটি polynomial সময়ের ρ-approximation algorithm A আছে
  2. HAMCYCLE-এর graph G থেকে TSP instance: edge-এর দূরত্ব 1, অন্য জোড়ার দূরত্ব ρn + 1
  3. G-এ Hamiltonian cycle থাকলে OPT = n, তাই A-এর উত্তর ≤ ρn
  4. না থাকলে প্রতিটি tour > ρn, তাই A-এর উত্তরও > ρn
  5. “A-এর উত্তর ≤ ρn?” দিয়ে HAMCYCLE polynomial সময়ে মীমাংসা হয়, তাই P = NP

একটি maximisation সমস্যায় একটি polynomial সময়ের algorithm প্রতিটি input-এ সেরা মূল্যের অন্তত 3/4 অংশ দেয়। ρ ≥ 1 নিয়মে (maximisation-এ OPT ≤ ρ · ALG) এর approximation ratio কত?

  • 3/4
  • 1/4
  • 4/3
  • 2

Vertex cover-এর matching-ভিত্তিক algorithm-এর প্রমাণে “যেকোনো vertex cover-এর আকার ≥ |M|” কেন সত্য, যেখানে M একটি maximal matching?

  • M-এর edge-গুলো কোনো vertex ভাগ করে না, আর প্রতিটির একটি প্রান্ত cover-এ থাকতেই হয়
  • M maximal, তাই M-এর বাইরে কোনো edge নেই
  • M graph-এর সব vertex ছোঁয়
  • Algorithm-এর উত্তর ঠিক |M|

একটি algorithm-পরিবার যেকোনো ε > 0-এ (1 + ε)-approximation দেয়, সময় O(n1/ε)। এটি কী?

  • FPTAS
  • PTAS, কিন্তু FPTAS নয়
  • শুধু একটি ধ্রুবক-ratio algorithm, তাই APX-এর সাধারণ সদস্য
  • কোনো approximation scheme নয়, কারণ সময় সূচকীয়

সাধারণ TSP (triangle inequality ছাড়া) সম্পর্কে কোন বক্তব্যটি সঠিক?

  • Christofides algorithm এখানেও 1.5-approximation
  • কোনো ধ্রুবক ratio-র algorithm নেই, শর্তহীনভাবে প্রমাণিত
  • শুধু ρ < 2-এর জন্য approximation অসম্ভব
  • P ≠ NP হলে কোনো ধ্রুবক ρ-এর polynomial সময়ের ρ-approximation নেই

PCP theorem-এর সঠিক বক্তব্য কোনটি?

  • NP = PCP(O(log n), O(1))
  • NP = PCP(0, poly(n)), আর এটিই উপপাদ্যের নতুনত্ব
  • Post correspondence problem NP-complete
  • P = PCP(O(log n), O(1))

MAX-3SAT (প্রতিটি clause-এ তিনটি আলাদা চলক) সম্পর্কে কোনটি সঠিক?

  • এর একটি PTAS আছে
  • এর কোনো ধ্রুবক-ratio algorithm জানা নেই
  • Random assignment 7/8 অংশ দেয়, আর P ≠ NP হলে এর চেয়ে ভালো ধ্রুবক অসম্ভব
  • প্রতিটি satisfiable সূত্রে polynomial সময়ে সব clause সত্য করা যায়

একটি সমস্যা strongly NP-hard আর তার মূল্য পূর্ণসংখ্যা, OPT ≤ input-এর polynomial (সংখ্যাগুলো unary ধরে)। কোনটি সঠিক?

  • এর কোনো PTAS থাকতে পারে না
  • এর FPTAS নেই, যদি না P = NP
  • Knapsack-এর মতো এরও FPTAS আছে
  • এটি APX-এর বাইরে

শব্দকোষ

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

মনে রাখুন

  1. Approximation ratio ρ ≥ 1: minimisation-এ ALG ≤ ρ·OPT, maximisation-এ OPT ≤ ρ·ALG, প্রতিটি input-এ। প্রমাণের চাবি OPT-এর একটি নিম্নসীমা।
  2. Vertex cover: maximal matching-এ ২ (tight). Set cover: greedy-তে H(d) ≤ 1 + ln n, আর লগারিদমিক ক্ষতি অনিবার্য। Metric TSP: MST-দ্বিগুণে ২, Christofides-এ ১.৫.
  3. Knapsack-এর FPTAS মান গোল করে, সময় O(n3/ε)। FPTAS ⊆ PTAS ⊆ APX ⊆ NPO; strongly NP-hard হলে FPTAS নেই, যদি না P = NP.
  4. Gap reduction: “হ্যাঁ” আর “না” instance-এর OPT-এর মাঝে চওড়া ফাঁক। সাধারণ TSP-এ কোনো ধ্রুবক ratio নেই, যদি না P = NP.
  5. PCP theorem: NP = PCP(O(log n), O(1)); সমতুল্যভাবে GAP-3SAT একটি ধ্রুবক ফাঁকে NP-hard. Håstad: MAX-3SAT-এ ৭/৮-এর চেয়ে ভালো NP-hard. UGC খোলা অনুমান।

পরের পর্বে: কঠিন সমস্যার আরেকটি পথ: সূচকীয় অংশটিকে একটি ছোট parameter k-তে আটকে রাখা। Parameterized complexity, FPT, kernel, আর ETH ও SETH থেকে আসা fine-grained সীমা (পর্ব ৭২)।

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

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