EXPSPACE
গণনামূলক জটিলতা তত্ত্বে, এক্সপোনেনশিয়াল স্পেসে একটি নির্ধারক টুরিং মেশিন দ্বারা সমাধানযোগ্য সমস্ত সিদ্ধান্ত সমস্যার সেট, অর্থাৎ, স্পেসে, যেখানে এর একটি বহুপদী ফাংশন। কিছু লেখক একটি রৈখিক ফাংশন হতে সীমাবদ্ধ, তবে বেশিরভাগ লেখক পরিবর্তে ফলাফল শ্রেণীকে কল করেন। এর পরিবর্তে যদি আমরা একটি অনির্ধারিত যন্ত্র ব্যবহার করি, তাহলে আমরা সেই শ্রেণীটি পাব, যা সাভিচের উপপাদ্যের সমান। একটি সিদ্ধান্ত সমস্যা হল যদি এটি ভিতরে থাকে, এবং প্রতিটি সমস্যার একটি বহুপদী-সময় বহু-এক হ্রাস থাকে। অন্য কথায়, একটি পলিনোমিয়াল-টাইম অ্যালগরিদম রয়েছে যা একই উত্তর দিয়ে একটির দৃষ্টান্তকে অন্যটির উদাহরণে রূপান্তরিত করে। সমস্যাগুলিকে সবচেয়ে কঠিন সমস্যা হিসাবে বিবেচনা করা যেতে পারে। এর একটি কঠোর সুপারসেট, এবং এবং এর একটি কঠোর সুপারসেট বলে মনে করা হয়। আনুষ্ঠানিক সংজ্ঞা এবং, সমস্যার উদাহরণ একটি সমস্যার উদাহরণ হল দুটি নিয়মিত অভিব্যক্তি বিভিন্ন ভাষার প্রতিনিধিত্ব করে কিনা তা শনাক্ত করার সমস্যা, যেখানে অভিব্যক্তিগুলি চারটি অপারেটরের মধ্যে সীমাবদ্ধঃ ইউনিয়ন, কনক্যাটেনেশন, ক্লিন স্টার (একটি অভিব্যক্তি শূন্য বা তার বেশি অনুলিপি), এবং বর্গ (একটি অভিব্যক্তিটির দুটি অনুলিপি)। যদি ক্লেইন স্টারটি বাদ দেওয়া হয়, তবে সেই সমস্যাটি হয়ে যায়, যা হল, এটি নির্ধারণের পরিবর্তে অ-নির্ধারণমূলক টুরিং মেশিনের পরিপ্রেক্ষিতে সংজ্ঞায়িত করা ছাড়া। 1980 সালে এল. বারম্যান এটাও দেখিয়েছেন যে, বাস্তব সংখ্যা সম্পর্কে যে কোনও প্রথম-ক্রমের বিবৃতি যাচাই/মিথ্যা করার সমস্যা রয়েছে যার মধ্যে কেবল যোগ এবং তুলনা জড়িত (তবে কোনও গুণন নেই)। আলুর এবং হেনজিঙ্গার সময় (পূর্ণসংখ্যা) সহ রৈখিক সাময়িক যুক্তি প্রসারিত করেন এবং প্রমাণ করেন যে তাদের যুক্তির বৈধতা সমস্যাটি EXPSPACE-সম্পূর্ণ। পেট্রি নেটসের জন্য কভারেবিলিটি সমস্যা-সম্পূর্ণ। পেট্রি জালের কাছে পৌঁছানোর সমস্যাটি দীর্ঘ সময় ধরে কঠিন বলে জানা গিয়েছিল, তবে এটি অপ্রয়োজনীয় বলে দেখানো হয়েছে, তাই এটি সম্ভবত নেই। অন্যান্য শ্রেণীর সাথে সম্পর্ক, এবং এর একটি কঠোর সুপারসেট হিসাবে পরিচিত। এটি একটি কঠোর সুপারসেট বলে সন্দেহ করা হচ্ছে, তবে এটি জানা যায় না। আরও দেখুন গেম কম্প্লেক্সিটি রেফারেন্স বিভাগ 9.1.1: এক্সপোনেনশিয়াল স্পেস কমপ্লিটনেস, পৃ. 313-317। প্রদর্শন করে যে সূচকের সাথে নিয়মিত অভিব্যক্তিগুলির সমতা নির্ধারণ করা EXPSPACE-সম্পূর্ণ। জটিলতার ক্লাস