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