কম্পিউটার বিজ্ঞানের ভিত্তি/গণনার সীমাবদ্ধতা

গণনার সীমাবদ্ধতা

আমরা কম্পিউটিংয়ের কিছু বড় ধারণা অধ্যয়ন করেছি, যা আমাদের তথ্য প্রক্রিয়ার মাধ্যমে আশ্চর্যজনক কাজ সম্পাদন করতে দেয়। আপনি হয়তো এই ধারণাটি অর্জন করেছেন যে আমরা যদি তথ্যের পরিমাণ নির্ধারণ করতে পারি এবং একটি অ্যালগরিদম ডিজাইন করতে পারি তবে আমরা কম্পিউটিং ব্যবহার করে যে কোনও সমস্যা সমাধান করতে পারি। এই অধ্যায়ে আমরা গণনার সীমা সম্পর্কে তত্ত্বটি অধ্যয়ন করব। কম্পিউটিং আমাদের জন্য কী করতে পারে তার তাত্ত্বিক এবং ব্যবহারিক সীমা রয়েছে।

টুরিং মেশিন রিভিজিটেড

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

হল্টিং সমস্যা

১৯৩৬ সালে অ্যালান টুরিং প্রমাণ করেছিলেন যে সমস্ত সম্ভাব্য প্রোগ্রাম-ইনপুট জোড়ার জন্য হাল্টিং সমস্যা সমাধানের জন্য একটি সাধারণ অ্যালগরিদম বিদ্যমান থাকতে পারে না, যেমনঃ হাল্টিং সমস্যাটি কম্পিউটিং ব্যবহার করে সমাধানযোগ্য নয়। আরও সুনির্দিষ্টভাবে, থামার সমস্যাটি অনিবার্য কারণ এটি সবচেয়ে সহজ ধরনের প্রশ্ন যা হ্যাঁ বা না (সিদ্ধান্ত) প্রশ্নের উত্তর দেয়ঃ কোনও ইনপুট দেওয়া হলে কোনও প্রোগ্রাম শেষ পর্যন্ত থামবে (থামবে) কিনা। স্পষ্টতই, এটি থামবে কিনা তা দেখার জন্য ইনপুট দিয়ে প্রোগ্রামটি চালানো অসম্ভব কারণ প্রোগ্রামে একটি অসীম লুপ থাকলে এটি চিরকালের জন্য সময় নিতে পারে। ধারণাটি হল প্রদত্ত ইনপুট সহ একটি প্রোগ্রাম বিশ্লেষণ করা যাতে এটি থামবে কিনা তা নির্ধারণ করা যায়।

অ্যালান টুরিং প্রমাণ করেন যে, থামার সমস্যাটি দ্বন্দ্ব দ্বারা প্রমাণ নামক একটি প্রমাণ কৌশল দ্বারা অনিবার্য। উইকিপিডিয়ায় কিছু নমুনা প্রমাণ পর্যালোচনা করা খুব সহায়ক হবে। আরেকটি ধ্রুপদী উদাহরণ হল সংখ্যা তত্ত্বে ইউক্লিডের উপপাদ্যের প্রমাণ, যা দাবি করে যে অসীম সংখ্যক মৌলিক সংখ্যা রয়েছে। দ্বন্দ্ব দ্বারা সমস্ত প্রমাণ একটি অনুমান দিয়ে শুরু হয় যে আমরা যে প্রস্তাবটি প্রমাণ করার চেষ্টা করছি তা মিথ্যা, বৈধ পদক্ষেপের যৌক্তিক ক্রম অনুসরণ করে এবং এমন একটি সিদ্ধান্তে পৌঁছায় যা স্পষ্টভাবে মিথ্যা বা পরস্পরবিরোধী, যা মিথ্যাও কারণ একটি বিবৃতি সত্য বা মিথ্যা হতে পারে তবে কখনই উভয়ই নয়।

