Foundationপ্রথম নীতি থেকে
LEVEL 13লেসন ১০/২৩অ্যাডভান্সড১ ঘণ্টা ৫ মিনিট

Complexity Classes — P, NP, PSPACE: সমাধান খোঁজা বনাম যাচাই করা

Complexity Classes — P, NP, co-NP, PSPACE

সমাধান খুঁজে বের করা আর হাতে-পাওয়া সমাধান যাচাই করা — এই দুইয়ের মধ্যে পার্থক্যই P আর NP-কে আলাদা করে। Turing machine দিয়ে চারটা class-এর আনুষ্ঠানিক সংজ্ঞা, আর কেন তাদের মধ্যে সম্পর্কটা আজও পুরোপুরি অজানা।

এই লেসন শেষে আপনি পারবেন

  • P, NP, co-NP, PSPACE-এর আনুষ্ঠানিক সংজ্ঞা Turing machine দিয়ে দিতে পারবেন
  • NP-এর verifier-based সংজ্ঞা ব্যবহার করে একটা problem NP-তে আছে তা দেখাতে পারবেন
  • P ⊆ NP ⊆ PSPACE এবং P ⊆ co-NP containment hierarchy ব্যাখ্যা ও যুক্তি দিয়ে প্রতিষ্ঠা করতে পারবেন
  • একটা problem কোন class-এ পড়ে তা চিনে উপযুক্ত উদাহরণ বেছে নিতে পারবেন
  • কেন এই containment-গুলো strict কি না তা আজও অমীমাংসিত তা ব্যাখ্যা করতে পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

একটা ৯×৯ Sudoku গ্রিড কল্পনা করুন। কেউ আপনাকে একটা পূর্ণ, ভরা-গ্রিড দিয়ে বলল “এটা সমাধান”। যাচাই করতে আপনার কতক্ষণ লাগবে? প্রতিটা সারি, কলাম, আর ৩×৩ বাক্সে ১ থেকে ৯ একবার করে আছে কি না দেখা — কয়েক সেকেন্ডের কাজ, হাতে করলেও এক মিনিটের বেশি না। এখন উল্টো প্রশ্ন: খালি গ্রিড থেকে নিজে একটা সমাধান খুঁজে বের করুন। ছোট গ্রিডে সহজ, কিন্তু গ্রিডের আকার বাড়তে থাকলে (16×16, 25×25, …) সমাধান খোঁজার সময় বিস্ফোরকভাবে বাড়ে — যেখানে যাচাই করার সময় প্রায় একই হারে বাড়ে যেভাবে গ্রিডের আকার বাড়ে, খুব বেশি না।

এই অসামঞ্জস্যটা কাকতালীয় নয়। এটা computer science-এর সবচেয়ে গভীর কাঠামোগত সত্যের একটা প্রতিচ্ছবি: একটা সমাধান যাচাই করা প্রায়ই সেটা খুঁজে বের করার চেয়ে ভয়ানকভাবে সহজ।

চিন্তা করুন আরো কিছু উদাহরণ:

  • একটা বড় সংখ্যার মৌলিক উৎপাদক (prime factorization) খুঁজে বের করা কঠিন, কিন্তু কেউ দুটো উৎপাদক দিলে গুণ করে যাচাই করা তাৎক্ষণিক।
  • একটা graph-এ k রঙে রঙ করা যায় কি না খুঁজে বের করা কঠিন, কিন্তু একটা রঙ-করা assignment দেখে “কোনো দুই প্রতিবেশীর রঙ এক নয়” যাচাই করা তুচ্ছ।
  • একটা delivery route যেটা 1000 কিমি-এর কম, খুঁজে বের করা কঠিন, কিন্তু একটা প্রস্তাবিত route দেখে তার মোট দূরত্ব যোগ করে যাচাই করা সহজ।

এই লেসনে আমরা এই পর্যবেক্ষণটাকে আনুষ্ঠানিক করব। আমরা সংজ্ঞায়িত করব চারটা complexity class — P (দ্রুত সমাধানযোগ্য), NP (দ্রুত যাচাইযোগ্য), co-NP (দ্রুত প্রত্যাখ্যান-যাচাইযোগ্য), আর PSPACE (সীমিত মেমরিতে সমাধানযোগ্য, সময় যতই লাগুক)। আর আমরা দেখব কেন — যদিও এই সংজ্ঞাগুলো ৫০ বছরের বেশি পুরনো, আর হাজার হাজার গবেষক এর উপর কাজ করেছেন — আমরা এখনো জানি না এই class-গুলো আসলে আলাদা, নাকি গোপনে একই জিনিস।

মূল ধারণা

Decision problem — সবকিছু হ্যাঁ/না প্রশ্নে রূপান্তর

Complexity theory-তে সুবিধার জন্য প্রতিটা সমস্যাকে decision problem আকারে লেখা হয় — উত্তর সবসময় “হ্যাঁ” বা “না”। যেমন “এই graph-টার shortest path কত?” -এর বদলে “এই graph-এ s থেকে t পর্যন্ত k-এর কম দৈর্ঘ্যের একটা path আছে কি?” ব্যবহার করা হয়।

কেন এই রূপান্তর? কারণ optimization বা search version প্রায়ই decision version-এর polynomial সংখ্যক call-এই সমাধান করা যায় (binary search k-এর উপর) — তাই decision version নিয়ে কাজ করাই যথেষ্ট, আর tractability-র প্রশ্নটা পরিষ্কার থাকে।

আনুষ্ঠানিকভাবে, একটা decision problem হলো একটা language L ⊆ Σ* — সব বৈধ input string-এর মধ্যে যেগুলোর উত্তর “হ্যাঁ” তাদের সেট। “এই graph 3-রঙে রঙ করা যায় কি?” প্রশ্নটা তখন হয়ে যায়: “এই graph-এর encoding কি 3COLOR নামের language-এর সদস্য?”

P — যা দ্রুত সমাধান করা যায়

P হলো সেই সব language-এর class যেগুলো একটা deterministic Turing machine দ্বারা polynomial time-এ decide করা যায়।

P=⋃k≥1TIME(nk)\mathbf{P} = \bigcup_{k \ge 1} \mathrm{TIME}(n^k)

যেখানে TIME(f(n)) মানে: এমন সব language যার জন্য একটা deterministic TM আছে যা প্রতিটা দৈর্ঘ্য-n input-এ সর্বোচ্চ O(f(n)) ধাপে থেমে সঠিক উত্তর দেয় (accept/reject)।

