Structural complexity theory
কম্পিউটার বিজ্ঞানের গণনামূলক জটিলতা তত্ত্বে, কাঠামোগত জটিলতা তত্ত্ব বা কেবল কাঠামোগত জটিলতা হল পৃথক সমস্যা এবং অ্যালগরিদমের গণনামূলক জটিলতার পরিবর্তে জটিলতা শ্রেণীর অধ্যয়ন। এতে বিভিন্ন জটিলতা শ্রেণীর অভ্যন্তরীণ কাঠামো এবং বিভিন্ন জটিলতা শ্রেণীর মধ্যে সম্পর্ক উভয়ই গবেষণা জড়িত। এই ধরনের প্রথম এবং এখনও সবচেয়ে গুরুত্বপূর্ণ প্রশ্ন, পি = এনপি সমস্যা সমাধানের প্রচেষ্টার ফলস্বরূপ (এখনও ব্যর্থ) তত্ত্বটি আবির্ভূত হয়েছে। বেশিরভাগ গবেষণা পি-এর এনপি-র সমান না হওয়ার অনুমানের উপর ভিত্তি করে এবং আরও সুদূরপ্রসারী অনুমানের উপর ভিত্তি করে করা হয় যে জটিলতা শ্রেণীর বহুপদী সময়ের শ্রেণিবিন্যাস অসীম। গুরুত্বপূর্ণ ফলাফল কম্প্রেশন উপপাদ্য কম্প্রেশন উপপাদ্য গণনাযোগ্য ফাংশনের জটিলতা সম্পর্কে একটি গুরুত্বপূর্ণ উপপাদ্য। উপপাদ্যটি বলে যে গণনাযোগ্য সীমানা সহ কোনও বৃহত্তম জটিলতা শ্রেণীর অস্তিত্ব নেই, যার মধ্যে সমস্ত গণনাযোগ্য ফাংশন রয়েছে। স্থান শ্রেণিবিন্যাস উপপাদ্য স্থান শ্রেণিবিন্যাস উপপাদ্য হল পৃথকীকরণের ফলাফল যা দেখায় যে নির্ধারক এবং অনির্ধার্য উভয় যন্ত্রই নির্দিষ্ট শর্ত সাপেক্ষে আরও বেশি জায়গায় (অ্যাসিম্পটোটিকভাবে) আরও সমস্যা সমাধান করতে পারে। উদাহরণস্বরূপ, একটি নির্ধারক টুরিং মেশিন স্থান n-এর তুলনায় স্থান n-এ আরও বেশি সিদ্ধান্তের সমস্যা সমাধান করতে পারে। সময়ের জন্য কিছুটা দুর্বল অনুরূপ উপপাদ্যগুলি হল সময় শ্রেণিবিন্যাস উপপাদ্য। সময় শ্রেণিবিন্যাস উপপাদ্য সময় শ্রেণিবিন্যাস উপপাদ্যগুলি টুরিং মেশিনে সময়-সীমাবদ্ধ গণনা সম্পর্কে গুরুত্বপূর্ণ বিবৃতি। অনানুষ্ঠানিকভাবে, এই উপপাদ্যগুলি বলে যে আরও সময় দেওয়া হলে, একটি টুরিং মেশিন আরও সমস্যা সমাধান করতে পারে। উদাহরণস্বরূপ, এমন কিছু সমস্যা রয়েছে যা n2 সময় দিয়ে সমাধান করা যেতে পারে কিন্তু n সময় দিয়ে নয়। ভ্যালিয়েন্ট-ভাজিরানি উপপাদ্য হল গণনামূলক জটিলতা তত্ত্বের একটি উপপাদ্য। লেসলি ভ্যালিয়েন্ট এবং বিজয় ভাজিরানি তাদের গবেষণাপত্রে এনপি 1986 সালে প্রকাশিত অনন্য সমাধান সনাক্ত করার মতোই সহজ বলে প্রমাণ করেছেন। উপপাদ্যটি বলে যে যদি দ্ব্যর্থহীন-স্যাটের জন্য একটি বহুপদী সময় অ্যালগরিদম থাকে, তাহলে এন. পি = আর. পি। প্রমাণটি মুলমুলে-ভাজিরানি বিচ্ছিন্নতা লেমার উপর ভিত্তি করে তৈরি, যা পরবর্তীকালে তাত্ত্বিক কম্পিউটার বিজ্ঞানের বেশ কয়েকটি গুরুত্বপূর্ণ প্রয়োগের জন্য ব্যবহৃত হয়েছিল। সিপসার-লাউটম্যান উপপাদ্য সিপসার-লাউটম্যান উপপাদ্য বা সিপসার-গ্যাকস-লাউটম্যান উপপাদ্য বলে যে বাউন্ডেড-এরর প্রোবেবিলিস্টিক পলিনোমিয়াল (বিপিপি) সময়, পলিনোমিয়াল সময় শ্রেণিবিন্যাসে রয়েছে এবং আরও নির্দিষ্টভাবে σ2 θ Π2। সাভিচের উপপাদ্য সাভিচের উপপাদ্য, 1970 সালে ওয়াল্টার সাভিচ দ্বারা প্রমাণিত, নির্ধারণমূলক এবং অ-নির্ধারণমূলক স্থান জটিলতার মধ্যে একটি সম্পর্ক দেয়। এতে বলা হয়েছে যে কোনও ফাংশনের জন্য, টোডার উপপাদ্যটি এমন একটি ফলাফল যা সিনোসুকে টোডা তাঁর গবেষণাপত্রে "পিপি ইজ অ্যাজ হার্ড অ্যাজ দ্য পলিনোমিয়াল-টাইম হায়ারার্কি" (1991)-তে প্রমাণ করেছিলেন এবং 1998 সালে তাকে গোডেল পুরস্কার দেওয়া হয়েছিল। উপপাদ্যটি বলে যে সমগ্র বহুপদী শ্রেণিবিন্যাস পিএইচ পিপিপিতে রয়েছে; এটি একটি ঘনিষ্ঠভাবে সম্পর্কিত বিবৃতি বোঝায়, যে পিএইচ P#P-এ রয়েছে। 1987 সালে নিল ইমারম্যান এবং রবার্ট সেলিপ্সনি দ্বারা স্বাধীনভাবে প্রমাণিত হয়েছিল ইমারম্যান-সেলিপ্সনি উপপাদ্য, যার জন্য তারা 1995 সালে গডেল পুরস্কার ভাগ করে নিয়েছিল। তার সাধারণ আকারে উপপাদ্যটি বলে যে যে কোনও ফাংশন s (n) ± লগ n-এর জন্য NSPACE (s (n)) = সহ-NSPACE (s (n))। ফলাফলটি সমতুল্যভাবে এন. এল = সহ-এন. এল হিসাবে বর্ণিত হয়; যদিও এটি বিশেষ ক্ষেত্রে যখন s (n) = লগ এন হয়, এটি একটি আদর্শ প্যাডিং যুক্তি দ্বারা সাধারণ উপপাদ্যকে বোঝায়। ফলাফলটি দ্বিতীয় এলবিএ সমস্যার সমাধান করে। গবেষণার বিষয় এই ক্ষেত্রে গবেষণার প্রধান দিকগুলির মধ্যে রয়েছেঃ জটিলতা সম্পর্কে বিভিন্ন অমীমাংসিত সমস্যা থেকে উদ্ভূত প্রভাবগুলির অধ্যয়ন শ্রেণী বিভিন্ন ধরনের সম্পদ-সীমাবদ্ধ হ্রাসের অধ্যয়ন এবং বিভিন্ন বিধিনিষেধের পরিণতি এবং তথ্য সংরক্ষণ ও অ্যাক্সেসের প্রক্রিয়াগুলির সংশ্লিষ্ট সম্পূর্ণ ভাষা অধ্যয়ন।