যদি আমরা ধরে নিই যে থামার সমস্যাটি নির্ণায়ক/সমাধানযোগ্য হয় তবে আমাদের একটি অ্যালগরিদম ডিজাইন করতে এবং এটিকে এমন একটি প্রোগ্রাম হিসাবে প্রয়োগ করতে সক্ষম হওয়া উচিত যা আমাদের জন্য সমস্যার সমাধান করে। প্রোগ্রামটিকে ইনপুট প্যারামিটার হিসাবে প্রোগ্রামে একটি প্রোগ্রাম এবং ইনপুট নিতে হবে এবং উত্তরটি ফেরত দিতে হবে-প্রোগ্রামটি ইনপুটটিতে থামবে কি না। এই জাতীয় প্রোগ্রামটি অদ্ভুত মনে হতে পারে কারণ এটি একটি প্রোগ্রামকে ইনপুট হিসাবে নেয়, তবে আমরা এই জাতীয় প্রোগ্রামগুলি দেখেছি, যেমনঃ স্ন্যাপ-এ উচ্চতর অর্ডার ফাংশন ব্লক! ইনপুট হিসাবে একটি ব্লক (প্রোগ্রাম) নেয় এবং একটি ইন্টারপ্রেটার প্রোগ্রাম ডেটা হিসাবে একটি প্রোগ্রামের সোর্স কোড নেয় এবং প্রোগ্রামটি চালায়। প্রোগ্রামগুলি হল ডেটা এবং টো-এর মধ্যে কোনও অভ্যন্তরীণ পার্থক্য নেই। নিম্নলিখিত প্রমাণ দেখায় যে থামানো প্রশ্নের উত্তর দেয় এমন একটি প্রোগ্রাম বিদ্যমান থাকতে পারে না।

অনুমান করুন যেমন একটি প্রোগ্রাম A বিদ্যমান। A(P, D) -> ইনপুট ডেটাতে প্রোগ্রাম P থামবে কিনা আমরা অন্য একটি প্রোগ্রাম B তৈরি করতে পারি যা একটি প্রোগ্রামকে ইনপুট হিসাবে নেয়। প্রোগ্রাম B এর ভিতরে আমরা প্রদত্ত ইনপুট সহ প্রোগ্রাম A কে কল করতে পারি যে ইনপুট প্রোগ্রামটি ইনপুট ডেটা হিসাবে নিজেই থামবে কিনা এবং যদি উত্তর না হয় (থেমে যাবে না) তবে আমরা থামি (রিটার্ন) এবং যদি উত্তর হ্যাঁ হয় (থেমে যাবে) ) চিরতরে লুপ।

 B(P):
   if A(P, P) = yes 
     infinite loop
   else
     return

১।আমরা যদি ইনপুট হিসাবে প্রোগ্রাম B-কে নিজেই ফিড করি তবে কী হবে? নাকি আরও সহজভাবে, প্রোগ্রাম B কি নিজেই থেমে যাবে? অনুশীলনের দুটি সম্ভাব্য ফলাফল রয়েছেঃ প্রোগ্রাম বি নিজেই থেমে যায় বা প্রোগ্রাম B চিরকালের জন্য চলে যখন নিজেই ইনপুট হয়। প্রকৃত ফলাফল/ফলাফল নির্ভর করে ইনসাইড প্রোগ্রাম B নামক প্রোগ্রাম A -এর ফলাফলের উপর। যদি প্রোগ্রাম B নিজেই থেমে যায়, প্রোগ্রাম B-এর নকশা অনুযায়ী এটি চিরকালের জন্য চলতে হবে কারণ প্রোগ্রাম B-এর সাথে প্রোগ্রাম A উভয় ইনপুট হিসাবে একটি অসীম লুপ চালানো উচিত। অন্যদিকে, যদি প্রোগ্রাম বি নিজেই থেমে না যায়, তবে প্রোগ্রাম বি থেকে আউটপুটটি ইনপুট হিসাবে অবিলম্বে ফিরে আসা উচিত। যেভাবেই হোক, এটা একটা দ্বন্দ্ব।

২। এ পর্যন্ত, আমরা একটি অনুমান করেছি, যৌক্তিকভাবে সঠিক পদক্ষেপের একটি সেট অনুসরণ করেছি এবং অবশেষে দ্বন্দ্বে পৌঁছেছি। কি ভুল হয়ে গেল? দ্বন্দ্বগুলি সত্য হতে পারে না কারণ সেগুলি যৌক্তিকভাবে অসম্ভব। পদক্ষেপগুলি যৌক্তিকভাবে সঠিক এবং একমাত্র অংশ যা ভুল হতে পারে তা হল অনুমান। অতএব, অনুমানটি সত্য হতে পারে না,যেমনঃ থামার সমস্যাটি নির্ণয়যোগ্য নয়। এখানে একটি ইউটিউব ভিডিও রয়েছে যা এর প্রমাণ দেয়ঃ https://www.youtube.com/watch?v=92WHN-pAFCs