k-এর উপর union নেওয়া হয় কারণ আমরা এই বলছি “কোনো না কোনো polynomial সময়ে” — n², n³, n¹⁰⁰ সবই P-তে, শুধু 2ⁿ বা n! নয়। এই সংজ্ঞাটা model-independent — একই class পাওয়া যায় যদি single-tape TM, multi-tape TM, বা RAM machine ব্যবহার করেন, কারণ এই মডেলগুলোর মধ্যে simulation-এর খরচ সবসময় polynomial (Level-এর আগের লেসনগুলোতে Church-Turing thesis-এর extended version এই দাবিই করে)।

P-এর সদস্য: sorting, shortest path (Dijkstra), matrix multiplication, linear programming, matching, 2-SAT, আর (একটা বিখ্যাত ২০০২-এর ফলাফল অনুযায়ী) primality testing — একটা সংখ্যা মৌলিক কি না তা polynomial সময়ে নির্ণয় করা যায় (AKS primality test), যদিও উৎপাদক বের করাটা এখনো কঠিন বলে বিশ্বাস করা হয়।

NP — যা দ্রুত যাচাই করা যায়

এখানেই মূল ধারণাটা আসে। NP (Nondeterministic Polynomial time)-এর দুইটা সমতুল্য সংজ্ঞা আছে — একটা মেশিন-কেন্দ্রিক, একটা verifier-কেন্দ্রিক। Verifier-কেন্দ্রিকটাই সাধারণত বেশি স্বজ্ঞাত।

Verifier সংজ্ঞা: একটা language L NP-তে আছে যদি একটা polynomial-time deterministic verifier V থাকে এবং একটা polynomial p থাকে যেন:

x∈L  ⟺  ∃ c, ∣c∣≤p(∣x∣):V(x,c) accept করেx \in L \iff \exists\, c,\ |c| \le p(|x|) : V(x, c) \text{ accept করে}

c-কে বলা হয় certificate (বা witness/proof)। মূল শর্তগুলো লক্ষ্য করুন:

  • c-এর দৈর্ঘ্য x-এর দৈর্ঘ্যের polynomial — সীমাহীন বড় certificate নয়
  • V নিজে polynomial time-এ চলে (x এবং c দুটোই ইনপুট হিসেবে পেয়ে)
  • x ∈ L হলে অন্তত একটা সঠিক certificate থাকবেই (completeness)
  • x ∉ L হলে কোনো certificate V-কে convince করতে পারবে না (soundness)

3COLOR-এর জন্য certificate হলো নিজেই একটা রঙ-assignment; V শুধু প্রতিটা edge-এর দুই প্রান্তের রঙ আলাদা কি না চেক করে — O(|V| + |E|) সময়ে, স্পষ্টতই polynomial।

co-NP — যা দ্রুত অস্বীকার-যাচাই করা যায়

প্রতিটা language L-এর একটা complement আছে: L̄ = Σ* \ L — যে সব string L-এ নেই। co-NP হলো সেই class যার complement NP-তে আছে:

co-NP={ L:Lˉ∈NP }\mathbf{co\text{-}NP} = \{\, L : \bar{L} \in \mathbf{NP} \,\}

স্বজ্ঞাতভাবে: NP-তে “হ্যাঁ” উত্তরের জন্য সংক্ষিপ্ত প্রমাণ (certificate) থাকে; co-NP-তে “না” উত্তরের জন্য সংক্ষিপ্ত প্রমাণ থাকে।

উদাহরণ — UNSAT: একটা Boolean formula φ কি unsatisfiable (কোনো assignment-এই true হয় না)? এটার জন্য সংক্ষিপ্ত “হ্যাঁ”-প্রমাণ দেওয়া কঠিন মনে হয় (সব 2ⁿ assignment-ই যে false করে তা দেখাতে হলে exponential তালিকা লাগে, মনে হয়)। কিন্তু SAT-এর (satisfiable কি না) জন্য certificate তুচ্ছ — একটা satisfying assignment দেখালেই হলো। তাই UNSAT-এর complement (SAT) NP-তে, ফলে সংজ্ঞা অনুযায়ী UNSAT ∈ co-NP।

আরেকটা ভালো উদাহরণ — tautology: একটা Boolean formula কি সব assignment-এই true হয়? এটাও co-NP-তে (প্রমাণ: UNSAT-এর মতোই, ¬φ-এর UNSAT-এর সমতুল্য)।

PSPACE — যা সীমিত মেমরিতে সমাধান করা যায়

PSPACE সময় নয়, space (মেমরি) সীমাবদ্ধ করে — সময় যতই লাগুক (এমনকি exponential), যদি মেমরি ব্যবহার polynomial-এর মধ্যে থাকে।

PSPACE=⋃k≥1SPACE(nk)\mathbf{PSPACE} = \bigcup_{k \ge 1} \mathrm{SPACE}(n^k)

SPACE(f(n)) মানে: এমন সব language যার জন্য একটা deterministic TM আছে যা প্রতিটা দৈর্ঘ্য-n input-এ কখনো O(f(n))-এর বেশি tape cell ব্যবহার করে না — সময়ের কোনো সীমা নেই।

স্বজ্ঞাত পার্থক্যটা গুরুত্বপূর্ণ: সময় জমা হয় (প্রতিটা ধাপ চিরস্থায়ীভাবে “খরচ” হয়ে যায়), কিন্তু space পুনর্ব্যবহার করা যায় (একটা tape cell লিখে আবার মুছে নতুন কিছু লেখা যায়)। এই একটা পার্থক্যই PSPACE-কে NP-এর চেয়ে আশ্চর্যজনকভাবে বড় ক্ষমতা দেয় — পরের অংশে দেখব ঠিক কীভাবে।

PSPACE-এর সদস্য: Quantified Boolean Formula (QBF/TQBF) — SAT-এরই একটা generalization যেখানে variable-গুলোর উপর ∃ আর ∀ উভয় quantifier থাকতে পারে (এবং এটা PSPACE-complete, পরের লেসনগুলোর ভাষায় PSPACE-এর “সবচেয়ে কঠিন” সমস্যা); generalized geography; polynomial-size বোর্ডের generalized chess/checkers/Go-এর মতো দুই-খেলোয়াড় game (কে জিতবে তা নির্ণয় করা)।

Containment hierarchy

এখন পর্যন্ত জানা সম্পর্কগুলো একসাথে দেখি:

P⊆NP⊆PSPACE⊆EXPTIME\mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} \subseteq \mathbf{EXPTIME}P⊆co-NP⊆PSPACE\mathbf{P} \subseteq \mathbf{co\text{-}NP} \subseteq \mathbf{PSPACE}
সম্পর্কপ্রমাণিত?কেন
P ⊆ NP✓ প্রমাণিতDeterministic TM নিজেই একটা (তুচ্ছ) verifier — certificate উপেক্ষা করে সরাসরি সিদ্ধান্ত নেয়
P ⊆ co-NP✓ প্রমাণিতP complement-এর অধীনে বদ্ধ (deterministic TM-এর accept/reject উল্টে দিলেই complement-এর TM)
NP ⊆ PSPACE✓ প্রমাণিতসব 2^{p(n)} সম্ভাব্য certificate একে একে চেষ্টা করা যায়, প্রতিবার একই space পুনর্ব্যবহার করে
co-NP ⊆ PSPACE✓ প্রমাণিতএকই যুক্তি — NP-এর প্রমাণ complement-এও খাটে, কারণ PSPACE complement-এর অধীনে বদ্ধ
P = NP?✗ অজানাএই module-এর কেন্দ্রীয় খোলা প্রশ্ন
NP = co-NP?✗ অজানাP = NP হলে এটাও সত্য হবে (যুক্তি নিচে), কিন্তু স্বাধীনভাবে খোলা
NP = PSPACE?✗ অজানাসত্য হলে P = NP-ও সত্য হবে (কারণ P ⊆ NP ⊆ PSPACE)
চারটা class-এর জানা containment — তীর মানে 'উপসেট', প্রশ্নবোধক মানে strict কি না অজানা।

একটা চমৎকার observation: যদি কখনো P = NP প্রমাণিত হয়, তাহলে সাথে সাথে NP = co-NP-ও প্রমাণিত হয়ে যাবে — বিনা বাড়তি কাজে। কারণ: P স্বভাবতই complement-এর অধীনে বদ্ধ (deterministic TM-এর accept আর reject অবস্থা উল্টে দিলেই complement-এর জন্য নতুন একটা deterministic TM পাওয়া যায়, তাই P = co-P সবসময় সত্য)। এখন P = NP ধরলে: NP = P = co-P = co-NP। এই ছোট্ট যুক্তিটা দেখায় class-গুলো কতটা আন্তঃসংযুক্ত — একটা সমতা প্রমাণিত হলে অন্যগুলোর উপর ডমিনো effect পড়ে। উল্টো দিকে, যদি কখনো দেখানো যায় NP ≠ co-NP, সেটাও স্বয়ংক্রিয়ভাবে P ≠ NP প্রমাণ করে দেবে — তাই NP বনাম co-NP প্রশ্নটাকে P বনাম NP-এর একটা সম্ভাব্য “সহজ দরজা” হিসেবেও দেখা হয়, যদিও এখনো কেউ এই দরজা খুলতে পারেননি।

ভেতরে কী ঘটছে

Nondeterministic Turing machine — ঠিক কীভাবে সংজ্ঞায়িত

NP-এর মূল সংজ্ঞা (ঐতিহাসিকভাবে, আর নামের উৎস) verifier দিয়ে নয় — একটা nondeterministic Turing machine (NTM) দিয়ে। দুটো সংজ্ঞা সমতুল্য, কিন্তু NTM-ভিত্তিক সংজ্ঞাটা বোঝা জরুরি কারণ এটাই PSPACE-এর সাথে সম্পর্ক বুঝতে সাহায্য করবে।

একটা deterministic TM-এর transition function প্রতিটা (state, tape symbol) জোড়ার জন্য ঠিক একটা পরবর্তী পদক্ষেপ বলে দেয়। একটা NTM-এ, transition function একটা সেট পদক্ষেপ বলে দিতে পারে — মেশিন “একই সাথে” সবগুলো branch অনুসরণ করে (কল্পনা করুন একটা ট্রি, যার প্রতিটা node একটা configuration, আর প্রতিটা সম্ভাব্য পরবর্তী পদক্ষেপ একটা child)। NTM একটা input accept করে যদি এই ট্রি-র অন্তত একটা path একটা accepting state-এ পৌঁছায়।

NP তখন সংজ্ঞায়িত হয়: এমন সব language যা কোনো NTM দ্বারা polynomial “সময়ে” (অর্থাৎ ট্রি-র প্রতিটা path polynomial দৈর্ঘ্যের) decide করা যায়।

কেন এটা verifier সংজ্ঞার সমতুল্য? একটা NTM-এর একটা accepting path-কে “certificate” হিসেবে ভাবুন — path-টা কোন branch বেছে নিল তার একটা রেকর্ড। Verifier V(x, c) তখন হয়: “certificate c অনুসরণ করে NTM চালাও (নির্দিষ্ট branch বেছে নিয়ে, তাই এখন deterministic), আর দেখো accept হয় কি না।” যেহেতু path-এর দৈর্ঘ্য polynomial, V-ও polynomial সময়ে চলে। বিপরীত দিকেও একইভাবে যায়: verifier থেকে NTM বানানো যায় — প্রতিটা সম্ভাব্য certificate-এর জন্য একটা branch, প্রতিটা branch-এ V simulate করা।

একটা NP সমস্যা — দুই সমতুল্য দৃষ্টি
  1. সমস্যা"এই graph কি 3-রঙে রঙ করা যায়?"
  2. NTM দৃষ্টিট্রি-র প্রতিটা branch একটা সম্ভাব্য রঙ-assignment গণনা করে চেষ্টা করে দেখে, যেকোনো একটা branch accept করলেই হ্যাঁ
  3. Verifier দৃষ্টিএকজন "সহায়ক" (oracle/prover) একটা রঙ-assignment certificate হিসেবে দেয়, V সেটা O(V+E) সময়ে চেক করে
  4. সমতুল্য কেনNTM-এর accepting branch-টাই সেই certificate — একটাকে অন্যটায় polynomial সময়ে রূপান্তর করা যায়

কেন NP ⊆ PSPACE — space পুনর্ব্যবহারের কৌশল

এটাই এই লেসনের সবচেয়ে গুরুত্বপূর্ণ “কেন”। ধরুন L ∈ NP, তাই একটা verifier V আছে certificate দৈর্ঘ্য p(n)-এর সাথে। একটা সরল deterministic algorithm (PSPACE-এর মধ্যে থেকেই) সমস্যাটা সমাধান করতে পারে:

সব সম্ভাব্য certificate c (দৈর্ঘ্য p(n)) লেক্সিকোগ্রাফিক ক্রমে:
    V(x, c) চালাও
    accept করলে → ACCEPT আর থামো
সবগুলো শেষ হলে → REJECT

