টুরিং মেশিন

হাল্টিং প্রবলেম

গণিত বা কম্পিউটার বিজ্ঞানের সব সমস্যাই কি সমাধানযোগ্য? আমরা জানি NP ক্যাটাগরির সমস্যাগুলোকে পলিনোমিয়াল সময়ে সমাধান করার সম্ভব নাকি সেটা জানা এখন পর্যন্ত সম্ভব হয় নি, কিন্তু ইনপুটের আকার যথেষ্ট ছোট হলে অথবা তোমার হাতে অসীম সময় এবং মেমরি থাকলে NP সমস্যাও এক্সপোনেনশিয়াল সময়ে সমাধান করা সম্ভব। কিন্তু এমন কিছু সমস্যা আছে যেটা তোমার হাতে যত বড় সুপার কম্পিউটারই থাকুক সমাধান করা সম্ভব না। এখানে আমি ধরে নিচ্ছি আমাদের কম্পিউটারগুলো টুরিং মেশিন কম্পিউটেবল। (টুরিং মেশিন কি মনে না থাকলে আগে আমার এই লেখাটা পড়ো) হাল্টিং প্রবলেম (Halting Problem) এমনই একটা সমস্যা যার কোনো সমাধান নেই। তোমাকে একট...
Read More

কমপ্লেক্সিটি ক্লাস(P-NP, টুরিং মেশিন ইত‍্যাদি)

আমরা যখন প্রবলেম সলভ করতে করতে মাথার চুল ছিড়ে ফেলি তখন প্রায়ই এমন কিছু প্রবলেম সামনে আসে যেগুলো সলভ করতে গেলে সবথেকে শক্তিশালী কম্পিউটারও হাজার হাজার বছর লাগিয়ে দিবে। বড় বড় কম্পিউটার বিজ্ঞানীরা যখন দিন-রাত চিন্তা করেও এগুলো সলভ করতে পারলেননা তখন তারা এই প্রবলেমগুলোকে কিছু ক্যাটাগরিতে ফেলে দিয়ে বললেন “এই ক্যাটাগরির প্রবলেমগুলো সলভ করার সাধ্য এখনো আমাদের হয়নি, তোমরা কেও পারলে সলভ করে দিয়ে ১০ লক্ষ ডলার পুরস্কার নিয়ে যাও”। সেগুলোকেই আমরা NP-complete, NP-hard ইত্যাদি নামে চিনি। NP ক্যাটাগরির প্রবলেমগুলো কম্পিউটার সায়েন্সে খুব বিখ্যাত। যেমন একটা গ্রাফে সবথেকে লম্বা পথ খুজে বের করা, ৩টা রঙ...
Read More