P-complete
গণনামূলক জটিলতা তত্ত্বে, একটি সিদ্ধান্ত সমস্যা হল পি-সম্পূর্ণ (জটিলতা শ্রেণী পি-এর জন্য সম্পূর্ণ) যদি এটি পি-তে থাকে এবং পি-এর প্রতিটি সমস্যাকে যথাযথ হ্রাসের মাধ্যমে হ্রাস করা যেতে পারে। পি-সম্পূর্ণ সিদ্ধান্ত সমস্যার ধারণাটি বিশ্লেষণের জন্য দরকারীঃ কোন সমস্যাগুলি কার্যকরভাবে সমান্তরাল করা কঠিন, কোন সমস্যাগুলি সীমিত জায়গায় সমাধান করা কঠিন। বিশেষত যখন পলিটাইম-রিডিউসিবিলিটির চেয়ে রিডিউসিবিলিটির শক্তিশালী ধারণাগুলি বিবেচনা করা হয়। ব্যবহৃত নির্দিষ্ট ধরনের হ্রাস পরিবর্তিত হয় এবং সমস্যার সঠিক সেটকে প্রভাবিত করতে পারে। সাধারণভাবে, বহুপদী-সময় হ্রাসের চেয়ে শক্তিশালী হ্রাসগুলি ব্যবহার করা হয়, কারণ পি-এর সমস্ত ভাষা (খালি ভাষা এবং সমস্ত স্ট্রিংয়ের ভাষা ব্যতীত) বহুপদী-সময় হ্রাসের অধীনে পি-সম্পূর্ণ। যদি আমরা এনসি রিডাকশন, অর্থাৎ রিডাকশন ব্যবহার করি যা বহুপদী সংখ্যক প্রসেসরের সাথে সমান্তরাল কম্পিউটারে পলিলোগারিদমিক সময়ে কাজ করতে পারে, তবে সমস্ত পি-সম্পূর্ণ সমস্যা এনসি-র বাইরে থাকে এবং তাই কার্যকরভাবে সমান্তরাল করা যায় না, অপ্রমাণিত অনুমানের অধীনে যে এনসি ষ্ণুপপি। যদি আমরা শক্তিশালী লগ-স্পেস হ্রাস ব্যবহার করি, তবে এটি সত্য থাকে, তবে অতিরিক্তভাবে আমরা শিখি যে সমস্ত পি-সম্পূর্ণ সমস্যাগুলি দুর্বল অপ্রমাণিত অনুমানের অধীনে এল-এর বাইরে থাকে যে এল ষ্ণুপপি। এই পরবর্তী ক্ষেত্রে সেট পি-সম্পূর্ণ ছোট হতে পারে। অনুপ্রেরণা ক্লাস পি, সাধারণত একটি ক্রমিক কম্পিউটারের জন্য সমস্ত "ট্র্যাক্টেবল" সমস্যা নিয়ে গঠিত, ক্লাস এনসি রয়েছে, যা সেই সমস্যাগুলি নিয়ে গঠিত যা সমান্তরাল কম্পিউটারে দক্ষতার সাথে সমাধান করা যেতে পারে। এর কারণ হল সমান্তরাল কম্পিউটারগুলি একটি ক্রমিক মেশিনে সিমুলেট করা যেতে পারে। এনসি = পি কিনা তা জানা যায় না। অন্য কথায়, এটি জানা যায় না যে এমন কোনও সমাধানযোগ্য সমস্যা রয়েছে যা সহজাতভাবে ক্রমিক। ঠিক যেমন এটি ব্যাপকভাবে সন্দেহ করা হয় যে পি এনপির সমান নয়, তাই এটি ব্যাপকভাবে সন্দেহ করা হয় যে এনসি পি-এর সমান নয়। একইভাবে, ক্লাস এল-এ সমস্ত সমস্যা রয়েছে যা লগারিদমিক স্পেসে একটি ক্রমিক কম্পিউটার দ্বারা সমাধান করা যেতে পারে। এই ধরনের যন্ত্রগুলি বহুপদী সময়ে চলে কারণ তাদের বিন্যাসের একটি বহুপদী সংখ্যা থাকতে পারে। এটি সন্দেহ করা হয় যে L ষ্ণ P; অর্থাৎ, কিছু সমস্যা যা বহুপদী সময়ে সমাধান করা যেতে পারে তার জন্য লগারিদমিক স্থানের চেয়েও বেশি প্রয়োজন। একইভাবে পি = এনপি প্রশ্ন বিশ্লেষণের জন্য এনপি-সম্পূর্ণ সমস্যাগুলির ব্যবহারের ক্ষেত্রে, পি-সম্পূর্ণ সমস্যাগুলি, "সম্ভবত সমান্তরাল নয়" বা "সম্ভবত সহজাতভাবে ক্রমিক" সমস্যা হিসাবে দেখা হয়, এনসি = পি প্রশ্ন অধ্যয়নের জন্য একই পদ্ধতিতে কাজ করে। কিছু পি-সম্পূর্ণ সমস্যার সমাধানের সমান্তরাল করার একটি কার্যকর উপায় খুঁজে পাওয়া দেখাবে যে এনসি = পি। এটিকে "অতি-গাণিতিক স্থানের প্রয়োজন সমস্যা" হিসাবেও ভাবা যেতে পারে; একটি পি-সম্পূর্ণ সমস্যার একটি লগ-স্পেস সমাধান (লগ-স্পেস হ্রাসের উপর ভিত্তি করে সংজ্ঞা ব্যবহার করে) বোঝায় এল = পি। এর পিছনের যুক্তিটি এই যুক্তির অনুরূপ যে একটি এনপি-সম্পূর্ণ সমস্যার একটি বহুপদী-সময়ের সমাধান পি = এনপি প্রমাণ করবেঃ যদি আমাদের কাছে পি-এর কোনও সমস্যা থেকে এ-তে এবং এ-এর জন্য একটি এনসি সমাধান থেকে এনসি হ্রাস থাকে, তাহলে এনসি = পি। একইভাবে, যদি আমাদের কাছে পি-এর কোনও সমস্যা থেকে এ-তে কোনও সমস্যা থেকে লগ-স্পেস হ্রাস থাকে, এবং একটি লগ-স্পেস সমাধান থাকে। পি-তে যে কোনও এক্স-এর জন্য, টুরিং মেশিনের এনকোডিং আউটপুট করুন যা এটি বহুপদী-সময়ে গ্রহণ করে, এক্স-এর এনকোডিং এবং পি-এর সাথে সম্পর্কিত বেশ কয়েকটি পদক্ষেপ যা টুরিং মেশিনের সিদ্ধান্ত নেওয়ার ক্রিয়াকলাপের উপর বহুপদী-সময় আবদ্ধ। যদি এবং শুধুমাত্র যদি x এল-এ থাকে তবে মেশিন এম ধাপের মধ্যে x-এ থামে। স্পষ্টতই, যদি আমরা একটি ক্রমিক কম্পিউটারের সাধারণ অনুকরণকে সমান্তরাল করতে পারি (অর্থাৎ। টুরিং মেশিনের সিমুলেশন), তারপর আমরা সেই কম্পিউটারে চলা যে কোনও প্রোগ্রামকে সমান্তরাল করতে সক্ষম হব। যদি এই সমস্যাটি এন. সি-তে হয়, তাহলে পি-তে অন্যান্য সমস্যাগুলিও তাই। যদি ধাপের সংখ্যা বাইনারিতে লেখা হয়, তবে সমস্যাটি এক্সপিটিআইএমই-সম্পূর্ণ। এই সমস্যাটি পি-সম্পূর্ণতা তত্ত্বের একটি সাধারণ কৌশলকে চিত্রিত করে। সমান্তরাল মেশিনে কোনও সমস্যা দ্রুত সমাধান করা যায় কিনা তা নিয়ে আমরা সত্যিই আগ্রহী নই। আমরা কেবল আগ্রহী যে একটি সমান্তরাল যন্ত্র একটি ক্রমিক যন্ত্রের চেয়ে অনেক দ্রুত এটি সমাধান করে কিনা। অতএব, আমাদের সমস্যাটিকে পুনরায় শব্দ করতে হবে যাতে ক্রমিক সংস্করণটি পি-তে থাকে। এই কারণেই এই সমস্যাটির জন্য টি-কে ইউনারি ভাষায় লেখার প্রয়োজন ছিল। যদি একটি সংখ্যা টি বাইনারি সংখ্যা হিসাবে লেখা হয় (n এক এবং শূন্যের একটি স্ট্রিং, যেখানে n = লগ টি), তবে সুস্পষ্ট ক্রমিক অ্যালগরিদম 2n সময় নিতে পারে। অন্যদিকে, যদি টি-কে একটি একক সংখ্যা হিসাবে লেখা হয় (এন-এর একটি স্ট্রিং, যেখানে এন = টি), তবে এটি কেবল সময় নেয়। বাইনারির পরিবর্তে একক সংখ্যায় টি লেখার মাধ্যমে, আমরা সুস্পষ্ট ক্রমিক অ্যালগরিদমকে সূচকীয় সময় থেকে রৈখিক সময়ে কমিয়ে এনেছি। এটি ক্রমিক সমস্যাটিকে পি-তে রাখে। তারপর, এটি এনসি-তে থাকবে যদি এবং শুধুমাত্র যদি এটি সমান্তরাল হয়। অন্যান্য অনেক সমস্যা পি-সম্পূর্ণ হিসাবে প্রমাণিত হয়েছে এবং তাই ব্যাপকভাবে সহজাতভাবে ক্রমিক বলে মনে করা হয়। এগুলির মধ্যে নিম্নলিখিত সমস্যাগুলি অন্তর্ভুক্ত রয়েছে যা কমপক্ষে লগস্পেস হ্রাসের অধীনে পি-সম্পূর্ণ, হয় প্রদত্ত হিসাবে, বা সিদ্ধান্ত-সমস্যা আকারেঃ সার্কিট ভ্যালু প্রবলেম (সিভিপি)-একটি সার্কিট দেওয়া, সার্কিটের ইনপুট এবং সার্কিটের একটি গেট, সেই গেটের আউটপুট গণনা করুন। সি. ভি. পি-র ক্ষেত্রে সীমাবদ্ধ-সি. ভি. পি-র মতো, প্রতিটি গেটের দুটি ইনপুট এবং দুটি আউটপুট (এফ এবং এফ নয়) ব্যতীত, প্রতিটি স্তর ঠিক এবং গেট, বাকিগুলি ও. আর গেট (বা, সমতুল্যভাবে, সমস্ত গেটগুলি ন্যান্ড গেট, বা সমস্ত গেটগুলি এন. ও. আর গেট), একটি গেটের ইনপুটগুলি অবিলম্বে পূর্ববর্তী স্তর থেকে আসে রৈখিক প্রোগ্রামিং-রৈখিক বৈষম্যের সীমাবদ্ধতার সাপেক্ষে একটি রৈখিক ফাংশনকে সর্বাধিক করুন অভিধানগতভাবে প্রথম গভীরতা প্রথম অনুসন্ধান অর্ডারিং-নির্দিষ্ট ক্রমযুক্ত সংলগ্ন তালিকা সহ একটি গ্রাফ দেওয়া হয়েছে, এবং নোডগুলি ইউ এবং ভি, একটি গভীরতা-প্রথম অনুসন্ধান দ্বারা প্ররোচিত গভীরতা-প্রথম অনুসন্ধানে শীর্ষে ভি-এর আগে ভিজিট করা হয়? প্রসঙ্গ-মুক্ত ব্যাকরণের সদস্যপদ-একটি প্রসঙ্গ-মুক্ত ব্যাকরণ এবং একটি স্ট্রিং দেওয়া হলে, সেই স্ট্রিংটি কি সেই ব্যাকরণ দ্বারা তৈরি করা যেতে পারে? হর্ন-সন্তুষ্টি-হর্ন ধারাগুলির একটি সেট দেওয়া হলে, এমন কোনও পরিবর্তনশীল অ্যাসাইনমেন্ট আছে যা তাদের সন্তুষ্ট করে? এটি বুলিয়ান সন্তোষজনকতার সমস্যার পি-এর সংস্করণ। গেম অফ লাইফ-কনওয়ের গেম অফ লাইফ, একটি নির্দিষ্ট কোষ এবং একটি সময় টি (ইউনারিতে)-এর প্রাথমিক বিন্যাসের পরিপ্রেক্ষিতে, সেই কোষটি কি টি ধাপের পরে জীবিত? LZW (অ্যালগরিদম) (1978 দৃষ্টান্ত) ডেটা কম্প্রেশন-প্রদত্ত স্ট্রিং s এবং t, কি LZ78 পদ্ধতিতে s সংকুচিত করলে অভিধানে t যোগ হবে? (লক্ষ্য করুন যে জিজিপের মতো এলজেড77 সংকোচনের জন্য, এটি অনেক সহজ, কারণ সমস্যাটি "ইজ টি ইন এস?"-এ কমে যায়।) আংশিক প্রকারের জন্য অনুমান টাইপ করুন-ল্যাম্বডা ক্যালকুলাস থেকে একটি অপ্রচলিত শব্দ দেওয়া হলে, এই শব্দটির আংশিক প্রকার আছে কিনা তা নির্ধারণ করুন। উপরের বেশিরভাগ ভাষা হ্রাসের আরও শক্তিশালী ধারণার অধীনে পি-সম্পূর্ণ, যেমন অভিন্ন বহু-এক হ্রাস, ডিএলওজিটিআইএমই হ্রাস বা পলিলোগারিদমিক অনুমান। পি-তে একটি প্রদত্ত সমস্যা পি-সম্পূর্ণ প্রমাণ করার জন্য, একজন সাধারণত একটি পরিচিত পি-সম্পূর্ণ সমস্যাকে প্রদত্ত সমস্যার তুলনায় কমিয়ে আনার চেষ্টা করে। 1999 সালে, ওগিহারার কাজের উপর ভিত্তি করে জিন-ই কাই এবং ডি. শিবকুমার দেখিয়েছিলেন যে যদি একটি বিরল ভাষা থাকে যা পি-সম্পূর্ণ হয়, তবে এল = পি. পি-সম্পূর্ণ সমস্যাগুলি বিভিন্ন সময়ের জটিলতার সাথে সমাধানযোগ্য হতে পারে। উদাহরণস্বরূপ, সার্কিট মান সমস্যাটি একটি টপোলজিকাল সাজানোর মাধ্যমে রৈখিক সময়ে সমাধান করা যেতে পারে। অবশ্যই, যেহেতু একটি পি-সম্পূর্ণ সমস্যার হ্রাসের বিভিন্ন সময় জটিলতা থাকতে পারে, এই সত্যটি বোঝায় না যে পি-এর সমস্ত সমস্যা রৈখিক সময়েও সমাধান করা যেতে পারে। পি-সম্পূর্ণ হিসাবে পরিচিত নয় এমন সমস্যাগুলি কিছু এনপি-সমস্যা এনপি-সম্পূর্ণ বা পি হিসাবে পরিচিত নয়। ফ্যাক্টরিং, গ্রাফ আইসোমরফিজম, প্যারিটি গেমস) কঠিন বলে সন্দেহ করা হয়। একইভাবে পি-তে এমন সমস্যা রয়েছে যা পি-সম্পূর্ণ বা এনসি হিসাবে পরিচিত নয়, তবে সমান্তরাল করা কঠিন বলে মনে করা হয়। উদাহরণগুলির মধ্যে রয়েছে দুটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ বিভাজক খুঁজে বের করার সিদ্ধান্ত সমস্যা রূপগুলি, দুটি সংখ্যা দেওয়া হলে বর্ধিত ইউক্লিডীয় অ্যালগরিদম কী উত্তর দেবে তা নির্ধারণ করা এবং বড় পূর্ণসংখ্যা ওজনের সাথে একটি গ্রাফের সর্বাধিক ওজনের মিল গণনা করা। রেফারেন্স গ্রীনলা, রেমন্ড, জেমস হুভার এবং ওয়াল্টার রুজো। 1995 সালে। সমান্তরাল গণনার সীমাবদ্ধতা; পি-সম্পূর্ণতা তত্ত্ব। । - তত্ত্বটি বিকাশ করে, তারপর 96 টি পি-সম্পূর্ণ সমস্যা তালিকাভুক্ত করে। সাতোরু মিয়ানো, শুজি শিরাইশি এবং তাকায়োশি শৌদাই। পি-সম্পূর্ণ সমস্যার একটি তালিকা। কিউশু বিশ্ববিদ্যালয়, আরআইএফআইএস-টিআর-সিএস-17। 1990 সালের ডিসেম্বর। জটিলতার ক্লাস