এখানে certificate-এর সংখ্যা 2^{p(n)} — exponential। তাই এই algorithm-এর সময় exponential। কিন্তু space কত? প্রতিটা c চেক করার পর, পরের c-এর জন্য একই memory পুনর্ব্যবহার করা যায় — আগের c মুছে নতুন c লিখুন (একটা counter-এর মতো, p(n)-bit counter বাড়াতে থাকা)। V নিজেও polynomial space-এ চলে (polynomial সময়ে চলে মানে polynomial-এর বেশি tape ব্যবহারও করতে পারে না, কারণ প্রতিটা ধাপে সর্বোচ্চ একটা নতুন cell স্পর্শ করা যায়)।

মোট space: O(p(n)) (certificate রাখতে) + V-এর নিজের space (O(poly(n))) — দুটোই polynomial, তাই যোগফলও polynomial। সময়ের কোনো সীমা এখানে ধরা হয়নি — সেটাই আসলে exponential, কিন্তু PSPACE-এর সংজ্ঞা শুধু space-এর উপর শর্ত দেয়, সময়ের উপর নয়।

এইভাবেই NP ⊆ PSPACE — একটা algorithm যেটা exponential সময় নেয় কিন্তু মাত্র polynomial space, PSPACE-এর জন্য যথেষ্ট বৈধ।

Savitch’s theorem — একটা বিস্ময়কর bonus

PSPACE সংজ্ঞায়িত করা হয়েছে deterministic TM দিয়ে। কিন্তু ধরুন আমরা NPSPACE সংজ্ঞায়িত করি — nondeterministic TM, একই polynomial space সীমা দিয়ে (NP-এর মতো, কিন্তু সময়ের বদলে space সীমাবদ্ধ)। স্বজ্ঞাতভাবে মনে হতে পারে NPSPACE PSPACE-এর চেয়ে বড় হবে — ঠিক যেমন NP (সম্ভবত) P-এর চেয়ে বড়।

Savitch’s theorem (1970) প্রমাণ করে এটা ভুল:

NPSPACE=PSPACE\mathbf{NPSPACE} = \mathbf{PSPACE}

(আসলে আরো শক্তিশালী: যেকোনো f(n) ≥ \log n-এর জন্য \mathrm{NSPACE}(f(n)) \subseteq \mathrm{SPACE}(f(n)^2) — nondeterminism space-এ সরাতে গেলে সর্বোচ্চ বর্গ খরচ লাগে, আর polynomial-এর বর্গও polynomial।)

এই ফলাফলটা NP বনাম P-এর প্রশ্নের সাথে তীক্ষ্ণভাবে বৈসাদৃশ্যপূর্ণ: space-এ nondeterminism প্রায় “বিনামূল্যে” সরানো যায় (শুধু বর্গ খরচে), কিন্তু সময়ে nondeterminism সরাতে (এখনো জানা সেরা উপায়ে) exponential খরচ লাগে। এই অসামঞ্জস্যটাই আংশিকভাবে ব্যাখ্যা করে কেন P বনাম NP এত কঠিন প্রশ্ন, অথচ space-এর অনুরূপ প্রশ্ন (\mathrm{NPSPACE} বনাম \mathrm{PSPACE}) দশকের পর দশক আগেই সমাধান হয়ে গেছে।

Time hierarchy theorem — কিছু জিনিস আমরা জানি

সবকিছু অজানা নয়। Time hierarchy theorem (Hartmanis-Stearns, 1965) diagonalization দিয়ে প্রমাণ করে যে বেশি সময় সত্যিই বেশি ক্ষমতা দেয়:

TIME(f(n))⊊TIME(f(n)1+ϵ)\mathrm{TIME}(f(n)) \subsetneq \mathrm{TIME}(f(n)^{1+\epsilon})

যথেষ্ট “ভালো” (time-constructible) f আর যেকোনো \epsilon > 0-এর জন্য। এখান থেকে সরাসরি বেরিয়ে আসে:

P⊊EXPTIME\mathbf{P} \subsetneq \mathbf{EXPTIME}

— অর্থাৎ P আর EXPTIME নিশ্চিতভাবে আলাদা, প্রমাণিত, কোনো সন্দেহ নেই। তাহলে প্রশ্ন জাগে: এই \subsetneq-টা ঠিক কোথায় ঘটে? P আর NP-এর মাঝে? NP আর PSPACE-এর মাঝে? নাকি আরো পরে? আমরা জানি কোথাও একটা কঠোর পার্থক্য আছে চেইনের মধ্যে — কিন্তু ঠিক কোন ধাপে, তা আজও অজানা। এটাই এই পুরো ক্ষেত্রের হতাশা আর সৌন্দর্য একসাথে: আমরা জানি দেয়াল আছে, কিন্তু জানি না ঠিক কোথায়।

উদাহরণ

চারটা class, একটা করে concrete সমস্যা

Classসমস্যাকেন এই class-এ
P2-SAT: প্রতিটা clause-এ ঠিক ২টা literal-ওয়ালা CNF formula satisfiable কি নাImplication graph বানিয়ে strongly-connected-component দিয়ে O(n+m)-এ সমাধানযোগ্য
NP3-SAT: প্রতিটা clause-এ ঠিক ৩টা literal-ওয়ালা CNF formula satisfiable কি নাCertificate = একটা satisfying assignment, O(n)-এ যাচাই যোগ্য; সমাধান খোঁজার কোনো known polynomial উপায় নেই
co-NPTAUTOLOGY: একটা Boolean formula কি সব assignment-এ true“না” (তাউটোলজি নয়)-এর প্রমাণ একটা counter-example assignment; “হ্যাঁ”-এর জন্য কোনো ছোট certificate জানা নেই
PSPACETQBF: \exists x_1 \forall x_2 \exists x_3 \ldots \phi আকারের সম্পূর্ণ-quantified formula true কি নাRecursive minimax-এর মতো evaluate করা যায়, O(n) গভীরতা, প্রতি স্তরে space পুনর্ব্যবহার
প্রতিটা class-এর একটা প্রতিনিধিত্বকারী সমস্যা, আর কেন সেটা সেই class-এ পড়ে।

একটা সম্পূর্ণ ওয়ার্কড উদাহরণ — Subset Sum

SUBSET-SUM: সংখ্যার একটা সেট S = {s_1, \ldots, s_n} আর একটা target T দেওয়া আছে — S-এর একটা উপসেট আছে কি যার যোগফল ঠিক T?

ধরুন S = \{3, 7, 12, 19, 25, 31, 42\}, T = 50।

যাচাই (verifier) — দ্রুত: কেউ certificate দিল \{19, 31\}। যোগ করুন: 19 + 31 = 50 ✓। O(n) সময়ে যাচাই সম্পন্ন — শুধু একটা যোগ। এটাই SUBSET-SUM ∈ NP-এর সরাসরি প্রমাণ।