জটিল সমস্যা

হাল্টিং সমস্যাটি কঠিন কারণ এটি নীতিগতভাবেও অ্যালগরিদমিকভাবে সমাধানযোগ্য নয়। অন্যান্য কঠিন সমস্যা রয়েছে যা নীতিগতভাবে সমাধানযোগ্য তবে বাস্তবে সেগুলি সমাধান করা অসম্ভব হওয়ার কাছাকাছি। আপনি দেখতে পাচ্ছেন, আমরা সর্বাধিক পরিচিত অ্যালগরিদমগুলির কার্যকারিতা দ্বারা সমস্যাগুলিকে শ্রেণীবদ্ধ করতে পারি। যদি একটি দ্রুত অ্যালগরিদম ব্যবহার করে কোনও সমস্যা সমাধান করা যায়, তবে সমস্যাটি সহজ কারণ আমরা দ্রুত সমাধানের জন্য একটি কম্পিউটার ব্যবহার করতে পারি। বিপরীতে, আমরা জানি যে সর্বাধিক পরিচিত অ্যালগরিদমটি কোনও সমস্যা সমাধান করতে দীর্ঘ সময় নেয়, এটি কঠিন কারণ কম্পিউটারগুলি এটি দ্রুত সমাধান করতে পারে না।

অ্যালগরিদম জটিলতা তত্ত্ব ব্যবহার করে আমরা প্রতিটি অ্যালগরিদমকে অ্যালগরিদমের জটিলতা অনুযায়ী একটি নির্দিষ্ট বিভাগে রাখতে পারি। যদি কোনও বিভাগের বিগ-ও নোটেশনে শুধুমাত্র পলিনোমিয়াল পদ থাকে, তবে এই বিভাগের অ্যালগরিদম ব্যবহার করে সমাধানযোগ্য সমস্যাগুলিকে পি সমস্যা বলা হয় (পলিনোমিয়াল সময় সমাধান বিদ্যমান) যেমন $O(1)$, $log_{2}(N)$$O(N)$, এবং $O(N^{2})$। $P$ সমস্যাগুলি কম্পিউটারের জন্য সহজ সমস্যা। পলিনোমিয়াল টাইম সলিউশন ব্যতীত সমস্যাগুলির মধ্যে এমন সমস্যা রয়েছে যে আমরা যদি সমাধানটি অনুমান করতে পারি তবে এটি পলিনোমিয়াল টাইমে যাচাই করা যেতে পারে। উদাহরণস্বরূপ, পূর্ণসংখ্যা ফ্যাক্টরাইজেশন (বা মৌলিক পচন) সমস্যার কোনও পরিচিত বহুপদী সময় সমাধান নেই তবে একটি উত্তর দেওয়া হলে আমরা কেবল ফ্যাক্টরগুলিকে গুণ করে এবং ফলাফলটিকে পূর্ণসংখ্যার সাথে তুলনা করে খুব দ্রুত এটি যাচাই করতে পারি। এই ধরনের সমস্যাকে বলা হয় $NP$ (নন-ডিটারমিনিস্টিক পলিনোমিয়াল) সমস্যা।

সমষ্টিগতভাবে আমরা এমন সমস্যাগুলিকে কল করি যা জটিল সমস্যাগুলি সমাধান করতে খুব বেশি সময় নেয়, যার মধ্যে এক্সপোনেনশিয়াল সময় ($O(2^{N})$) বা পলিনোমিয়াল সময় সমাধানগুলির সাথে সেরা অ্যালগরিদমের সমস্যা রয়েছে তবে সূচকটি খুব বড়, যেমন $O(N^{15})$।

