জটিলতা ও তার পরিমাপ

জন ওয়াট্রস

(U Waterloo)

 

21 Aug 2020

Link: https://bigyan.org.in/measurement-of-complexity

সৌমিকঃ  আমরা জটিলতার তত্ত্ব (complexity theory) নিয়ে খুব ঘরোয়াভাবে একটু আড্ডা দেব, প্রধানতঃ হাই স্কুল এবং সদ্য কলেজে পা রাখা ছাত্রছাত্রীদের কথা মাথায় রেখে। আচ্ছা, কম্পিউটার সায়েন্স বলতে তো আমাদের প্রথমেই “কোডিং”-এর কথা মাথায় আসে। অথবা মেশিন লার্নিং বা কম্পিউটার অ্যাপ বানানো। আপনি তো এসব করেন না, আপনি একজন “থিওরিটিক্যাল কম্পিউটার সাইন্টিস্ট”। সেই ব্যাপারে যদি একটু বিশদে বলেন।

জনঃ আসলে থিওরিটিক্যাল কম্পিউটার সায়েন্স মানে কম্পিউটার বিষয়ক অঙ্ক কষা। এখানে আমরা কম্পিউটারকে একটা গণনা করার যন্ত্র হিসেবে দেখি, আর জিজ্ঞেস করি কোন কোন গণনার কাজ কম্পিউটার করতে পারবে, আর কোন কোন কাজ একেবারেই পারবেনা। যেমন অনেক এমন কাজ আছে যেগুলো কম্পিউটারের  জন্য বেশ কঠিন। কিছু কাজ তো কম্পিউটার একেবারেই করতে পারবে না, তা সে যতক্ষণই চলুক না কেন। আর কিছু কাজ এমনই শক্ত যে কম্পিউটার তা করতে প্রচুর সময় লাগায় – এতো বেশি সময় যে আমাদের জীবনকালে তা শেষ হবে না। এমনকি, যদি সবচেয়ে কম অপচয়শীল আর সবচেয়ে উন্নত পদ্ধতিও ব্যবহার করি, তাহলেও সেই কাজগুলো করতে এতটাই সময় লাগে যে পৃথিবী ধ্বংস হয়ে যাওয়ার আগে — এমনকি সূর্য মরে যাওয়ার আগেও — সেগুলো শেষ হবে না। কাজ বলতে আমি কিন্তু প্রেমের কবিতার বা ভালোবাসার গানের মর্মার্থ উদ্ধারের কথা বলছি না, আমি বলছি একদম কাঠখোট্টা অঙ্কের কথা!

রাজীবুলঃ  এক্ষেত্রে খুব ক্ষমতাশালী  কম্পিউটারের কথা হচ্ছে নিশ্চয়, যে কোন কম্পিউটার নয় …

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

রাজীবুলঃ  এক্ষেত্রে ঠিক কোন ধরণের কাজের কথা বলছেন?

জনঃ যেমন ধরুন, কোনও একটা অনুকূলিকরণ সমস্যা বা optimization problem — কয়েকটা জিনিসকে কিছু constraint বা প্রতিবন্ধকতা অনুযায়ী সাজিয়ে ফেলা। যদি সবচেয়ে ভালোভাবে সাজাতে চান, যাকে বলে optimal ভাবে, সেটা একটা কম্পিউটারের পক্ষে করা খুব খুব শক্ত।

রাজীবুলঃ  যেমন থিসিস কমিটির ৫ জনকে একসঙ্গে একই দিনে জড়ো করা [১]।

(হাসি)

জনঃ বা ধরুন, কিছু সংখ্যক শিক্ষার্থীর জন্য ক্লাসের সময়সূচি তৈরি করা, যেখানে প্রতিটি শিক্ষার্থীর কিছু নির্দিষ্ট প্রতিবন্ধকতা আছে। অথবা একটি সার্কিট বোর্ডে সবদিক বিবেচনা করে চিপ্‌ বসানো, যাতে বোর্ডটা চলার সময় খুব বেশি গরম না হয়ে যায় [২]।