সমাধান (solver) — ধীর, naive পদ্ধতিতে: 7-টা সংখ্যার প্রতিটা উপসেট (2^7 = 128-টা) চেষ্টা করে দেখা লাগবে (যদি না কোনো চতুর কৌশল ব্যবহার করেন — dynamic programming দিয়ে O(n \cdot T)-এ করা যায় যখন T ছোট, কিন্তু T যদি n-এর সাপেক্ষে exponentially বড় হয়, তাহলে সেটাও exponential হয়ে যায়। এটাই SUBSET-SUM-কে “weakly NP-hard” বলার কারণ — পরের লেসনে এই সূক্ষ্মতা আসবে)।

7-টা সংখ্যায় 128-টা উপসেট এখনো তুচ্ছ। কিন্তু n = 50-এ 2^{50} \approx 10^{15} — সেকেন্ডে ১ বিলিয়ন উপসেট চেক করলেও প্রায় ১২ দিন লাগবে। n = 100-এ মহাবিশ্বের বয়সের চেয়ে বেশি সময় লাগবে naive brute force-এ।

এটাই মূল বার্তা: certificate যাচাই O(n)-এ, কিন্তু certificate খোঁজা (কোনো known ভালো কৌশল ছাড়া) O(2^n)-এ — একই সমস্যার দুই সম্পূর্ণ ভিন্ন সময়-জটিলতা, নির্ভর করছে আপনি সমাধান করছেন নাকি যাচাই করছেন তার উপর। Level 6-এর algorithms module-এ আপনি এই exponential search-টাকে backtracking দিয়ে prune করার কৌশল শিখেছেন — pruning সাহায্য করে, worst case-এ এখনো exponential-ই থেকে যায়, যতক্ষণ না P = NP প্রমাণিত হয়।

নিজে চালিয়ে দেখুন

EXPERIMENT

Verify বনাম Solve — সময়ের ব্যবধান নিজের চোখে দেখুন

Python 3· ১৫ মিনিট
import time, itertools, random

def verify_subset_sum(nums, target, certificate):
    """O(|certificate|) — শুধু যোগ করে target-এর সাথে তুলনা"""
    return sum(certificate) == target and set(certificate) <= set(nums)

def solve_subset_sum_bruteforce(nums, target):
    """O(2^n) — সব উপসেট চেষ্টা"""
    n = len(nums)
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        if sum(subset) == target:
            return subset
    return None

random.seed(7)
print(f"{'n':>4} {'solve(ms)':>12} {'verify(ms)':>12} {'অনুপাত':>10}")