যদি কোনও সমস্যার সেরা অ্যালগরিদমিক সমাধান $O(2^{N})$, যখন $N=100$ এবং একটি কম্পিউটার প্রতি সেকেন্ডে $10^{12}$ অপারেশন করে তবে কম্পিউটারে সমস্যাটি সমাধান করতে $4\times 10^{10}$ বছর (মহাবিশ্বের বয়স) সময় লাগবে।

P বনাম NP

স্পষ্টতই P হল NP -র একটি উপসেট কারণ এনপি শুধুমাত্র পলিনোমিয়াল উত্তর যাচাইকরণ সময় দ্বারা সংজ্ঞায়িত করা হয় এবং পলিনোমিয়াল সময় (P)-এ একটি সমস্যা সমাধান করতে সক্ষম হওয়া অবশ্যই তার জন্য যোগ্য। P NP এর একটি যথাযথ উপসেট কিনা বা অন্য কথায়,$P=NP$ কম্পিউটার বিজ্ঞানের একটি উন্মুক্ত প্রশ্ন হিসাবে রয়ে গেছে। এর উত্তর কেউ জানে না। আপনি যদি সহস্রাব্দ পুরস্কার সমস্যাগুলির মধ্যে একটি হিসাবে এটি সমাধান করতে পারেন তবে আপনি এক মিলিয়ন ডলার জিততে পারেন।

এই P বনাম NP আক্রমণ করতে। NP সমস্যা তাত্ত্বিক কম্পিউটার বিজ্ঞানী NP -সম্পূর্ণ সমস্যা নামে আরেকটি বিভাগকে সংজ্ঞায়িত করেছেন। তিনটি বিভাগের মধ্যে সম্পর্ক নিম্নলিখিত চিত্রে চিত্রিত করা হয়েছে।

এই বিভাগের সমস্ত সমস্যাগুলি হল একটি বিশেষ বৈশিষ্ট্য ভাগ করে নেওয়া এনপি সমস্যা-অন্যান্য সমস্ত এনপি-সম্পূর্ণ সমস্যাগুলি বহুপদী সময়ে প্রতিটি এনপি-সম্পূর্ণ সমস্যায় অনুবাদ/হ্রাস করা যেতে পারে। এনপি-সম্পূর্ণতার প্রকৃতির কারণে যদি আমরা এই বিভাগের যে কোনও একক সমস্যা সমাধান করতে পারি তবে আমরা প্রমাণ করেছি যে সমস্ত এনপি সমস্যাগুলি বহুপদী সময়ে সমাধানযোগ্য, যেমন $P=NP$। আমরা যে কোনও NP সমস্যা নিতে পারি, এটিকে সমাধান করা এনপি-সম্পূর্ণ সমস্যায় অনুবাদ করতে পারি এবং বহুপদী সময়ে সমস্যাটি সমাধান করতে পারি। সামগ্রিক সময় এখনও পলিনোমিয়াল কারণ পলিনোমিয়াল + পলিনোমিয়াল পলিনোমিয়াল। হাজার হাজার NP-সম্পূর্ণ সমস্যা আবিষ্কৃত হয়েছে কিন্তু সেগুলির কোনওটিরই সমাধান হয়নি। NP-সম্পূর্ণ সমস্যাগুলি, এক অর্থে, সবচেয়ে কঠিন পরিচিত সমস্যা।

বেশিরভাগ কম্পিউটার বিজ্ঞানী বিশ্বাস করেন $P\neq NP$ কারণ অন্যথায় এর প্রভাব পড়ে। "সৃজনশীল লাফ" অদৃশ্য হয়ে যাবে কারণ একটি সমস্যা সমাধান করা সঠিক উত্তর চিনতে সক্ষম হওয়ার মতোই সহজ। বেশিরভাগ এনক্রিপশন অ্যালগরিদম গণনামূলকভাবে নিরাপদ কারণ সেগুলি ভেঙে ফেলা এনপি-সমস্যা-কোনও পরিচিত দক্ষ বহুপদী সময় সমাধান নেই। যদি $P=NP$ হয় তবে সমস্ত এনক্রিপশন ভেঙে যাবে।

কম্পিউটার বিজ্ঞানে অন্যান্য অমীমাংসিত সমস্যা রয়েছে। আপনি এই ধরনের সমস্যার একটি তালিকা পেতে পারেন https://en.wikpedia.org/wiki/List_of_unsolved_problems_in_computer_science