মধ্য দূরত্বের জন্য গাণিতিক কৌশল | কোয়ান্টা ম্যাগাজিন

এ বছর এ পর্যন্ত, কোয়ান্টা রামসে তত্ত্বের তিনটি বড় অগ্রগতি ক্রনিক করেছে, কিভাবে গাণিতিক নিদর্শন তৈরি করা এড়াতে হয় তার অধ্যয়ন। দ্য প্রথম ফলাফল পূর্ণসংখ্যার একটি সেট কত বড় হতে পারে তার উপর একটি নতুন ক্যাপ রাখুন যাতে তিনটি সমান ব্যবধানের সংখ্যা না থাকে, যেমন {2, 4, 6} বা {21, 31, 41}। দ্য দ্বিতীয় এবং তৃতীয় একইভাবে নেটওয়ার্কের আকারে বিন্দুর ক্লাস্টার ছাড়াই নতুন সীমানা স্থাপন করুন যা হয় সমস্ত সংযুক্ত, বা সমস্ত একে অপরের থেকে বিচ্ছিন্ন।

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

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

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

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

যদিও কেলি এবং মেকার ফলাফল প্রযোজ্য হলেও N তুলনামূলকভাবে ছোট, এটি সেই ক্ষেত্রে বিশেষভাবে দরকারী আবদ্ধ দেয় না। খুব ছোট মান জন্য N, আপনি খুব সহজ পদ্ধতিতে লেগে থাকা ভাল। যদি N হল, বলুন, 5, শুধু 1 এবং এর মধ্যে সমস্ত সম্ভাব্য সংখ্যার সেটগুলি দেখুন N, এবং সবচেয়ে বড় অগ্রগতি-মুক্ত একটি বেছে নিন: {1, 2, 4, 5}।

কিন্তু বিভিন্ন সম্ভাব্য উত্তরের সংখ্যা খুব দ্রুত বৃদ্ধি পায় এবং এই ধরনের একটি সহজ কৌশল নিয়োগ করা খুব কঠিন করে তোলে। 1 থেকে 1 এর মধ্যে সংখ্যা নিয়ে গঠিত 20 মিলিয়নেরও বেশি সেট রয়েছে।⁶⁰ 1 এবং 200 এর মধ্যে সংখ্যা ব্যবহার করে। এই ক্ষেত্রেগুলির জন্য সেরা অগ্রগতি-মুক্ত সেট খুঁজে পেতে কম্পিউটিং শক্তির একটি বিশাল ডোজ লাগে, এমনকি দক্ষতা-উন্নতির কৌশলগুলির সাথেও। "আপনাকে জিনিসগুলি থেকে অনেকগুলি পারফরম্যান্স চেপে নিতে সক্ষম হতে হবে," বলেছেন জেমস গ্লেন, ইয়েল বিশ্ববিদ্যালয়ের একজন কম্পিউটার বিজ্ঞানী। 2008 সালে, Gasarch, Glenn এবং ক্লাইড ক্রুস্কাল মেরিল্যান্ড বিশ্ববিদ্যালয়ের একটি প্রোগ্রাম লিখেছেন একটি পর্যন্ত সবচেয়ে বড় অগ্রগতি-মুক্ত সেট খুঁজে পেতে N 187 এর। (আগের কাজটি 150টি পর্যন্ত উত্তর পেয়েছিল, সেইসাথে 157টির জন্য।) কৌশলের একটি তালিকা থাকা সত্ত্বেও, তাদের প্রোগ্রামটি শেষ হতে কয়েক মাস লেগেছিল, গ্লেন বলেছিলেন।

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

Gasarch, Glenn এবং Kruskal এছাড়াও আরো বেশ কিছু কৌশলের চেষ্টা করেছিলেন। একটি প্রতিশ্রুতিশীল ধারণা এলোমেলোতার দিকে ঝুঁকেছে। একটি অগ্রগতি-মুক্ত সেট নিয়ে আসার একটি সহজ উপায় হল আপনার সেটে 1 রাখা, তারপর সর্বদা পরবর্তী সংখ্যা যোগ করুন যা একটি গাণিতিক অগ্রগতি তৈরি করে না। আপনি 10 নম্বরে না আসা পর্যন্ত এই পদ্ধতিটি অনুসরণ করুন এবং আপনি সেটটি {1, 2, 4, 5, 10} পাবেন৷ কিন্তু দেখা যাচ্ছে এটি সাধারণভাবে সেরা কৌশল নয়। "যদি আমরা 1 এ শুরু না করি?" গাসারচ ড. "আপনি যদি এলোমেলো জায়গায় শুরু করেন তবে আপনি আসলে আরও ভাল করবেন।" গবেষকদের কোন ধারণা নেই কেন এলোমেলোতা এত দরকারী, তিনি যোগ করেছেন।