কিংবা আরও সূক্ষ্ম সমস্যা: ধরুণ কম্পিউটারকে একটা অঙ্কের উপপাদ্য দিলেন, আর সেটি প্রমাণ করতে বললেন। বা উপপাদ্যটার প্রমাণ কতবড় হবে সেটা বেঁধে দিলেন; এবার কম্পিউটারকে বলতে হবে সেই সংখ্যক অক্ষরের  কোনও প্রমাণ হতে পারে কিনা। যেহেতু এরম হুটহাট প্রমাণ বের করে দিতে বেশ স্বাধীন ভাবনাচিন্তা ও সৃজনশীলতা লাগে, একটা কম্পিউটার সেটা খুব একটা পারে না। তার একটা কারণ হলো এরম কিছু বের করতে গেলে অনেক কটা প্রমাণ ধরে ধরে খুঁজতে হবে – পুরনো হলঘরে ফাইল ধরে ধরে খোঁজার মত। এত বেশি প্রমাণ আছে যে খোঁজাটা সময়ে কুলোবে না।

রাজীবুলঃ  এইটা তাহলে একটি কঠিন কাজের উদাহরণ।

জনঃ হ্যাঁ, বাস্তব জীবনে এরকম অনেক কাজ দেখা যায়। এরকম অনেক কাজ আছে যাদেরকে NP complete বলা হয়, এবং সেগুলোর প্রয়োগ বাস্তব জীবনে যথেষ্ট গুরুত্বপূর্ণ। কিন্তু সেইসব সমস্যা সাধারণ কম্পিউটার ছেড়েই দিলাম, কোয়ান্টাম কম্পিউটার দিয়েও এখনো সমাধান করার কথা ভাবতে পারিনা।

সৌমিকঃ যখন আমরা কোয়ান্টাম বলবিদ্যা (quantum mechanics) নিয়ে কথা বলি, তখন সাধারণত তাকে পদার্থবিদ্যার অংশ হিসেবে ধরা হয়। এই কোয়ান্টাম বলবিদ্যা এবং জটিলতার তত্ত্বের মধ্যে কোন সম্পর্ক আছে কি?

জনঃ হ্যাঁ, যখনি আমরা কোন একটি সমস্যা সমাধানের জটিলতা (complexity) নিয়ে কথা বলি, তখন আমাদের এটাও বলতে হয় যে কি কম্পিউটার দিয়ে আমরা সমস্যাটা সমাধান করছি। এই মেশিন একটি ক্লাসিক্যাল কম্পিউটার হতে পারে, কোয়ান্টাম কম্পিউটারও হতে পারে, অথবা আরও বিমূর্ত (abstract) কিছু হতে পারে।

রাজীবুলঃ   অথবা একটা সংকর (hybrid) – অর্থাৎ এদের মিলিয়ে মিশিয়ে  কিছু একটা হতে পারে।

জনঃ  হ্যাঁ, গোদা ভাষায় বললে জটিলতার তত্ত্বে  আমরা বিভিন্ন গণনামূলক (computational) সমস্যাগুলোর মধ্যে সম্পর্ক দেখি, কিন্তু সেটা দেখার আগে কোন কম্পিউটারে সমস্যাটা সমাধান করছি সেটাও দেখা হয়। কোনও বিশেষ একটা কম্পিউটার ধরে নিয়ে কোন্‌ কাজটা করা কতটা সহজ – এইটা দেখে কাজগুলোকে বিভিন্ন বিভাগে (category) ভাগ করি। তবে এই ভাগটা  একটু অন্যভাবেও করা যায়। সাধারণত এই বিভাগগুলো সময়ের ভিত্তিতে করা হয় – একটা নির্দিষ্ট কম্পিউটার একটা কাজ করতে কতটা সময় লাগাচ্ছে সেইটা আমরা দেখি। এক দিক থেকে ভাবলে কতটা সময় লাগছে সেটা সত্যিই সবচেয়ে গুরুত্বপূর্ণ। তবে মাঝে মাঝে কতটা মেমরি (memory) বা জায়গা লাগছে, সেটাও দেখা হয়। সময় আর মেমরি বেশ আলাদা – সময় একবার চলে গেলে আর ফিরে আসে না, কিন্তু একই মেমরিতে বারবার লেখা যায়।

জটিলতার আরও কিছু বিমূর্ত ধারনা আছে। মাঝে মাঝে আমরা সময় বা মেমরি না মেপে কোনও একটা নির্দিষ্ট বিমূর্ত জিনিস – যেমন একটা প্রোগ্রামের স্বয়ংসম্পূর্ণ একটা একক বা সাব-রুটিন (subroutine) – কতবার ব্যবহার করছি সেইটা মাপি। কখনও আবার কাজটা করতে কম্পিউটারের একটা দিক থেকে অন্য দিকে কতবার যোগাযোগ করতে হবে – সেইটা মাপি। 

