Generalized geography
গণনামূলক জটিলতা তত্ত্বে, সাধারণীকৃত ভূগোল একটি সুপরিচিত পি. এস. পি. এ. সি. ই-সম্পূর্ণ সমস্যা। ভূমিকা ভূগোল একটি শিশুদের খেলা, যেখানে খেলোয়াড়রা পালাক্রমে বিশ্বের যে কোনও জায়গা থেকে শহরগুলির নামকরণ করে। নির্বাচিত প্রতিটি শহরকে অবশ্যই একই অক্ষর দিয়ে শুরু করতে হবে যা পূর্ববর্তী শহরের নাম শেষ করে। পুনরাবৃত্তি অনুমোদিত নয়। খেলাটি একটি নির্বিচারে শুরুর শহর দিয়ে শুরু হয় এবং শেষ হয় যখন কোনও খেলোয়াড় হেরে যায় কারণ সে চালিয়ে যেতে পারে না। গ্রাফ মডেল গেমটি কল্পনা করার জন্য, একটি নির্দেশিত গ্রাফ তৈরি করা যেতে পারে যার নোডগুলি বিশ্বের প্রতিটি শহর। নোড এন1 থেকে নোড এন2-এ একটি তীর যুক্ত করা হয় যদি এবং শুধুমাত্র যদি শহরের লেবেলিং এন2 অক্ষর দিয়ে শুরু হয় যা শহরের লেবেলিং নোড এন1-এর নাম শেষ করে। অন্য কথায়, আমরা এক শহর থেকে অন্য শহরে একটি তীর টানতে পারি যদি খেলার নিয়ম অনুযায়ী প্রথমটি দ্বিতীয়টির দিকে নিয়ে যেতে পারে। নির্দেশিত গ্রাফের প্রতিটি বিকল্প প্রান্ত প্রতিটি খেলোয়াড়ের সাথে মিলে যায় (দুই খেলোয়াড়ের খেলার জন্য)। যে প্রথম খেলোয়াড় পথ প্রসারিত করতে অক্ষম হয় সে হেরে যায়। খেলার একটি চিত্র (মিশিগানের কয়েকটি শহর সহ) নীচের চিত্রে দেখানো হয়েছে। একটি সাধারণীকৃত ভূগোল (জিজি) খেলায়, আমরা একটি নির্বিচারে নির্দেশিত গ্রাফ দিয়ে শহরের নামের গ্রাফ প্রতিস্থাপন করি। নিম্নলিখিত গ্রাফটি একটি সাধারণীকৃত ভূগোল খেলার একটি উদাহরণ। খেলাটি খেলে আমরা পি1-কে প্রথমে চলা খেলোয়াড় এবং পি2-কে দ্বিতীয় দিকে চলা খেলোয়াড় হিসাবে সংজ্ঞায়িত করি এবং নোডগুলির নাম এন1 থেকে এনএন রাখি। উপরের চিত্রে, পি1-এর একটি বিজয়ী কৌশল রয়েছে যা নিম্নরূপঃ এন1 শুধুমাত্র নোড এন2 এবং এন3-এর দিকে নির্দেশ করে। সুতরাং পি1-এর প্রথম পদক্ষেপটি অবশ্যই এই দুটি বিকল্পের মধ্যে একটি হতে হবে। পি1 এন2 বেছে নেয় (যদি পি1 এন3 বেছে নেয়, তাহলে পি2 এন9 বেছে নেবে কারণ এটিই একমাত্র বিকল্প এবং পি1 হারবে)। পরবর্তী পি2 এন4 বেছে নেয় কারণ এটিই একমাত্র অবশিষ্ট পছন্দ। পি1 এখন এন5 বেছে নেয় এবং পি2 পরবর্তীকালে এন3 বা এন7 বেছে নেয়। পি2-এর পছন্দ যাই হোক না কেন, পি1 এন9 বেছে নেয় এবং পি2-এর কোনও অবশিষ্ট পছন্দ নেই এবং খেলাটি হেরে যায়। গণনামূলক জটিলতা একটি সাধারণ ভূগোলের খেলায় কোন খেলোয়াড়ের জয়ের কৌশল রয়েছে তা নির্ধারণের সমস্যাটি পি. এস. পি. এ. সি. ই-সম্পূর্ণ। সাধারণ ভূগোলটি পি. এস. পি. এ. সি. ই-তে রয়েছে ধরা যাক জি. জি = {75জি, বি. পি. এল. এ। পি1-এর একটি বিজয়ী কৌশল রয়েছে গ্রাফ জি-তে খেলা সাধারণ ভূগোল খেলার জন্য যা নোড বি থেকে শুরু হয়; এটি দেখানোর জন্য যে জি. জি. পি. এস. পি. এ. সি, আমরা একটি বহুপদী-স্থান পুনরাবৃত্তিমূলক অ্যালগরিদম উপস্থাপন করি যা নির্ধারণ করে যে কোন খেলোয়াড়ের একটি বিজয়ী কৌশল রয়েছে। জিজি, 75জি, এনস্টার্টওলোর একটি উদাহরণ দেওয়া হয়েছে যেখানে জি একটি নির্দেশিত গ্রাফ এবং এনস্টার্ট মনোনীত স্টার্ট নোড, অ্যালগরিদম এম নিম্নরূপ এগিয়ে যায়ঃ এম-এ (75জি, এনস্টার্টওল): নোড এনস্টার্টের আউট-ডিগ্রি পরিমাপ করুন। যদি এই ডিগ্রিটি 0 হয়, তবে ফিরে আসুন, কারণ প্রথম খেলোয়াড়ের জন্য কোনও পদক্ষেপ উপলব্ধ নেই। এনস্টার্ট থেকে এক প্রান্ত দিয়ে পৌঁছানো যায় এমন সমস্ত নোডের একটি তালিকা তৈরি করুনঃ এন1, এন2,., এনআই। জি1 গঠন করতে জি থেকে এনস্টার্ট এবং এর সাথে সংযুক্ত সমস্ত প্রান্ত সরিয়ে ফেলুন। n1,., ni তালিকার প্রতিটি নোড nj-এর জন্য, M-কে কল করুন। যদি এই সমস্ত কলগুলি প্রত্যাবর্তন গ্রহণ করে, তবে পি1 যে সিদ্ধান্তই নিক না কেন, পি2-এর জেতার কৌশল রয়েছে, তাই প্রত্যাবর্তন প্রত্যাখ্যান করুন। অন্যথায় (যদি কলগুলির মধ্যে একটি প্রত্যাখ্যান করে) পি1-এর একটি বিকল্প রয়েছে যা পি2-এর জন্য কোনও সফল কৌশলকে অস্বীকার করবে, তাই প্রত্যাবর্তন গ্রহণ করুন। অ্যালগরিদম এম স্পষ্টভাবে জিজি নির্ধারণ করে। এটি পি. এস. পি. এ. সি. ই-তে রয়েছে কারণ একমাত্র অ-স্পষ্ট বহুপদী কর্মক্ষেত্রটি রিকার্সন স্ট্যাকে ব্যবহৃত হয়। পুনরাবৃত্তি স্ট্যাক দ্বারা ব্যবহৃত স্থানটি বহুপদী কারণ পুনরাবৃত্তির প্রতিটি স্তর স্ট্যাকে একটি একক নোড যোগ করে এবং সর্বাধিক n স্তরে রয়েছে, যেখানে n হল G-তে নোডের সংখ্যা। এটি মূলত একটি গভীরতা-প্রথম অনুসন্ধানের সমতুল্য। সাধারণ ভূগোল হল স্পেস-হার্ড নিম্নলিখিত প্রমাণ ডেভিড লিকটেনস্টাইন এবং মাইকেল সিপসারের কারণে। জিজির পি. এস. পি. এ. সি. ই-কঠোরতা প্রতিষ্ঠার জন্য, আমরা বহুপদী সময়ে (পি) ফর্মুলা-গেম সমস্যা (যা পি. এস. পি. ই-হার্ড হিসাবে পরিচিত) কে জি. জি-তে হ্রাস করতে পারি। সংক্ষেপে, ফর্মুলা-গেম সমস্যার একটি উদাহরণ একটি পরিমাপকৃত বুলিয়ান সূত্র নিয়ে গঠিত φ = HEx1 βx2 HEx3. Qxk (si) যেখানে Q হয় HE বা β। এই খেলাটি দুইজন খেলোয়াড়, পা এবং পে দ্বারা খেলা হয়, যারা পর্যায়ক্রমে xi-এর জন্য বিকল্প মান বেছে নেয়। পে খেলায় জয়ী হয় যদি সূত্রটি সত্য হয়, এবং পা জয়ী হয় যদি সূত্রটি মিথ্যা হয়। সূত্রটি কনজাংক্টিভ নরমাল আকারে রয়েছে বলে ধরে নেওয়া হয়। এই প্রমাণটিতে, আমরা ধরে নিই যে সরলতার জন্য কোয়ান্টিফায়ার তালিকাটি অস্তিত্বগত যোগ্যতা, এইচ. ই দিয়ে শুরু এবং শেষ হয়। মনে রাখবেন যে কোনও অভিব্যক্তি এই রূপে রূপান্তরিত করা যেতে পারে ডামি ভেরিয়েবল যোগ করে যা si-তে উপস্থিত হয় না। উপরে দেখানো গ্রাফের মতো একটি গ্রাফ জি তৈরি করে, আমরা দেখাব যে ফর্মুলা-গেমের যে কোনও উদাহরণকে সাধারণীকৃত ভূগোলের একটি উদাহরণে হ্রাস করা যেতে পারে, যেখানে পি1-এর জন্য সর্বোত্তম কৌশলটি পি-এর সমতুল্য এবং পি2-এর জন্য সর্বোত্তম কৌশলটি পি-এর সমতুল্য। নোডের বাম উল্লম্ব চেইনটি ফর্মুলা-গেমে ভেরিয়েবলের জন্য মান নির্বাচন করার পদ্ধতি অনুকরণ করার জন্য ডিজাইন করা হয়েছে। হীরার প্রতিটি কাঠামো একটি পরিমাণগত পরিবর্তনশীলের সাথে মিলে যায়। খেলোয়াড়রা পালা করে প্রতিটি শাখা নোডে পথ নির্ধারণ করে। যেহেতু আমরা ধরে নিয়েছিলাম যে প্রথম কোয়ান্টিফায়ারটি অস্তিত্বমূলক হবে, তাই পি1 প্রথমে যায়, বাম নোডটি নির্বাচন করে যদি x1 সত্য হয় এবং ডান নোডটি যদি x1 মিথ্যা হয়। প্রতিটি খেলোয়াড়কে তখন জোরপূর্বক মোড় নিতে হবে এবং তারপর পি2 x2-এর জন্য একটি মান বেছে নেবে। এই পর্যায়ক্রমিক কাজগুলি বাম দিকে চলতে থাকে। উভয় খেলোয়াড়ই সমস্ত হীরার মধ্য দিয়ে যাওয়ার পরে, আবার পি1-এর পালা, কারণ আমরা ধরে নিয়েছিলাম যে শেষ কোয়ান্টিফায়ারটি অস্তিত্বগত। গ্রাফের ডান দিকের পথ অনুসরণ করা ছাড়া পি1-এর আর কোনও উপায় নেই। তারপর সরে দাঁড়ানোর পালা পি2-এর। যখন খেলাটি গ্রাফের ডান দিকে পৌঁছায়, তখন এটি ফর্মুলা গেমের খেলার শেষের অনুরূপ হয়। মনে রাখবেন যে ফর্মুলা গেমে, পে জিতবে যদি si সত্য হয়, আর পা জিতবে যদি si মিথ্যা হয়। গ্রাফের ডান দিকটি নিশ্চিত করে যে পি1 জিতবে যদি এবং শুধুমাত্র পে জিতবে, এবং পি2 জিতবে যদি এবং শুধুমাত্র যদি পা জিতবে। প্রথমে আমরা দেখাই যে পি 2 সর্বদা জিতে যায় যখন পি জিতে যায়। যদি পা জয়ী হয়, তাহলে si মিথ্যা। যদি si মিথ্যা হয়, তবে একটি অসন্তোষজনক ধারা বিদ্যমান। পি2 জেতার জন্য একটি অসন্তোষজনক ধারা বেছে নেবে। তারপর যখন পি1-এর পালা আসে তখন তাকে অবশ্যই পি2 দ্বারা নির্বাচিত সেই ধারার একটি আক্ষরিক শব্দ বেছে নিতে হবে। যেহেতু ধারার সমস্ত আক্ষরিক শব্দগুলি মিথ্যা, তাই তারা বাম উল্লম্ব শৃঙ্খলে পূর্বে পরিদর্শন করা নোডগুলির সাথে সংযুক্ত হয় না। এটি পি2-কে বাম চেইনের হীরায় সংশ্লিষ্ট নোডের সংযোগ অনুসরণ করতে এবং এটি নির্বাচন করতে দেয়। যাইহোক, পি1 এখন কোনও সংলগ্ন নোড নির্বাচন করতে অক্ষম এবং হারায়। এখন আমরা দেখাব যে পি1 সর্বদা জয়ী হয় যখন পে জয়ী হয়। যদি পে জয়ী হয়, তাহলে si সত্য। যদি si সত্য হয়, তবে গ্রাফের ডান দিকের প্রতিটি ধারায় একটি সত্য আক্ষরিক থাকে। পি2 যে কোনও ধারা বেছে নিতে পারে। তারপর পি1 আক্ষরিক সত্যটি বেছে নেয়। এবং যেহেতু এটি সত্য, বাম উল্লম্ব নোডে এর সংলগ্ন নোডটি ইতিমধ্যে নির্বাচন করা হয়েছে, তাই পি2-এর কোনও পদক্ষেপ করার এবং হারানোর নেই। প্ল্যানার সাধারণীকৃত ভূগোল হল পি. এস. পি. এ. সি. ই-সম্পূর্ণ সাধারণীকৃত ভূগোল হল পি. এস. পি. এ. সি. ই-সম্পূর্ণ, এমনকি যখন প্ল্যানার গ্রাফগুলিতে খেলা হয়। নিম্নলিখিত প্রমাণটি 3-এর উপপাদ্য থেকে পাওয়া যায়। যেহেতু প্ল্যানার জিজি জিজির একটি বিশেষ কেস, এবং জিজি পি. এস. পি. এ. সি-তে রয়েছে, তাই প্ল্যানার জিজি পি. এস. পি. এ. সি-তে রয়েছে। এটি দেখানো বাকি যে প্ল্যানার জিজি স্পেস-হার্ড। এটি প্রমাণ করা যেতে পারে কিভাবে একটি স্বেচ্ছাচারী গ্রাফকে একটি সমতলীয় গ্রাফে রূপান্তরিত করা যায়, যাতে এই গ্রাফে খেলা জি. জি-র একটি খেলার মূল গ্রাফের মতো একই ফলাফল থাকে। এটি করার জন্য, শুধুমাত্র মূল গ্রাফের সমস্ত প্রান্তের ক্রসিংগুলি বাদ দেওয়া প্রয়োজন। আমরা গ্রাফটি এমনভাবে আঁকি যাতে কোনও তিনটি প্রান্ত একটি বিন্দুতে ছেদ না করে এবং একই খেলায় কোনও জোড়া ক্রসিং প্রান্ত ব্যবহার করা যায় না। এটি সাধারণভাবে সম্ভব নয়, তবে একটি ফর্মুলা-গেম উদাহরণ থেকে নির্মিত গ্রাফের জন্য সর্বদা সম্ভব; উদাহরণস্বরূপ, আমরা ক্রসিংয়ের সাথে জড়িত ধারা শীর্ষগুলি থেকে কেবল প্রান্তগুলি পেতে পারি। এখন আমরা প্রতিটি ক্রসিংকে এই গঠন দিয়ে প্রতিস্থাপন করিঃ ফলাফলটি একটি প্ল্যানার গ্রাফ, এবং একই খেলোয়াড় মূল গ্রাফের মতো একটি জয়কে বাধ্য করতে পারেঃ যদি কোনও খেলোয়াড় রূপান্তরিত খেলায় ভি থেকে "উপরে" যাওয়ার সিদ্ধান্ত নেয়, তবে উভয় খেলোয়াড়কে অবশ্যই ডাব্লু-তে "উপরে" যেতে হবে বা অবিলম্বে হারতে হবে। সুতরাং রূপান্তরিত খেলায় ভি থেকে "উপরে" সরে যাওয়া মূল খেলায় ভি → ডাব্লু পদক্ষেপের অনুকরণ করে। যদি ভি-ডাব্লু একটি বিজয়ী পদক্ষেপ হয়, তবে রূপান্তরিত খেলায় ভি থেকে "উপরে" যাওয়াও একটি বিজয়ী পদক্ষেপ, এবং তদ্বিপরীত। সুতরাং, রূপান্তরিত গ্রাফে খেলা জিজি খেলার ফলাফল মূল গ্রাফের মতোই হবে। এই রূপান্তরের জন্য সময় লাগে যা মূল গ্রাফের প্রান্ত ছেদগুলির সংখ্যার একটি ধ্রুবক গুণিতক, সুতরাং এটি বহুপদী সময় নেয়। এইভাবে প্ল্যানার জিজি হল পি. এস. পি. এ. সি. ই-সম্পূর্ণ। সর্বাধিক ডিগ্রি 3 সহ প্ল্যানার দ্বিদলীয় গ্রাফ সর্বাধিক ডিগ্রি 3 সহ প্ল্যানার দ্বিদলীয় গ্রাফগুলিতে খেলা হয়, 3 এর চেয়ে বেশি ডিগ্রির শীর্ষগুলিকে সর্বাধিক ডিগ্রি 3 সহ শীর্ষগুলির একটি শৃঙ্খল দিয়ে প্রতিস্থাপন করে এখনও পি. এস. পি. এ. সি. ই সম্পূর্ণ। প্রমাণ রয়েছে। এবং নিম্নলিখিত গঠনটি ব্যবহার করেঃ যদি একজন খেলোয়াড় এই নির্মাণের যে কোনও প্রবেশদ্বার ব্যবহার করে, তবে অন্য খেলোয়াড় বেছে নেয় যে কোন প্রস্থানটি ব্যবহার করা হবে। এছাড়াও নির্মাণটি শুধুমাত্র একবার অতিক্রম করা যেতে পারে, কারণ কেন্দ্রীয় শীর্ষটি সর্বদা পরিদর্শন করা হয়। তাই এই গঠনটি মূল শীর্ষের সমতুল্য। জিজির একটি রূপকে প্রান্ত ভূগোল বলা হয়, যেখানে প্রতিটি পদক্ষেপের পরে, খেলোয়াড় যে প্রান্তের মধ্য দিয়ে গেছে তা মুছে ফেলা হয়। এটি মূল জিজির বিপরীতে, যেখানে প্রতিটি পদক্ষেপের পরে, খেলোয়াড় যে শীর্ষে থাকতেন তা মুছে ফেলা হয়। এই দৃষ্টিতে, মূল জিজিকে ভার্টেক্স ভূগোল বলা যেতে পারে। প্রান্তের ভূগোল পি. এস. পি. এ. সি. ই-সম্পূর্ণ। এটি একই নির্মাণ ব্যবহার করে প্রমাণিত হতে পারে যা শীর্ষ ভূগোলের জন্য ব্যবহৃত হয়েছিল। অনির্দিষ্ট ভূগোল একটি অনির্দিষ্ট গ্রাফের উপর ভূগোল খেলা খেলার কথাও বিবেচনা করা যেতে পারে (অর্থাৎ, প্রান্তগুলি উভয় দিকেই অতিক্রম করা যেতে পারে)। ফ্রেনকেল, শাইনারম্যান এবং উলম্যান দেখান যে অনির্দিষ্ট শীর্ষ ভূগোল বহুপদী সময়ে সমাধান করা যেতে পারে, যেখানে অনির্দিষ্ট প্রান্ত ভূগোল পি. এস. পি. এ. সি. ই-সম্পূর্ণ, এমনকি সর্বোচ্চ ডিগ্রি 3 সহ সমতলীয় গ্রাফের ক্ষেত্রেও। যদি গ্রাফটি দ্বিদলীয় হয়, তবে অনির্দিষ্ট প্রান্ত ভূগোল বহুপদী সময়ে সমাধানযোগ্য। ফলস্বরূপ জি. জি. পি. এস. পি. এ. সি. ই-সম্পূর্ণ, পি = পি. এস. পি. এ. সি ছাড়া জি. জি-তে সর্বোত্তম খেলার জন্য কোনও বহুপদী সময় অ্যালগরিদম বিদ্যমান নেই। যাইহোক, অন্যান্য খেলার জটিলতা প্রমাণ করা এত সহজ নাও হতে পারে কারণ নির্দিষ্ট কিছু খেলায় (যেমন দাবা) সীমিত সংখ্যক খেলার অবস্থান থাকে-যা একটি পি. এস. পি. এ. সি. ই-সম্পূর্ণ সমস্যার ম্যাপিং তৈরি করা কঠিন (বা অসম্ভব) করে তোলে। তা সত্ত্বেও, কিছু নির্দিষ্ট খেলার জটিলতা এখনও সাধারণীকরণের মাধ্যমে বিশ্লেষণ করা যেতে পারে (যেমন, একটি এন × এন বোর্ডে)। জিজি-র সম্পূর্ণতার প্রমাণ হিসাবে সাধারণীকৃত গো-এর প্রমাণের জন্য রেফারেন্সগুলি দেখুন। রেফারেন্স মাইকেল সিপসার, ইন্ট্রোডাকশন টু দ্য থিওরি অফ কম্পিউটশন, পিডব্লিউএস, 1997। স্পেস-সম্পূর্ণ সমস্যা