আভি উইগডারসন, কমপ্লেসিটি থিওরি পাইওনিয়ার, টুরিং অ্যাওয়ার্ড জিতেছে | কোয়ান্টা ম্যাগাজিন

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

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

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

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

তিনি এমন একটি ক্ষেত্র খুঁজে পেয়েছিলেন যার মধ্যে গভীর, অনুত্তরিত প্রশ্ন ছিল যা হৃদয়ে গাণিতিক ছিল। তার প্রথম দিকের যুগান্তকারী প্রচেষ্টাগুলির মধ্যে একটি আপাতদৃষ্টিতে দ্বন্দ্বের উপর দৃষ্টি নিবদ্ধ করেছিল: এটি অন্য কাউকে বোঝানো সম্ভব ছিল কিনা যে একটি গাণিতিক বিবৃতি কীভাবে না দেখিয়ে প্রমাণিত হয়েছে।

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

“এটি ক্রিপ্টোগ্রাফির একটি মূল ফলাফল; এটা অত্যন্ত কেন্দ্রীয়,” রাজ বলেছেন। একটি শূন্য-জ্ঞান প্রমাণ ব্যবহার করে, কেউ প্রমাণ করতে পারে যে তারা সঠিকভাবে এনক্রিপ্ট করেছে বা তাদের গোপন কী ব্যবহার করে একটি বার্তা স্বাক্ষর করেছে, এটি সম্পর্কে কোনো তথ্য প্রকাশ না করে। "ক্রিপ্টোগ্রাফিতে আভির কিছু অত্যন্ত গুরুত্বপূর্ণ ফলাফল রয়েছে এবং এটি তাদের মধ্যে সবচেয়ে গুরুত্বপূর্ণ হতে পারে।"

তবে সম্ভবত উইগডারসনের সবচেয়ে মৌলিক ফলাফল অন্য একটি ক্ষেত্রে নিহিত: গণনাগত কঠোরতাকে সংযুক্ত করা যদৃচ্ছতা. 1970 এর দশকের শেষের দিকে, কম্পিউটার বিজ্ঞানীরা বুঝতে পেরেছিলেন যে অনেক কঠিন সমস্যার জন্য, অ্যালগরিদমগুলি যেগুলি এলোমেলোতাকে নিযুক্ত করে, যাকে সম্ভাব্য অ্যালগরিদমও বলা হয়, তারা তাদের নির্ধারক বিকল্পগুলিকে ব্যাপকভাবে প্রতিদ্বন্দ্বিতা করতে পারে। ক 1977 প্রমাণ, উদাহরণস্বরূপ, রবার্ট সলোভে এবং ভলকার স্ট্রাসেন একটি এলোমেলো অ্যালগরিদম প্রবর্তন করেছিলেন যা নির্ধারণ করতে পারে যে একটি সংখ্যা সেই সময়ের সেরা নির্ধারক অ্যালগরিদমের চেয়ে দ্রুততম কিনা।

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

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

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

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

সুদান বলেছে যে কাগজটি কম্পিউটার বিজ্ঞানীদের এলোমেলোতার ডিগ্রী সনাক্ত করতে সাহায্য করেছে যা কঠিন সমস্যার জটিলতা এবং কীভাবে সেগুলি সমাধান করতে পারে তা প্রকাশ করতে সহায়তা করতে পারে। "এটি শুধু এলোমেলোতা নয় বরং এলোমেলোতার উপলব্ধি," তিনি বলেছিলেন। "এটাই চাবিকাঠি।"

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

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

কিন্তু উইগারসনের জন্য, কম্পিউটিং-এর উদাহরণ সর্বত্র রয়েছে — শুধু স্মার্টফোন এবং ল্যাপটপ এবং এনক্রিপশন অ্যালগরিদমের মধ্যে নয়, জৈবিক এবং শারীরিক সিস্টেমেও। সাম্প্রতিক দশকগুলিতে, গণনার তত্ত্ব থেকে প্রাপ্ত ফলাফলগুলি অপ্রত্যাশিত সমস্যাগুলির একটি পরিসরের অন্তর্দৃষ্টি প্রদান করেছে, ঝাঁকে ঝাঁকে পাখি এবং নির্বাচনের ফলাফল থেকে শুরু করে দেহে জৈব রাসায়নিক প্রতিক্রিয়া পর্যন্ত৷ "মূলত, যেকোনো প্রাকৃতিক প্রক্রিয়া হল একটি বিবর্তন যা আপনি গণনা হিসাবে দেখতে পারেন, তাই আপনি এটিকে অধ্যয়ন করতে পারেন। প্রায় সবকিছুই গণনা করে।"