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