Computational indistinguishability
গণনামূলক জটিলতা এবং ক্রিপ্টোগ্রাফিতে, বিতরণের দুটি পরিবার গণনামূলকভাবে অবিচ্ছেদ্য যদি কোনও দক্ষ অ্যালগরিদম নগণ্য সম্ভাবনা ব্যতীত তাদের মধ্যে পার্থক্য বলতে না পারে। আনুষ্ঠানিক সংজ্ঞা ধরা যাক এবং একটি নিরাপত্তা পরামিতি এন দ্বারা সূচীভুক্ত দুটি বন্টন এনসেম্বল হতে হবে (যা সাধারণত ইনপুটের দৈর্ঘ্যকে বোঝায়); আমরা বলি যে তারা গণনামূলকভাবে অবিচ্ছেদ্য যদি কোনও অভিন্ন সম্ভাবনাময় বহুপদী সময় অ্যালগরিদম এ-এর জন্য, নিম্নলিখিত পরিমাণটি এন-এ একটি নগণ্য ফাংশনঃ চিহ্নিত। অন্য কথায়, প্রতিটি দক্ষ অ্যালগরিদম আচরণ হিসাবে উল্লেখযোগ্যভাবে পরিবর্তিত হয় না যখন সীমাতে ডিএন বা এন অনুসারে নমুনা দেওয়া হয়। গণনামূলক অবিচ্ছেদ্যতার আরেকটি ব্যাখ্যা হল যে, পলিনোমিয়াল-টাইম অ্যালগরিদমগুলি সক্রিয়ভাবে দুটি এনসেম্বলের মধ্যে পার্থক্য করার চেষ্টা করে তা করতে পারে নাঃ যে এই ধরনের কোনও অ্যালগরিদম কেবল অনুমান করার চেয়ে নগণ্যভাবে ভাল কাজ করবে। সম্পর্কিত ধারণাগুলি সংজ্ঞায় অন্তর্নিহিত শর্ত হল যে অ্যালগরিদমকে অবশ্যই বিতরণগুলির মধ্যে একটি থেকে একক নমুনার উপর ভিত্তি করে সিদ্ধান্ত নিতে হবে। কেউ এমন একটি পরিস্থিতি কল্পনা করতে পারে যেখানে অ্যালগরিদম দুটি বিতরণের মধ্যে পার্থক্য করার চেষ্টা করে, যতগুলি প্রয়োজন ততগুলি নমুনা অ্যাক্সেস করতে পারে। তাই একাধিক নমুনার দিকে তাকিয়ে পলিনোমিয়াল-টাইম অ্যালগরিদম দ্বারা আলাদা করা যায় না এমন দুটি এনসেম্বলকে পলিনোমিয়াল-টাইম স্যাম্পলিং দ্বারা অবিচ্ছেদ্য বলে মনে করা হয়। যদি পলিনোমিয়াল-টাইম অ্যালগরিদম পলিনোমিয়াল সময়ে নমুনা তৈরি করতে পারে, অথবা একটি র্যান্ডম ওরাকলে অ্যাক্সেস থাকে যা এর জন্য নমুনা তৈরি করে, তবে পলিনোমিয়াল-টাইম স্যাম্পলিং দ্বারা অবিচ্ছেদ্যতা গণনামূলক অবিচ্ছেদ্যতার সমতুল্য। রেফারেন্স বাহ্যিক লিঙ্ক ইয়েহুদা লিন্ডেল। ডোনাল্ড বিভার এবং সিলভিও মিকালি এবং ফিলিপ রোগাওয়ের ক্রিপ্টোগ্রাফির ভূমিকা, দ্য রাউন্ড কমপ্লেক্সিটি অফ সিকিউর প্রোটোকলস (এক্সটেন্ডেড অ্যাবস্ট্রাক্ট), 1990, পৃ। 503-513 শফি গোল্ডওয়াসার এবং সিলভিও মিকালি। সম্ভাব্য এনক্রিপশন। জে. সি. এস. এস, 28 (2): 270-299,1984 ওডেড গোল্ডরিখ। ক্রিপ্টোগ্রাফির ভিত্তিঃ খণ্ড 2-মৌলিক প্রয়োগ। কেমব্রিজ ইউনিভার্সিটি প্রেস, 2004। জোনাথন কাটজ, ইয়েহুদা লিন্ডেল, "আধুনিক ক্রিপ্টোগ্রাফির পরিচিতিঃ নীতি ও প্রোটোকল", চ্যাপম্যান অ্যান্ড হল/সিআরসি, 2007 অ্যালগরিদমিক তথ্য তত্ত্ব