EXPTIME
গণনামূলক জটিলতা তত্ত্বে, জটিলতা শ্রেণী ই. এক্স. পি. টি. আই. এম. ই (কখনও কখনও ই. এক্স. পি বা ডি. ই. এক্স. পি. টি. আই. এম. ই বলা হয়) হল সমস্ত সিদ্ধান্ত সংক্রান্ত সমস্যার সমষ্টি যা একটি নির্ধারক টুরিং মেশিন দ্বারা সূচকীয় সময়ে সমাধানযোগ্য, অর্থাৎ, ও (2পি (এন)) সময়ে, যেখানে পি (এন) হল এন-এর একটি বহুপদী ফাংশন। উদাহরণস্বরূপ, ক্লাস 2-এক্সপিটিআইএমই-কে এক্সপিটিআইএমই-এর মতো একইভাবে সংজ্ঞায়িত করা হয়েছে তবে দ্বিগুণ সূচকীয় সময়সীমার সাথে। এটি উচ্চতর এবং উচ্চতর সময়সীমার মধ্যে সাধারণীকরণ করা যেতে পারে। EXPTIME কে স্পেস ক্লাস APSPACE হিসাবেও পুনর্গঠন করা যেতে পারে, যা বহুপদী স্থানে একটি বিকল্প টুরিং মেশিন দ্বারা সমাধান করা যেতে পারে এমন সমস্ত সমস্যার সেট। EXPTIME অন্যান্য মৌলিক সময় এবং স্থান জটিলতা শ্রেণীর সাথে নিম্নলিখিত উপায়ে সম্পর্কিতঃ পি-এন. পি-স্পেস-স্পেস-স্পেস। উপরন্তু, সময় শ্রেণিবিন্যাস উপপাদ্য এবং স্থান শ্রেণিবিন্যাস উপপাদ্য দ্বারা, এটি জানা যায় যে পি এক্সপিটিআইএমই, এনপি এনইএক্সপিটিআইএমই এবং পিএসপিই এক্সপস্পেস। আনুষ্ঠানিক সংজ্ঞা ডি. টি. আই. এম. ই-এর পরিপ্রেক্ষিতে, অন্যান্য শ্রেণীর সাথে সম্পর্ক এটিও জানা যায় যে, সময় শ্রেণিবিন্যাস উপপাদ্য এবং স্থান শ্রেণিবিন্যাস উপপাদ্য দ্বারা, উপরের অভিব্যক্তিতে, প্রতীকটির অর্থ হল "এর একটি উপসেট", এবং প্রতীকটির অর্থ হল "এর একটি কঠোর উপসেট"। সুতরাং প্রথম তিনটি অন্তর্ভুক্তির মধ্যে অন্তত একটি এবং শেষ তিনটি অন্তর্ভুক্তির মধ্যে অন্তত একটি অবশ্যই যথাযথ হতে হবে, তবে কোনটি তা জানা যায় না। বেশিরভাগ বিশেষজ্ঞরা বিশ্বাস করেন যে সমস্ত অন্তর্ভুক্তি সঠিক। এটিও জানা যায় যে, যদি পি = এন. পি হয়, তাহলে এক্স. পি. টি. আই. এম. ই. এন. ই. এক্স. পি. টি. আই. এম, একটি অনির্ধারিত টুরিং মেশিন দ্বারা সূচকীয় সময়ে সমাধানযোগ্য সমস্যার শ্রেণী। আরও সুনির্দিষ্টভাবে বলতে গেলে, যদি এবং শুধুমাত্র এন. পি-তে বিরল ভাষা থাকে যা পি-তে না থাকে, তাহলেই এক্স. পি. টি. আই. এম-কে স্পেস ক্লাস এ. পি. এস. পি. এ. সি হিসাবে পুনর্বিন্যাস করা যেতে পারে, যা বহুপদী স্থানে বিকল্প টুরিং মেশিন দ্বারা সমাধান করা যেতে পারে এমন সমস্ত সমস্যার সমষ্টি। এটি পি. এস. পি. এ. সি. ই. এক্স. পি. টি. আই. এম দেখার একটি উপায়, যেহেতু একটি বিকল্প টুরিং মেশিন অন্তত একটি নির্ধারক টুরিং মেশিনের মতো শক্তিশালী। এক্সপিটিআইএম-সম্পূর্ণ একটি সিদ্ধান্ত সমস্যা এক্সপিটিআইএম-সম্পূর্ণ হয় যদি এটি এক্সপিটিআইএম-এ থাকে এবং এক্সপিটিআইএম-এর প্রতিটি সমস্যার একটি বহুপদী-সময় বহু-এক হ্রাস থাকে। অন্য কথায়, একটি পলিনোমিয়াল-টাইম অ্যালগরিদম রয়েছে যা একই উত্তর দিয়ে একটির দৃষ্টান্তকে অন্যটির উদাহরণে রূপান্তরিত করে। এক্সপিটিআইএমই-সম্পূর্ণ সমস্যাগুলিকে এক্সপিটিআইএমই-এর সবচেয়ে কঠিন সমস্যা হিসাবে বিবেচনা করা যেতে পারে। লক্ষ্য করুন যে যদিও এটি অজানা যে এনপি পি-এর সমান কিনা, আমরা জানি যে এক্সপিটিআইএমই-সম্পূর্ণ সমস্যাগুলি পি-তে নেই; এটি প্রমাণিত হয়েছে যে এই সমস্যাগুলি বহুপদী সময়ে, সময় শ্রেণিবিন্যাস উপপাদ্য দ্বারা সমাধান করা যায় না। গণনাযোগ্যতা তত্ত্বে, মৌলিক অনির্ধারিত সমস্যাগুলির মধ্যে একটি হল থামার সমস্যাঃ একটি নির্ধারক টুরিং মেশিন (ডিটিএম) থামবে কিনা তা নির্ধারণ করা। সবচেয়ে মৌলিক এক্সপিটিআইএমই-সম্পূর্ণ সমস্যাগুলির মধ্যে একটি হল এর একটি সহজ সংস্করণ, যা জিজ্ঞাসা করে যে কোনও ডিটিএম সর্বাধিক কে ধাপে প্রদত্ত ইনপুট বন্ধ করে দেয় কিনা। এটি এক্সপিটিআইএমই-তে রয়েছে কারণ একটি তুচ্ছ সিমুলেশনের জন্য ও (কে) সময় প্রয়োজন, এবং ইনপুট কে ও (লগ কে) বিট ব্যবহার করে এনকোড করা হয় যা সূচকীয় সংখ্যক সিমুলেশন সৃষ্টি করে। এটি EXPTIME-সম্পূর্ণ কারণ, মোটামুটিভাবে বলতে গেলে, আমরা এটি নির্ধারণ করতে ব্যবহার করতে পারি যে একটি EXPTIME সমস্যা সমাধানকারী মেশিন সূচকীয় সংখ্যক ধাপে গ্রহণ করে কিনা; এটি আরও বেশি ব্যবহার করবে না। ইউনারিতে লেখা ধাপের সংখ্যা নিয়ে একই সমস্যা হল পি-কমপ্লিট। EXPTIME-সম্পূর্ণ সমস্যার অন্যান্য উদাহরণগুলির মধ্যে রয়েছে সাধারণ দাবা, চেকার বা গো (জাপানি কো নিয়ম সহ)-এ একটি অবস্থানের মূল্যায়ন করার সমস্যা। এই গেমগুলির এক্সপিটিআইএমই-সম্পূর্ণ হওয়ার সম্ভাবনা রয়েছে কারণ গেমগুলি বেশ কয়েকটি পদক্ষেপের জন্য স্থায়ী হতে পারে যা বোর্ডের আকারে সূচকীয়। গো উদাহরণে, জাপানি কো নিয়মটি এক্সপিটিআইএমই-সম্পূর্ণতা বোঝায় বলে জানা যায়, তবে গেমটির জন্য আমেরিকান বা চীনা নিয়মগুলি এক্সপিটিআইএমই-সম্পূর্ণ কিনা তা জানা যায় না (সেগুলি পি. এস. পি. এ. সি. ই থেকে এক্সপি. এস. পি. এ. সি পর্যন্ত হতে পারে)। বিপরীতে, সাধারণ গেমগুলি যা বোর্ডের আকারে বহুপদী বেশ কয়েকটি পদক্ষেপের জন্য স্থায়ী হতে পারে প্রায়শই পি. এস. পি. এ. সি. ই-সম্পূর্ণ হয়। ক্রমবর্ধমান দীর্ঘ গেমগুলির ক্ষেত্রেও একই কথা প্রযোজ্য যেখানে পুনরাবৃত্তি না করা স্বয়ংক্রিয়। গুরুত্বপূর্ণ EXPTIME-সম্পূর্ণ সমস্যার আরেকটি সেট সংক্ষিপ্ত সার্কিটের সাথে সম্পর্কিত। সুসিঙ্ক সার্কিট হল সহজ যন্ত্র যা কম জায়গায় কিছু গ্রাফ বর্ণনা করতে ব্যবহৃত হয়। তারা দুটি শীর্ষ সংখ্যাকে ইনপুট এবং আউটপুট হিসাবে গ্রহণ করে, যদি তাদের মধ্যে একটি প্রান্ত থাকে। অনেক প্রাকৃতিক পি-সম্পূর্ণ গ্রাফ সমস্যার জন্য, যেখানে গ্রাফটি একটি প্রাকৃতিক উপস্থাপনায় যেমন একটি সংলগ্ন ম্যাট্রিক্সে প্রকাশ করা হয়, একটি সংক্ষিপ্ত সার্কিট উপস্থাপনায় একই সমস্যা সমাধান করা এক্সপিটিআইএমই-সম্পূর্ণ, কারণ ইনপুটটি তাত্পর্যপূর্ণভাবে ছোট; তবে এর জন্য অ-তুচ্ছ প্রমাণ প্রয়োজন, কারণ সংক্ষিপ্ত সার্কিটগুলি শুধুমাত্র গ্রাফের একটি উপশ্রেণী বর্ণনা করতে পারে। তথ্যসূত্র জটিলতা শ্রেণী