Finite promise games and greedy clique sequences
সীমাবদ্ধ প্রতিশ্রুতি গেমগুলি 2009 সালে আমেরিকান গণিতবিদ হার্ভি ফ্রিডম্যান দ্বারা বিকশিত গাণিতিক গেমগুলির একটি সংগ্রহ যা দ্রুত বর্ধনশীল ফাংশনগুলির একটি পরিবার বিকাশ করতে ব্যবহৃত হয়। লোভী চক্রের ক্রম একটি গ্রাফ তত্ত্বের ধারণা, যা 2010 সালে ফ্রিডম্যানও তৈরি করেছিলেন, যা দ্রুত বর্ধনশীল ফাংশনগুলি বিকাশ করতে ব্যবহৃত হয়। জেড. এফ. সি প্লাস তত্ত্বের প্রতিনিধিত্ব করে, প্রত্যেকটির জন্য, "একটি দৃঢ়ভাবে-মাহলো কার্ডিনাল রয়েছে", এবং জেড. এফ. সি প্লাস তত্ত্বের প্রতিনিধিত্ব করে "প্রত্যেকটির জন্য, একটি দৃঢ়ভাবে-মাহলো কার্ডিনাল রয়েছে"। জেডএফসি প্লাস তত্ত্বের প্রতিনিধিত্ব করে, প্রতিটির জন্য, "একটি-স্থির রামসে কার্ডিনাল রয়েছে", এবং জেডএফসি প্লাসের তত্ত্বের প্রতিনিধিত্ব করে "প্রতিটির জন্য, একটি দৃঢ়-স্থির রামসে কার্ডিনাল রয়েছে"। জেড. এফ. সি প্লাস তত্ত্বের প্রতিনিধিত্ব করে, প্রত্যেকটির জন্য, "একটি-বিশাল কার্ডিনাল রয়েছে", এবং জেড. এফ. সি প্লাস তত্ত্বের প্রতিনিধিত্ব করে "প্রত্যেকটির জন্য, একটি দৃঢ়-বিশাল কার্ডিনাল রয়েছে"। প্রতিটি খেলা সীমাবদ্ধ, দৈর্ঘ্যে পূর্বনির্ধারিত এবং এতে দুজন খেলোয়াড় (অ্যালিস এবং বব) রয়েছে। প্রতিটি মোড়ের সময়, অ্যালিস একটি পূর্ণসংখ্যা বা বেশ কয়েকটি পূর্ণসংখ্যা (একটি প্রস্তাব) বেছে নেয় এবং ববকে তার ভবিষ্যতের সম্ভাব্য পদক্ষেপগুলিকে সীমাবদ্ধ করার জন্য দুই ধরনের প্রতিশ্রুতির মধ্যে একটি করতে হয়। সমস্ত খেলায় বব তখনই জয়ী হয় যখন বব তার সমস্ত প্রতিশ্রুতি রক্ষা করে। ফাইনাইট পিসওয়াইজ লিনিয়ার কপি/ইনভার্ট গেম এখানে, পূর্ণসংখ্যার সেট, এবং অ-নেতিবাচক পূর্ণসংখ্যার সেট। এখানে, সমস্ত অক্ষর পূর্ণসংখ্যার প্রতিনিধিত্ব করে। আমরা বলি যে একটি মানচিত্র টুকরো টুকরো রৈখিক হয় যদি সীমাবদ্ধভাবে অনেকগুলি টুকরোর প্রত্যেকটিতে পূর্ণসংখ্যা সহগের সাথে বিভিন্ন অ্যাফিন ফাংশন দ্বারা সংজ্ঞায়িত করা যায়, যেখানে প্রতিটি টুকরো পূর্ণসংখ্যা সহগের সাথে রৈখিক বৈষম্যের একটি সীমাবদ্ধ সেট দ্বারা সংজ্ঞায়িত করা হয়। কিছু পিসওয়াইজ রৈখিক মানচিত্রের জন্য, এর একটি-ইনভার্সন এমন কিছু। আমরা তখন ননজিরোর জন্য খেলাটিকে সংজ্ঞায়িত করি। রাউন্ড আছে, এবং অ্যালিস এবং ববের মধ্যে পরিবর্তিত হয়। খেলার প্রতিটি পর্যায়ে, অ্যালিসকে খেলতে হয়, যাকে তার অফার বলা হয়, যা হয় ফর্মের বা, যেখানে এবং পূর্ণসংখ্যা যা পূর্বে বব খেলেছিলেন। ববের তখন প্রয়োজন হয়ঃ গ্রহণ করুন, যার ফলে খেলুন এবং প্রতিশ্রুতি দিন যে ববের দ্বারা অভিনীত পূর্ণসংখ্যার মধ্যে কোনও-বিপরীত হবে না। এই প্রতিশ্রুতি খেলার অতীত, বর্তমান এবং ভবিষ্যতের সমস্ত খেলার ক্ষেত্রে প্রযোজ্য। প্রত্যাখ্যান করুন, যার ফলে এমন একটি বিপরীতমুখী এবং প্রতিশ্রুতিবদ্ধ খেলা খেলুন যা বব কখনও খেলেনি। আরসিএ0-তে, এটা প্রমাণ করা যেতে পারে যে যে কোনও খেলার জন্য ববের সর্বদা একটি বিজয়ী কৌশল থাকে। গেমটি একটি পরিবর্তিত সংস্করণ যেখানে বব অ্যালিসের সমস্ত ফ্যাক্টোরিয়াল অফার গ্রহণ করতে বাধ্য হয়। যথেষ্ট বড়ের জন্য ববের সর্বদা একটি বিজয়ী কৌশল থাকে, যদিও এটি কোনও নির্দিষ্ট ধারাবাহিক অংশে এবং শুধুমাত্র প্রমাণিত হতে পারে না। ফাংশনটি এমন ক্ষুদ্রতম যে বব এমন যে কোনও কিছুর জন্য জিততে পারে এবং এর চেয়ে বড় বা সমান এবং নিম্নলিখিত সমস্ত মানগুলি এর চেয়ে কমঃ (এর ক্ষেত্রটি হল) সীমাবদ্ধ বহুপদী অনুলিপি/বিপরীত গেমগুলিতে অ্যাফিন ফাংশনের সহগের পরম মানগুলির অসমতার সহগের পরম মানগুলির টুকরোগুলির সংখ্যা ধরা যাক পূর্ণসংখ্যা সহ একটি বহুপদী। একটি বিশেষ-ইনভার্সন এই ধরনের নিয়ে গঠিত। আমরা এখন অ-শূন্যের জন্য খেলাটি সংজ্ঞায়িত করি, যেখানে পূর্ণসংখ্যা সহগ সহ বহুপদ রয়েছে। এটি অ্যালিস এবং ববের পর্যায়ক্রমিক নাটক নিয়ে গঠিত। খেলার প্রতিটি পর্যায়ে, অ্যালিসকে ফর্মটি খেলতে হয়, বা, যেখানে পূর্বে বব দ্বারা খেলা পূর্ণসংখ্যার একটি-টুপল রয়েছে। ববের তখন প্রয়োজন হয়ঃ গ্রহণ করুন, যার ফলে খেলুন এবং প্রতিশ্রুতি দিন যে ববের দ্বারা অভিনীত পূর্ণসংখ্যাগুলির মধ্যে কোনও বিশেষ-বা-বিপরীত হবে না। এই প্রতিশ্রুতি খেলার অতীত, বর্তমান এবং ভবিষ্যতের সমস্ত খেলার ক্ষেত্রে প্রযোজ্য। প্রত্যাখ্যান করুন, যার ফলে একটি বিশেষ-বা-বিপরীত এবং প্রতিশ্রুতিবদ্ধ খেলা যা বব কখনও খেলেনি। ধরা যাক পূর্ণসংখ্যা সহগ সহ বহুপদী। আরসিএ0-তে, এটা প্রমাণ করা যেতে পারে যে যে কোনও খেলার জন্য ববের সর্বদা একটি বিজয়ী কৌশল থাকে। যদি যথেষ্ট বড় হয় তবে বব জিতে যায়, যেখানে বব অ্যালিসের দেওয়া সমস্ত ডাবল ফ্যাক্টোরিয়াল গ্রহণ করতে বাধ্য হয়। যাইহোক, আরও একবার, এটি কোনও নির্দিষ্ট সামঞ্জস্যপূর্ণ অংশে এবং শুধুমাত্র প্রমাণিত হতে পারে না। ফাংশনটি এমন ক্ষুদ্রতম যে বব এমন যে কোনও কিছুর জন্য জিততে পারে যা বড় বা সমান এবং নিম্নলিখিত সমস্ত মানগুলি এর চেয়ে কমঃ (পলিনোমিয়ালগুলির ডোমেন হল) সহগের ডিগ্রি এবং পরম মান এবং ফাইনাইট লিনিয়ার কপি/ইনভার্ট গেম আমরা বলি যে যোগাত্মকভাবে সমতুল্য যদি এবং শুধুমাত্র যদি। অ-শূন্য পূর্ণসংখ্যার জন্য এবং, আমরা গেমটিকে সংজ্ঞায়িত করি যা অ্যালিস এবং ববের মধ্যে পর্যায়ক্রমে রাউন্ড নিয়ে গঠিত। খেলার প্রতিটি পর্যায়ে, অ্যালিসকে ফর্মের একটি পূর্ণসংখ্যা খেলতে হয়, যেখানে পূর্বে বব পূর্ণসংখ্যাটি খেলেছেন। ববের তখন প্রয়োজন হয়ঃ গ্রহণ করুন, যার ফলে খেলা এবং প্রতিশ্রুতি দেওয়া হয় যা হিসাবে লেখা যায় না, যেখানে যোগাত্মকভাবে কিছু সমতুল্য, এবং বিভিন্ন সময়ে বব দ্বারা বাজানো পূর্ণসংখ্যা। প্রত্যাখ্যান করুন, এর ফলে খেলুন, যেখানে এবং যোগাত্মকভাবে কিছু সমতুল্য, এবং এমন প্রতিশ্রুতি যা বব কখনও খেলেন না। যাক। আরসিএ0-তে, এটা প্রমাণ করা যেতে পারে যে যে কোনও খেলার জন্য ববের সর্বদা একটি বিজয়ী কৌশল থাকে। যাক। যদি যথেষ্ট বড় হয়, তাহলে বব জিতবে, যেখানে বব অ্যালিসের দেওয়া সমস্ত ফ্যাক্টোরিয়াল গ্রহণ করবে। যাইহোক, আরও একবার, এটি কোনও নির্দিষ্ট সামঞ্জস্যপূর্ণ অংশে এবং শুধুমাত্র প্রমাণিত হতে পারে না। ফাংশনটি এমন ক্ষুদ্রতম যে বব যে কোনও কিছুর জন্য জিততে পারে যা এর চেয়ে বড় বা সমান, ধনাত্মক এবং নিম্নলিখিত সমস্ত মান এর চেয়ে কমঃ ফাংশনগুলিতে প্রতিটি ভেক্টরের উপাদানের সংখ্যা যেমন ফ্রিডম্যান দেখিয়েছেন, তিনটি ফাংশন, এবং অত্যন্ত দ্রুত বর্ধনশীল, শেষ পর্যন্ত যে কোনও ফাংশনে আধিপত্য বিস্তার করে যে কোনও সামঞ্জস্যপূর্ণ অংশে পুনরাবৃত্তিমূলক (এগুলির মধ্যে একটি হল জেডএফসি), তবে সেগুলি গণনাযোগ্য এবং মোট হিসাবে প্রমাণিত। লোভী চক্রের ক্রমগুলি যুক্তিসঙ্গত সংখ্যার সমস্ত টুপলের সেটকে বোঝায়। আমরা সাবস্ক্রিপ্ট ব্যবহার করে সূচীগুলিকে টুপল (1 থেকে শুরু করে) এবং কোণ বন্ধনীতে টুপলগুলির সংহতকরণ বোঝাতে, যেমন। । প্রদত্ত, আমরা এর উপরের স্থানান্তরকে সংজ্ঞায়িত করি, যা তার সমস্ত অ-নেতিবাচক উপাদানগুলিতে 1 যোগ করার ফলাফল হিসাবে চিহ্নিত করা হয়। প্রদত্ত, আমরা এটি এবং বলি। তাদের অর্ডার সমতুল্য বলা হয় যদি এবং শুধুমাত্র যদি তাদের একই দৈর্ঘ্য থাকে এবং সকলের জন্য, আই. এফ. এফ। একটি সেট হল সমস্ত অর্ডার সমতুল্য এবং,-এর জন্য অর্ডার অপরিবর্তনীয় আই. এফ. এফ। ধরা যাক একটি গ্রাফ যার মধ্যে শীর্ষস্থান রয়েছে। সেটটি নিম্নরূপ সংজ্ঞায়িত করা যাকঃ প্রতিটি প্রান্তের জন্য, তাদের সংহতকরণ হয়। তারপর যদি ক্রম অপরিবর্তনীয় হয়, আমরা বলি যে এটি ক্রম অপরিবর্তনীয়। যখন ক্রম অপরিবর্তনীয়, তার অসীম প্রান্ত থাকে। আমাদের দেওয়া হয়েছে, এবং একটি সহজ গ্রাফ (বা উপরের শিফট লোভী ডাউন ক্লাইক সিকোয়েন্সের ক্ষেত্রে একটি ডিগ্রাফ) যার মধ্যে শীর্ষগুলি রয়েছে। আমরা একটি ক্রমকে একটি নন-এম্প্টি টুপল হিসাবে সংজ্ঞায়িত করি। এটি কোনও টুপল নয়, বরং টুপলগুলির একটি টুপল। যখন, একটি উচ্চ স্থানান্তর লোভী চক্র ক্রম বলা হয় যদি এটি নিম্নলিখিতগুলিকে সন্তুষ্ট করেঃ শুধুমাত্র শূন্য নিয়ে গঠিত। ধরা যাক একটি পূর্ণসংখ্যা যেমন, বা একটি ধনাত্মক পূর্ণসংখ্যা যদি আমরা অসীম ক্রমের অনুমতি দিই। এবং যেতে দিন। তারপর, এবং এর একটি প্রান্ত নয়। একটি চক্র, অর্থাৎ। প্রতিটি জোড়া শীর্ষে একটি প্রান্ত হিসাবে থাকে। যখন, লোভী চক্রের ক্রমের একটি উপরের স্থানান্তর বলা হয় যদি এটি নিম্নলিখিতগুলিকে সন্তুষ্ট করেঃ শুধুমাত্র শূন্য নিয়ে গঠিত। ধরা যাক একটি পূর্ণসংখ্যা যেমন, বা একটি ধনাত্মক পূর্ণসংখ্যা যদি আমরা অসীম ক্রমের অনুমতি দিই। এবং যেতে দিন। তারপর, বা এবং এর একটি প্রান্ত নয়; এবং। একটি ডাউন ক্লিক, অর্থাৎ। সকলের জন্য এবং, এর একটি প্রান্ত। যখন, লোভী চক্রের ক্রমের নীচে একটি চরম উপরের স্থানান্তর বলা হয় যদি এটি নিম্নলিখিতগুলিকে সন্তুষ্ট করেঃ শুধুমাত্র শূন্য নিয়ে গঠিত। ধরা যাক একটি পূর্ণসংখ্যা যেমন, বা একটি ধনাত্মক পূর্ণসংখ্যা যদি আমরা অসীম ক্রমের অনুমতি দিই। এবং যেতে দিন। তারপর, বা এবং এর একটি প্রান্ত নয়; এবং। যদি হয়, তাহলে। যদি হয়, তাহলে। যদি এবং, তাহলে একটি ডাউন ক্লিক হয় এর থ্রেডটি একটি ধারাবাহিকভাবে সংজ্ঞায়িত করা হয় যেমনঃ একটি থ্রেড দেওয়া হলে, আমরা বলি যে যদি খোলা থাকে। এই ব্যবহার করে হার্ভি ফ্রিডম্যান তিনটি অত্যন্ত শক্তিশালী ফাংশনকে সংজ্ঞায়িত করেছেনঃ এটি এমন ক্ষুদ্রতম যে প্রতিটি সহজ, ক্রমের অপরিবর্তনীয় গ্রাফের একটি খোলা সুতো সহ দৈর্ঘ্যের উপরের শিফট লোভী চক্রের ক্রম থাকে। এটি সবচেয়ে ছোট যে প্রতিটি ক্রমের অপরিবর্তনীয় ডিগ্রাফের একটি উপরের শিফট লোভী ডাউন ক্লাইক সিকোয়েন্স থাকে যার দৈর্ঘ্য সর্বাধিক একটি খোলা সুতা সহ। এটি সবচেয়ে ছোট যে প্রতিটি ক্রম অপরিবর্তনীয় ডিগ্রাফ একটি খোলা থ্রেড সহ দৈর্ঘ্যের সর্বাধিক উপরের শিফট লোভী ডাউন ক্লাইক সিকোয়েন্স রয়েছে। এবং অবশেষে প্রমাণিতভাবে পুনরাবৃত্তিমূলক সমস্ত ফাংশনে আধিপত্য বিস্তার করে, তবে তারা নিজেরাই প্রমাণিতভাবে পুনরাবৃত্তিমূলক। অবশেষে প্রমাণিতভাবে পুনরাবৃত্তিমূলক সমস্ত ফাংশনে আধিপত্য বিস্তার করে, তবে এটি নিজেই প্রমাণযোগ্যভাবে মোট। তথ্যসূত্র গাণিতিক খেলা গাণিতিক ধারণাগুলি