for n in range(10, 26, 3):
    nums = random.sample(range(1, 10 * n), n)
    target = sum(random.sample(nums, n // 2))  # নিশ্চিতভাবে একটা সমাধান আছে

    t0 = time.perf_counter()
    sol = solve_subset_sum_bruteforce(nums, target)
    t_solve = (time.perf_counter() - t0) * 1000

    t0 = time.perf_counter()
    for _ in range(1000):  # ১০০০ বার যাতে সময় মাপার যোগ্য হয়
        verify_subset_sum(nums, target, sol)
    t_verify = (time.perf_counter() - t0)

    ratio = t_solve / t_verify if t_verify > 0 else float("inf")
    print(f"{n:>4} {t_solve:>12.3f} {t_verify:>12.6f} {ratio:>10.0f}x")

প্রত্যাশিত (illustrative) আউটপুট:

   n    solve(ms)   verify(ms)     অনুপাত
  10        0.412     0.000891        462x
  13        3.201     0.000903       3546x
  16       24.850     0.000897      27703x
  19      198.442     0.000912     217589x
  22     1583.201     0.000905    1749393x
  25    12904.553     0.000898   14370326x

লক্ষ্য করুন: n প্রতি 3 বাড়লে solve সময় প্রায় ৮ গুণ বাড়ছে (2^3 = 8, ঠিক যেমন তত্ত্ব predict করে), কিন্তু verify সময় কার্যত অপরিবর্তিত থাকছে — কারণ certificate-এর দৈর্ঘ্য n-এর সাথে রৈখিকভাবে বাড়লেও, n ≤ 25-এর জন্য এটা এত ছোট যে পার্থক্য মাপার যন্ত্রের precision-এর নিচে। এই সূচকীয়-বনাম-স্থির বৈসাদৃশ্যটাই NP-এর সংজ্ঞার হৃদয়।

নিজে বাড়ান: solve_subset_sum_bruteforce-এর বদলে dynamic programming সংস্করণ (O(n \cdot T)) বসিয়ে দেখুন — ছোট T-তে এটা polynomial-এর মতো আচরণ করে, কিন্তু target-কে খুব বড় করে দিলে (যেমন 2^{40}-এর কাছাকাছি) সেটাও ধীর হয়ে যাবে — pseudo-polynomial হওয়ার সীমাটা নিজের চোখে দেখুন।

এটা কী প্রমাণ করে

একই সমস্যার (Subset Sum) certificate যাচাই করার সময় প্রায় স্থির থাকে যখন সমাধান খোঁজার সময় ইনপুট আকারের সাথে exponentially বাড়ে — NP-এর সংজ্ঞার ঠিক যে অসামঞ্জস্যটা ধরতে চায়, সেটাই এখানে measured।

বাস্তব সিস্টেমে

এই class-গুলো কোথায় বাস্তব সিদ্ধান্ত নির্ধারণ করে

Cryptography। আধুনিক public-key cryptography (RSA, Diffie-Hellman) নির্ভর করে এমন সমস্যার উপর যেগুলো NP-তে আছে (factoring, discrete log-এর certificate তুচ্ছ) কিন্তু যাদের জন্য কোনো known polynomial algorithm নেই। এটা লক্ষ্য করুন — এই সমস্যাগুলো NP-complete বলে প্রমাণিত নয় (আসলে factoring NP ∩ co-NP-তে আছে বলে মনে করা হয়, যা এটাকে NP-complete হওয়া থেকে দূরে রাখে — যদি NP-complete হতো আর NP ≠ co-NP হতো, তাহলে সেটা NP ∩ co-NP-তে থাকতে পারত না)। তবু cryptography পুরো “P vs NP-এর তাৎপর্য” লেসনে বিস্তারিত আলোচিত এই বৃহত্তর অনুমানের উপর দাঁড়িয়ে আছে যে সাধারণভাবে সমাধান খোঁজা যাচাই করার চেয়ে ভয়ানকভাবে কঠিন। Level 12-এর security module-এ RSA-এর নিরাপত্তা যুক্তি ঠিক এই ভিত্তির উপর দাঁড় করানো হয়েছে।

Compiler — register allocation। একটা program-এর variable-গুলোকে সীমিত সংখ্যক CPU register-এ বসানো — এটা graph coloring-এর একটা রূপ (interference graph-এ প্রতিটা variable একটা node, দুইটা variable একসাথে “জীবিত” থাকলে edge)। k-রঙে রঙ করা যায় কি না (যেখানে k = register সংখ্যা) NP-complete, তাই বাস্তব compiler কখনো সেরা সমাধান guarantee করে না — heuristic (graph coloring approximation, spilling) ব্যবহার করে।

AI planning। একটা robot-এর জন্য কাজের একটা ক্রম (plan) খুঁজে বের করা যা goal অর্জন করে — এটা সাধারণভাবে PSPACE-complete (কিছু সরলীকৃত সংস্করণ NP-complete)। এই কারণেই বাস্তব planning system (STRIPS-ধাঁচের planner) সম্পূর্ণতা ছেড়ে দিয়ে heuristic search ব্যবহার করে।

VLSI ডিজাইন। Chip-এর উপর component বসানো (placement) আর তার মধ্যে তার সংযোগ করা (routing) — দুটোই classical NP-hard optimization সমস্যা। EDA (Electronic Design Automation) টুলগুলো দশকের পর দশক ধরে এই সমস্যার জন্য চতুর heuristic তৈরি করেছে, কারণ exact সমাধান বাস্তবসম্মত নয়।

Database query optimization। একটা multi-table JOIN কোন ক্রমে করা হবে তা নির্ধারণ — সম্ভাব্য ক্রম সংখ্যা n!, আর অপটিমাল ক্রম খোঁজা NP-hard। বাস্তব database engine dynamic programming (ছোট n-এ exact) বা greedy heuristic (বড় n-এ) ব্যবহার করে।

Game verification। দুই-খেলোয়াড় সম্পূর্ণ তথ্যের game (Chess, Checkers, Go-এর generalized, polynomial-size বোর্ড সংস্করণ) — “সাদা কি জিততে পারে?” প্রশ্নটা PSPACE-complete (বা তার চেয়েও বেশি কঠিন, নির্দিষ্ট নিয়মের উপর নির্ভর করে)। এটাই ব্যাখ্যা করে কেন সাধারণ বোর্ড সাইজের game solver-ও কেন exponential search এড়াতে পারে না, শুধু ভালো pruning (alpha-beta) দিয়ে ব্যবহারিকভাবে দ্রুত করে।

যে ভুলগুলো সবাই করে

“NP মানে 'কম্পিউটারে করা যায় না' বা 'polynomial সময়ে সমাধান করা যায় না'।”

সম্পূর্ণ ভুল, আর এটাই সবচেয়ে সাধারণ ভুল ব্যাখ্যা।

NP = “Nondeterministic Polynomial time” — একটা positive সংজ্ঞা (কোনো কিছু করা যায় তার উপর ভিত্তি করে: যাচাই করা যায় polynomial সময়ে), negative নয়।

প্রতিটা P সমস্যাও NP-তে আছে (P ⊆ NP)। 2-SAT, sorting, shortest path — সবই NP-তে, আর সবই polynomial সময়ে সমাধানযোগ্যও। NP-তে থাকা মানে সমাধান-অযোগ্য নয় — মানে অন্তত যাচাই-যোগ্য।

আসল প্রশ্নটা হলো: NP-এর ভেতর এমন কোনো সমস্যা কি আছে যেটা P-তে নেই (অর্থাৎ যাচাই করা সহজ কিন্তু সমাধান করা কঠিন)? এটাই P বনাম NP প্রশ্ন, আর এর উত্তর অজানা — আমরা বিশ্বাস করি “হ্যাঁ” (আছে), কিন্তু প্রমাণ নেই।

“PSPACE মানে 'অনেক বেশি মেমরি লাগে, তাই এটা NP-এর চেয়ে বাস্তবে ব্যবহার করা কঠিন'।”

উল্টো — PSPACE-এর সংজ্ঞা NP-এর চেয়ে কম সীমাবদ্ধতা রাখে। PSPACE শুধু বলে “polynomial space ব্যবহার করো, সময় যা লাগে লাগুক” — এতে exponential সময়ের algorithm-ও অন্তর্ভুক্ত, যতক্ষণ তার space ছোট থাকে।

NP একটা সময়-ভিত্তিক class (verifier polynomial সময়ে চলে)। PSPACE একটা space-ভিত্তিক class। এই দুইটা ভিন্ন অক্ষ — এক বললে অন্যটা বোঝায় না।

NP ⊆ PSPACE প্রমাণিত (এই লেসনের “hood” অংশে দেখানো হয়েছে) — তাই প্রতিটা NP সমস্যা PSPACE-তেও আছে। ব্যবহারিকভাবে, PSPACE-complete সমস্যা (TQBF-এর মতো) সাধারণত NP-complete সমস্যার চেয়েও কঠিন মনে হয় বাস্তব solver-এ — কারণ তাদের সমাধান করতে exponential স্তরের recursion লাগে (নেস্টেড quantifier), যেখানে NP-complete সমস্যায় অন্তত একটা “সমতল” exponential search যথেষ্ট।

“যেহেতু কেউ প্রমাণ করতে পারেনি P ≠ NP, তার মানে সম্ভবত P = NP আর আমরা শুধু প্রমাণটা খুঁজে পাইনি।”

বেশিরভাগ গবেষকের অবস্থান ঠিক উল্টো — কার্যত সর্বসম্মতভাবে বিশ্বাস করা হয় P ≠ NP, যদিও প্রমাণ নেই।

কারণ: হাজার হাজার NP-complete সমস্যা (পরের লেসনে দেখব) — বিভিন্ন ক্ষেত্রের সবচেয়ে মেধাবী গবেষকরা ৫০ বছর ধরে চেষ্টা করেছেন কোনো একটার জন্য polynomial algorithm খুঁজতে, একটাও পাওয়া যায়নি। একটাও পাওয়া গেলে সব NP-complete সমস্যা সমাধান হয়ে যেত (এটাই পরের লেসনের বিষয়) — এত বড় একটা পুরস্কার এত দীর্ঘ সময় ধরে অস্পৃশ্য থাকাটা শক্তিশালী (যদিও প্রমাণ নয়) evidence যে P ≠ NP।

“P vs NP-এর তাৎপর্য” লেসনে আমরা দেখব কেন এই বিশ্বাসের পক্ষে আরো কাঠামোগত যুক্তি আছে — আর কেন এই প্রশ্নটা প্রমাণ করা এত কঠিন যে বহু প্রমাণ-পদ্ধতিই কাঠামোগতভাবে ব্যর্থ হতে বাধ্য।

বুঝেছেন কি না দেখুন

1

NP-এর verifier-based সংজ্ঞায় দুইটা শর্ত আছে certificate c-এর উপর। কী কী, আর কেন দুটোই দরকার?

স্মরণ

দুইটা শর্ত:

  1. দৈর্ঘ্য সীমাবদ্ধ: |c| ≤ p(|x|) কোনো polynomial p-এর জন্য।
  2. Verifier polynomial সময়ে চলে: V(x, c) O(poly(|x|)) সময়ে সিদ্ধান্ত দেয়।

দুটোই দরকার একসাথে, নাহলে সংজ্ঞা অর্থহীন হয়ে যায়:

  • যদি শুধু (২) থাকত (verifier দ্রুত, কিন্তু c-এর দৈর্ঘ্যে কোনো সীমা নেই): c হতে পারত x-এর দৈর্ঘ্যের সূচকীয় বড়, আর verifier শুধু c-এর প্রথম কয়েকটা bit polynomial সময়ে পড়ে সিদ্ধান্ত নিতে পারত — কিন্তু certificate নিজে বানাতেই তো exponential সময় লাগত (যদি না এটা compactly encode করা যায়, যেটা আবার দৈর্ঘ্যের সীমা দাবি করে)।
  • যদি শুধু (১) থাকত (c ছোট, কিন্তু verifier যত সময় ইচ্ছা নিতে পারে): তাহলে verifier নিজেই সরাসরি সমাধান খুঁজে ফেলতে পারত (c ignore করে), যা NP-কে PSPACE-এর মতো বিশাল করে দিত — differentiation হারিয়ে যেত P থেকে।

দুই শর্ত একসাথেই “সহজে যাচাইযোগ্য কিন্তু (সম্ভবত) কঠিনভাবে-খোঁজার-যোগ্য” প্রমাণের সংজ্ঞাটা নিখুঁতভাবে ধরে।

2

HAMILTONIAN-PATH (একটা graph-এ প্রতিটা node ঠিক একবার visit করে এমন path আছে কি?) NP-তে আছে তা দেখান — certificate কী, আর verifier কীভাবে কাজ করে?

যুক্তি

Certificate: node-গুলোর একটা ক্রম v_1, v_2, \ldots, v_n (দাবি করা path-টা)।

Verifier V(G, c):

1. c-তে G-এর প্রতিটা node ঠিক একবার আছে কি না চেক করো — O(n)
2. প্রতিটা পরপর জোড়া (v_i, v_{i+1}) G-তে একটা edge কি না চেক করো — O(n)
3. দুটোই সত্য হলে ACCEPT, নাহলে REJECT

মোট সময়: O(n), স্পষ্টতই polynomial |G|-এর সাপেক্ষে।

Completeness: যদি সত্যিই একটা Hamiltonian path থাকে, সেই path-টাই certificate হিসেবে দিলে V অবশ্যই accept করবে।

Soundness: যদি কোনো Hamiltonian path না থাকে, তাহলে যেকোনো প্রস্তাবিত ক্রম c-এর জন্য হয় node বাদ পড়বে/পুনরাবৃত্তি হবে, নয়তো কোনো একটা পরপর জোড়া edge হবে না — দুই ক্ষেত্রেই V reject করবে।

তাই HAMILTONIAN-PATH ∈ NP। (লক্ষ্য করুন — সমাধান খোঁজা, অর্থাৎ এমন একটা ক্রম নিজে বের করা, সম্পূর্ণ ভিন্ন প্রশ্ন, আর HAMILTONIAN-PATH আসলে NP-complete — পরের লেসনের বিষয়।)

3

P ⊆ co-NP কেন সত্য, তা প্রমাণ করুন। (ইঙ্গিত: P-এর একটা structural property ব্যবহার করুন যা সরাসরি এই লেসনে আলোচিত হয়েছে।)

যুক্তি

প্রথমে প্রমাণ করি P complement-এর অধীনে বদ্ধ, অর্থাৎ L ∈ P ⟹ \bar{L} ∈ P।

ধরুন L ∈ P, তাই একটা deterministic TM M আছে যা polynomial সময়ে L decide করে — x ∈ L হলে accept, x ∉ L হলে reject।

একটা নতুন TM M' বানান: M' হুবহু M-এর মতোই চলে, কিন্তু শেষে accept/reject উল্টে দেয় (M accept করলে M' reject করে, আর বিপরীত)। M'-ও polynomial সময়ে চলে (M-এর সাথে সমান সময়, প্লাস একটা ধ্রুবক), আর M' ঠিক \bar{L} decide করে।

তাই \bar{L} ∈ P, অর্থাৎ P complement-এর অধীনে বদ্ধ — একে সংক্ষেপে P = co\text{-}P লেখা হয়।

এখন P ⊆ NP (আগে প্রমাণিত — deterministic TM-ই একটা তুচ্ছ verifier)। L ∈ P নিন। তাহলে \bar{L} ∈ P (উপরের প্রমাণ)। যেহেতু P ⊆ NP, \bar{L} ∈ NP। কিন্তু co-NP-এর সংজ্ঞা অনুযায়ী: \bar{L} ∈ NP \iff L ∈ co\text{-}NP।

তাই L ∈ co\text{-}NP। যেহেতু L-কে যথেচ্ছভাবে নেওয়া হয়েছিল P থেকে, P ⊆ co\text{-}NP ∎

এই প্রমাণটা লক্ষ্য করুন — এটা এই লেসনের সেই “ডমিনো effect” observation-এরই ভিত্তি: P-এর complement-বদ্ধতাই সব class-এর মধ্যে অতিরিক্ত সম্পর্ক তৈরি করে।

4

নিচের প্রতিটা সমস্যার জন্য বলুন এটা P, NP, co-NP, না PSPACE-এর কোন class-এ সবচেয়ে স্বাভাবিকভাবে পড়ে (একাধিক হতে পারে যদি containment-এর কারণে হয়), আর সংক্ষেপে কেন:

(a) দুইটা সংখ্যা গুণ করে তৃতীয় সংখ্যার সমান হয় কি না যাচাই (b) একটা n × n Sudoku গ্রিড বৈধভাবে ভরা যায় কি না নির্ণয় (c) একটা graph-এ কোনো triangle (৩-node cycle) নেই তা নির্ণয়

প্রয়োগ

(a) গুণফল যাচাই — P-তে (তাই NP আর co-NP-তেও, কারণ P ⊆ NP আর P ⊆ co-NP)। গুণ করা নিজেই polynomial সময়ে (স্কুলের পদ্ধতিতেও O(n^2) digit-এর সাপেক্ষে) হয়, verifier লাগেই না — সরাসরি decide করা যায়। এটা মনে করিয়ে দেয়: P-তে থাকা সমস্যা NP আর co-NP দুটোতেই “স্বাভাবিকভাবে” পড়ে, কারণ containment।

(b) Sudoku (generalized n × n) — NP-complete (তাই NP-তে)। certificate = একটা ভরা গ্রিড, যাচাই O(n^2)-এ (প্রতিটা সারি/কলাম/বক্স চেক)। সমাধান খোঁজার কোনো known polynomial algorithm নেই generalized সংস্করণে (নির্দিষ্ট 9×9 সাইজে অবশ্যই দ্রুত সমাধানযোগ্য — ধ্রুবক আকারের ইনপুটে জটিলতা তত্ত্ব প্রযোজ্য নয়; complexity class-এর প্রশ্ন সবসময় পরিবর্তনশীল input size-এর উপর, ধ্রুবক size-এর নয়)।

(c) Triangle-মুক্ত — co-NP-তে প্রাকৃতিকভাবে বসে, কিন্তু আসলে P-তেও আছে। “না, এটা triangle-মুক্ত নয়” এমন দাবির জন্য certificate তুচ্ছ (একটা triangle দেখিয়ে দিন) — তাই “G-তে triangle আছে” NP-তে, ফলে তার complement (“triangle নেই”) co-NP-তে। কিন্তু এই নির্দিষ্ট সমস্যাটার জন্য আসলে সরাসরি O(n^3) (বা matrix multiplication কৌশলে আরো দ্রুত) polynomial algorithm আছে — সব node-জোড়ার common neighbor চেক করা — তাই এটা আসলে P-তেই, co-NP-তে “শুধু certificate-ভিত্তিক যুক্তিতে” রাখাটা অতিরিক্ত সতর্কতা মাত্র। এই উদাহরণটা মনে করিয়ে দেয়: একটা সমস্যা কোন class-এ “স্বাভাবিকভাবে বসে” তা প্রমাণ করা আর সেটা আসলে কতটা কঠিন তা এক জিনিস নয় — P-এর সদস্যরা NP আর co-NP দুই জায়গাতেই বসে, কারণ তারা উভয়ের উপসেট।

5

“hood” অংশে দেখানো হয়েছে NP ⊆ PSPACE — সব certificate একে একে চেষ্টা করে, space পুনর্ব্যবহার করে। একই যুক্তি ব্যবহার করে দেখান co\text{-}NP ⊆ PSPACE-ও সত্য। (PSPACE complement-এর অধীনে বদ্ধ কি না, সেটা প্রথমে প্রতিষ্ঠা করে শুরু করুন।)

ডিজাইন

ধাপ ১ — PSPACE complement-এর অধীনে বদ্ধ।

ধরুন L ∈ PSPACE, একটা TM M আছে যা O(n^k) space-এ L decide করে। P-এর জন্য যা করেছিলাম ঠিক সেই একই কৌশল: M-এর accept/reject উল্টে দিয়ে M' বানান। M'-এর space ব্যবহার M-এর সমানই থাকে (শুধু শেষ সিদ্ধান্তটা উল্টানো, extra memory লাগে না)। তাই \bar{L} ∈ PSPACE। অর্থাৎ PSPACE = co\text{-}PSPACE।

ধাপ ২ — co\text{-}NP ⊆ PSPACE।

L ∈ co\text{-}NP নিন। সংজ্ঞা অনুযায়ী \bar{L} ∈ NP। “hood” অংশের ফলাফল থেকে: \bar{L} ∈ PSPACE (কারণ NP ⊆ PSPACE)। ধাপ ১ অনুযায়ী PSPACE complement-বদ্ধ, তাই \overline{\bar{L}} = L ∈ PSPACE।

তাই co\text{-}NP ⊆ PSPACE ∎

একটা সাধারণ প্যাটার্ন লক্ষ্য করুন: এই লেসনের প্রায় প্রতিটা containment প্রমাণ একই দুইটা কৌশলের সমন্বয় — (১) সরাসরি simulation (একটা মডেলের algorithm অন্য মডেলে চালানো, resource-এর হিসাব রেখে), আর (২) complement-বদ্ধতার maneuver (P, PSPACE উভয়ই এই সম্পত্তি রাখে, কিন্তু NP নিজে রাখে কি না তা অজানা — এটাই NP বনাম co-NP প্রশ্নের মূল)। এই দুইটা কৌশল বারবার ফিরে আসবে পরের লেসনগুলোতেও, যখন আমরা reduction দিয়ে NP-completeness প্রমাণ করব।

এরপর কী

আমরা এখন চারটা class-এর আনুষ্ঠানিক সংজ্ঞা জানি, আর জানি তাদের মধ্যেকার containment — কিন্তু এই containment-গুলো strict কি না তা অজানা।

পরের প্রশ্ন: NP-এর ভেতরেই কি এমন কোনো কাঠামো আছে যা ব্যাখ্যা করে কেন এত সমস্যা (Sudoku, Hamiltonian Path, graph coloring, TSP, আরো হাজার হাজার) একসাথে কঠিন মনে হয়, একটাতে অগ্রগতি হলে বাকি সবগুলোতেও হয়ে যাবে বলে মনে হয়? পরের লেসনে আমরা দেখব NP-completeness — আর Cook-Levin theorem, যা প্রমাণ করে SAT (Boolean satisfiability) হলো NP-এর সবচেয়ে কঠিন সমস্যা, আর কীভাবে একটা মাত্র সমস্যা থেকে হাজার হাজার অন্য সমস্যার কাঠিন্য reduction দিয়ে প্রমাণ করা যায়।

আরও পড়ুন

  • Introduction to the Theory of Computation, Chapter 7 — Michael Sipser · P, NP, NP-completeness, PSPACE-এর জন্য মান পাঠ্যবই — এই লেসনের কাঠামো মূলত এখান থেকে
  • Computers and Intractability: A Guide to the Theory of NP-Completeness — Michael Garey, David Johnson · ৩০০+ NP-complete problem-এর catalog, এখনো ব্যবহৃত reference
  • Computational Complexity: A Modern Approach — Sanjeev Arora, Boaz Barak · PSPACE, Savitch's theorem, আর হায়ারার্কির কঠোর treatment-এর জন্য