অন্য দুটি নতুন রামসে তত্ত্বের ফলাফলের সসীম সংস্করণ গণনা করা প্রগতি-মুক্ত সেটের আকার নির্ধারণের চেয়ে আরও বেশি বিরক্তিকর। এই ফলাফলগুলি প্রান্ত নামক লাইন দ্বারা সংযুক্ত নোডগুলি দ্বারা গঠিত গাণিতিক নেটওয়ার্কগুলির (যাকে গ্রাফ বলা হয়) সম্পর্কিত। রামসে নম্বর r(s, t) হল ক্ষুদ্রতম সংখ্যক নোড যা একটি গ্রাফ থাকা আবশ্যক আগে এটিকে এড়ানো অসম্ভব s সংযুক্ত নোড বা t সংযোগ বিচ্ছিন্ন। Ramsey সংখ্যা যে এমনকি গণনা যেমন একটি মাথাব্যথা r(5, 5) অজানা - এটি 43 এবং 48 এর মধ্যে কোথাও।

1981 সালে ব্রেন্ডন ম্যাককে, এখন অস্ট্রেলিয়ান ন্যাশনাল ইউনিভার্সিটির একজন কম্পিউটার বিজ্ঞানী, nauty নামে একটি সফ্টওয়্যার প্রোগ্রাম লিখেছেন, যার উদ্দেশ্য ছিল রামসে সংখ্যা গণনা করা সহজতর করা। Nauty নিশ্চিত করে যে গবেষকরা দুটি গ্রাফ পরীক্ষা করার সময় নষ্ট করবেন না যেগুলি একে অপরের শুধু উল্টানো বা ঘোরানো সংস্করণ। “যদি কেউ এলাকায় থাকে এবং দুষ্টু ব্যবহার না করে, খেলা শেষ। আপনি এটা ব্যবহার করতে হবে,” বলেন স্ট্যানিস্লো রাডজিসজভস্কি, রচেস্টার ইনস্টিটিউট অফ টেকনোলজির একজন গণিতবিদ। তবুও, জড়িত গণনার পরিমাণ প্রায় বোধগম্য নয়। 2013 সালে, Radziszowski এবং জ্যান গোয়েজেবেউর প্রমাণ করেছে যে r(3, 10) সর্বাধিক 42. বেলজিয়ামের কে ইউ লিউভেন ইউনিভার্সিটির কম্পিউটার বিজ্ঞানী গোয়েজেবেউর বলেন, "আমার মনে হয়, প্রায় ৫০ সিপিইউ বছর লেগেছে।"

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

এলোমেলোতা বোঝার জন্য একটি বাধা এবং একটি দরকারী টুল। জিওফ্রে এক্সু, ইন্ডিয়ানা স্টেট ইউনিভার্সিটির একজন কম্পিউটার বিজ্ঞানী, রামসে গ্রাফ তৈরি করার জন্য এলোমেলো পদ্ধতিগুলিকে পরিমার্জন করতে কয়েক বছর ব্যয় করেছেন। ভিতরে একটি 2015 কাগজ কয়েক ডজন নতুন, রেকর্ড-বীটিং রামসে গ্রাফ ঘোষণা করে, Exoo এবং Milos Tatarevic এলোমেলো গ্রাফ তৈরি করেছে এবং তারপর ধীরে ধীরে মুছে ফেলা বা প্রান্ত যোগ করে তাদের টুইক করেছে যা রামসে গ্রাফ না পাওয়া পর্যন্ত অবাঞ্ছিত ক্লাস্টারের সংখ্যা কমিয়ে দিয়েছে। রেডজিসজোস্কি বলেন, এক্সওর কৌশলগুলি যে কোনও কিছুর মতোই একটি শিল্প। তারা কখনও কখনও তাকে একাধিক পদ্ধতি একত্রিত করতে বা কোন ধরণের গ্রাফ দিয়ে শুরু করতে হবে সে সম্পর্কে রায় ব্যবহার করতে চায়। "অনেক, অনেক লোক এটি চেষ্টা করে, এবং তারা এটি করতে পারে না," রাডজিসজোস্কি বলেছিলেন।

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

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