রাজীবুলঃ  অর্থাৎ এখানে আপনি জটিলতা কীভাবে পরিমাপ করা যায়, তার কথা বলছেন, তাই তো?

জনঃ হ্যাঁ। এটাও বলছি কমপ্লেক্সিটি নিয়ে বিভিন্ন রকম ভাবে ভাবা যায়। কতটা সময় লাগছে সেটাই বেশি দেখা হয়, কিন্তু আরও অনেক রকমফের আছে।

রাজীবুলঃ  তাহলে তো আমরা এনার্জি (energy), অর্থাৎ কাজটা করতে কতটা শক্তি খরচ হল, সেটা নিয়েও ভাবতে পারি?

জনঃ হ্যাঁ, এনার্জি আসলে অনেক কোম্পানির কাছে খুবই গুরুত্বপূর্ণ। এতটাই গুরুত্বপূর্ণ যে অনেক কোম্পানি দেখে প্রতি একরে কতটা এনার্জি ব্যয় করে কোনও কাজের কতটুকু তারা করতে পারছে।

(হাসি)

জনঃ যেমন, কোনও একটি কোম্পানির অফিসে কত একর কম্পিউটার দরকার কোন একটা নির্দিষ্ট কাজ করার জন্য। আমরা সচরাচর এটা নিয়ে ভাবি না, কিন্তু কিছু কোম্পানির কাছে এটা বেশ গুরুত্বপূর্ণ।

(জটিল সমস্যা কীরকম হতে পারে এবং জটিলতার পরিমাপ কী, সেটা একটু বোঝা গেল। পরবর্তী অংশে জন তাঁর গবেষণার কথা বলবেন। জটিলতাকে কিছু শ্রেণীতে ভাগ করে কীভাবে সেই নিয়ে গবেষণা করা হয়, তার একটা আন্দাজ পাওয়া যাবে।)

প্রচ্ছদের ছবি: Sierra সুপারকম্পিউটার, IBM-এর তৈরী একটা দুর্দান্ত ক্ষমতাশালী কম্পিউটার, এখন লরেন্স লিভারমোর ন্যাশনাল ল্যাবরেটরি-তে রয়েছে। (ছবির সূত্র)

কৃতজ্ঞতা স্বীকার: ইন্টারভিউটা ট্রান্সক্রাইব করেছে “বিজ্ঞান” টিমের সৌমিক ঘোষ। ইংরেজি থেকে বাংলায় অনুবাদ করেছে “বিজ্ঞান” টিমের শৌর্য সেনগুপ্ত। অনুবাদে সাহায্য করেছে “বিজ্ঞান” টিমের অনির্বাণ গঙ্গোপাধ্যায় ও সৌমিক ঘোষ।

উৎসাহী পাঠকদের জন্য

1. থিসিস কমিটি-তে সময় ঠিক করে প্রফেসরদের একত্রিত করার সমস্যাটা শুনতে খুব একটা কঠিন কাজ মনে নাও হতে পারে। কিন্তু মনে রাখতে হবে থিসিস কমিটির বিভিন্ন প্রফেসরের বিভিন্ন চাহিদা থাকে – সবাই সব তারিখে খালি নন, খালি থাকলেও যে যতটা সময় ব্যয় করতে পারবেন, সেটা সমান নয়। ৫ জন হলে হয়তো অতটা সমস্যা হবে না, কিন্তু যত বেশিজন প্রফেসর, আর যত বেশি তাঁদের চাহিদার ফিরিস্তি, তত বিপদ। এই ধরণের কাজ নিয়ে পড়তে হলে উইকিপিডিয়ার এই পেজটা পড়ে দেখতে পারো।
2. থিসিস কমিটি-তে সময় ঠিক করে প্রফেসরদের একত্রিত করা, কিংবা শিক্ষার্থীদের সময়সূচি ঠিক করা, কিংবা ইলেকট্রনিক বোর্ড-এ চিপ-এর বিন্যাস ঠিক করা – সবকটাকেই এই কাজটার বিভিন্ন রূপ হিসেবে দেখা যায়। বিশেষ করে, উইকিপিডিয়া পেজটার ৫ নম্বর সেকশনটা পড়লে জন কি বলছেন তা কিছুটা আন্দাজ করতে পারবে।

লেখাটি অনলাইন পড়তে হলে নিচের কোডটি স্ক্যান করো।

Scan the above code to read the post online.

Link: https://bigyan.org.in/measurement-of-complexity

print