Sparse language
গণনামূলক জটিলতা তত্ত্বে, একটি বিরল ভাষা হল একটি আনুষ্ঠানিক ভাষা (স্ট্রিংয়ের একটি সেট) যাতে জটিলতার ফাংশন, ভাষায় n দৈর্ঘ্যের স্ট্রিংয়ের সংখ্যা গণনা করে, n-এর একটি বহুপদী ফাংশন দ্বারা আবদ্ধ থাকে। এগুলি প্রাথমিকভাবে অন্যান্য শ্রেণীর সাথে জটিলতা শ্রেণীর NP-এর সম্পর্কের অধ্যয়নে ব্যবহৃত হয়। সমস্ত বিরল ভাষার জটিলতা শ্রেণীকে স্পার্স বলা হয়। বিক্ষিপ্ত ভাষাগুলিকে বিক্ষিপ্ত বলা হয় কারণ n দৈর্ঘ্যের মোট 2n স্ট্রিং রয়েছে এবং যদি কোনও ভাষায় বহুপদীভাবে এগুলির অনেকগুলি থাকে, তবে n দৈর্ঘ্যের স্ট্রিংয়ের অনুপাত যা এটি ধারণ করে তা n বৃদ্ধির সাথে সাথে দ্রুত শূন্যে চলে যায়। সমস্ত ইউনারি ভাষা বিরল। একটি অ-তুচ্ছ বিরল ভাষার উদাহরণ হল বাইনারি স্ট্রিংয়ের সেট যা কিছু নির্দিষ্ট k-এর জন্য ঠিক k 1 বিট ধারণ করে; প্রতিটি n-এর জন্য, ভাষায় কেবল স্ট্রিং রয়েছে, যা nk দ্বারা আবদ্ধ। অন্যান্য জটিলতা শ্রেণীর সাথে সম্পর্ক স্পার্সে ট্যালি, ইউনারি ভাষার শ্রেণী রয়েছে, কারণ এগুলির যে কোনও একটি দৈর্ঘ্যের সর্বাধিক একটি স্ট্রিং রয়েছে। যদিও পি/পলির সমস্ত ভাষা বিরল নয়, তবে পি/পলির যে কোনও ভাষা থেকে একটি বিরল ভাষায় একটি বহুপদী-সময় টুরিং হ্রাস রয়েছে। ফরচুন 1979 সালে দেখিয়েছিল যে যদি কোনও বিরল ভাষা সহ-এনপি-সম্পূর্ণ হয়, তবে পি = এনপি; 1982 সালে মাহানি এটি দেখাতে ব্যবহার করেছিলেন যে যদি কোনও বিরল ভাষা এনপি-সম্পূর্ণ হয়, তবে পি = এনপি (এটি মাহানির উপপাদ্য)। 1991 সালে ওগিহারা এবং ওয়াতানাবে বাম-সেটের উপর ভিত্তি করে এর একটি সহজ প্রমাণ দিয়েছিলেন। মাহানির যুক্তিতে আসলে বিরল ভাষাটি এনপিতে থাকার প্রয়োজন নেই (কারণ একটি এনপি-হার্ড স্পার্স সেটের অস্তিত্ব একটি এনপি-সম্পূর্ণ স্পার্স সেটের অস্তিত্বকে বোঝায়), তাই একটি বিরল এনপি-হার্ড সেট থাকে যদি এবং শুধুমাত্র যদি পি = এনপি হয়। উপরন্তু, যদি এবং শুধুমাত্র যদি এন. পি-তে বিরল ভাষাগুলি বিদ্যমান থাকে যা পি-তে নেই। একটি এন. পি-সম্পূর্ণ ভাষা থেকে একটি বিরল ভাষায় টুরিং হ্রাস (মহানির উপপাদ্য থেকে কার্প হ্রাসের বিপরীতে) হয় যদি এবং শুধুমাত্র যদি। 1999 সালে, ওগিহারার কাজের উপর ভিত্তি করে জিন-ই কাই এবং ডি. শিবকুমার দেখিয়েছিলেন যে যদি একটি বিরল পি-সম্পূর্ণ সমস্যা থাকে, তবে এল = পি। প্রিয় উপপাদ্যঃ ছোট সেট। 18ই এপ্রিল, 2006। উইলিয়াম গ্যাসার্ক। স্পার্স সেটস (মহানিকে শ্রদ্ধা)। 29শে জুন, 2007। আনুষ্ঠানিক ভাষা গণনামূলক জটিলতা তত্ত্ব