পলিনমিয়াল-টাইম রিডাকশন ও NP-কমপ্লিটনেস

১ · পলিনমিয়াল-টাইম রিডাকশন

M9/L40-এ আমরা দেখেছি একটি সমস্যাকে আরেকটি সমস্যায় "রূপান্তর" (রিডিউস) করে আনডিসাইডেবিলিটি প্রমাণ করা যায় — এখানে একই গঠন ব্যবহার করা হবে, কিন্তু একটি গুরুত্বপূর্ণ অতিরিক্ত শর্তসহ। ল্যাঙ্গুয়েজ $A$ পলিনমিয়াল সময়ে ল্যাঙ্গুয়েজ $B$-তে রিডিউস করে ($A \leq_p B$ লেখা হয়) যদি একটি পলিনমিয়াল-সময়ে-গণনাযোগ্য ফাংশন $f$ থাকে, যাতে —

$$w \in A \iff f(w) \in B$$

সরাসরি, গুরুত্বপূর্ণ পরিণতি — যদি $A \leq_p B$ হয় এবং $B \in \mathrm{P}$ হয়, তাহলে $A \in \mathrm{P}$-ও (প্রথমে $f$ দিয়ে $w$-কে রূপান্তর করে, তারপর $B$-এর পলিনমিয়াল অ্যালগরিদম চালিয়ে $A$ সমাধান করা যায় — দুটো পলিনমিয়ালের composition এখনও পলিনমিয়াল, তাই মোট সময়ও পলিনমিয়াল)। এই একটি সাধারণ সত্যই সমস্যাগুলোর আপেক্ষিক কঠিনতা তুলনা করার প্রধান টুল।

২ · NP-হার্ড ও NP-কমপ্লিট

একটি ল্যাঙ্গুয়েজ $B$ NP-হার্ড যদি NP-এর প্রতিটি ল্যাঙ্গুয়েজ $A$-এর জন্য $A \leq_p B$ হয় — অর্থাৎ $B$ "NP-এর প্রতিটি সমস্যার চেয়ে অন্তত ততটাই কঠিন।" গুরুত্বপূর্ণভাবে, $B$ নিজে NP-তে থাকা এখানে বাধ্যতামূলক নয়।

একটি ল্যাঙ্গুয়েজ NP-কমপ্লিট যদি এটি একই সাথে NP-তে এবং NP-হার্ড — এই সংমিশ্রণটিই এই পাঠের কেন্দ্রীয় লক্ষ্য। এর সরাসরি, গুরুত্বপূর্ণ পরিণতি — যদি যেকোনো একটি NP-কমপ্লিট সমস্যা P-তে প্রমাণিত হয়, তাহলে NP-এর প্রতিটি সমস্যাও P-তে হয়ে যাবে (কারণ প্রতিটি NP সমস্যা তাতে রিডিউস করা যায়) — অর্থাৎ $\mathrm{P} = \mathrm{NP}$। ঠিক এই কারণেই NP-কমপ্লিট সমস্যাগুলো P-vs-NP প্রশ্নের (L49) স্বাভাবিক আক্রমণ-বিন্দু — এরা এক অর্থে NP-এর "সবচেয়ে কঠিন" সমস্যা, প্রমাণযোগ্যভাবে।

৩ · একটি সত্যিকারের রিডাকশন — ইনডিপেন্ডেন্ট সেট ↔ ভার্টেক্স কভার

একটি গ্রাফ $G=(V,E)$-তে ইনডিপেন্ডেন্ট সেটIndependent Setভার্টেক্সের এমন একটি সেট যাদের মধ্যে কোনো দুটি ভার্টেক্সই একটি এজ দিয়ে সংযুক্ত নয় হলো ভার্টেক্সের একটি সেট $S$ যাদের মধ্যে কোনো দুটিই একটি এজ দিয়ে সংযুক্ত নয়। একটি ভার্টেক্স কভারVertex Coverভার্টেক্সের এমন একটি সেট যাতে গ্রাফের প্রতিটি এজের অন্তত একটি প্রান্ত-বিন্দু সেটে থাকে হলো ভার্টেক্সের একটি সেট $C$ যাতে প্রতিটি এজের অন্তত একটি প্রান্ত-বিন্দু $C$-তে থাকে। একটি সুন্দর, প্রমাণযোগ্য সত্য — $S$ একটি ইনডিপেন্ডেন্ট সেট যদি এবং শুধু যদি $V - S$ (এর পরিপূরক) একটি ভার্টেক্স কভার হয়। তাই রিডাকশনটি খুবই সরল — একই গ্রাফ রেখে দিয়ে, "size-$k$ ইনডিপেন্ডেন্ট সেট আছে কি?" প্রশ্নকে "size-$(n-k)$ ভার্টেক্স কভার আছে কি?" প্রশ্নে রূপান্তর করা, যেখানে $n = |V|$।

# ইনডিপেন্ডেন্ট সেট -> ভার্টেক্স কভার: একটি সত্যিকারের পলিনমিয়াল-টাইম রিডাকশন
# (রিডাকশনের ফাংশনটি নিজে O(1) -- শুধু k -> n-k বদলায়, গ্রাফ অপরিবর্তিত থাকে)

import itertools

def has_independent_set(vertices, edges, k):
    # ব্রুট-ফোর্স ডিসাইডার: size-k ইনডিপেন্ডেন্ট সেট আছে কি না
    for subset in itertools.combinations(vertices, k):
        s = set(subset)
        if all(not (u in s and v in s) for (u, v) in edges):
            return True, s
    return False, None

def has_vertex_cover(vertices, edges, k):
    # ব্রুট-ফোর্স ডিসাইডার: size-k ভার্টেক্স কভার আছে কি না
    for subset in itertools.combinations(vertices, k):
        s = set(subset)
        if all(u in s or v in s for (u, v) in edges):
            return True, s
    return False, None

def reduce_independent_set_to_vertex_cover(vertices, edges, k):
    # পলিনমিয়াল-টাইম রিডাকশন f: গ্রাফ অপরিবর্তিত, শুধু টার্গেট size n-k -- O(1)
    n = len(vertices)
    return vertices, edges, n - k

# টেস্ট গ্রাফ: একটি পাঁচ-নোডের path graph 0-1-2-3-4
vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
n = len(vertices)

print(f"{'k':>3} | {'independent_set(k) আছে?':>26} | {'vertex_cover(n-k) আছে?':>26} | {'মিলে গেছে?':>10}")
print("-" * 78)
for k in range(0, n + 1):
    is_exists, is_set = has_independent_set(vertices, edges, k)
    v2, e2, target = reduce_independent_set_to_vertex_cover(vertices, edges, k)
    vc_exists, vc_set = has_vertex_cover(v2, e2, target) if target >= 0 else (False, None)
    match = (is_exists == vc_exists)
    print(f"{k:>3} | {str(is_exists):>26} | {str(vc_exists) + f' (size {target})':>26} | {str(match):>10}")
    assert match, "রিডাকশনের দাবি ভঙ্গ হয়েছে!"

print()
print("সব k-এর জন্য independent_set(k) ঠিক ততক্ষণই True যতক্ষণ vertex_cover(n-k) True -- রিডাকশন সঠিক প্রমাণিত।")