Existential theory of the reals
গাণিতিক যুক্তি, গণনামূলক জটিলতা তত্ত্ব এবং কম্পিউটার বিজ্ঞানে, বাস্তবগুলির অস্তিত্ব তত্ত্ব হল সেই রূপের সমস্ত সত্য বাক্যের সেট যেখানে চলকগুলিকে বাস্তব সংখ্যার মান হিসাবে ব্যাখ্যা করা হয় এবং যেখানে বাস্তব বহুপদের সমতা এবং বৈষম্যের সাথে জড়িত একটি পরিমাণ-মুক্ত সূত্র রয়েছে। এই ফর্মের একটি বাক্য সত্য হয় যদি সমস্ত চলকের জন্য মান খুঁজে পাওয়া সম্ভব হয়, যা যখন সূত্রে প্রতিস্থাপিত হয়, তখন এটি সত্য হয়ে যায়। বাস্তবতার অস্তিত্বগত তত্ত্বের সিদ্ধান্তের সমস্যা হল এমন একটি অ্যালগরিদম খুঁজে বের করার সমস্যা যা এই ধরনের প্রতিটি বাক্যের জন্য সিদ্ধান্ত নেয় যে এটি সত্য কি মিথ্যা। সমতুল্যভাবে, এটি একটি প্রদত্ত আধা-বীজগাণিতিক সেট খালি নয় কিনা তা পরীক্ষা করার সমস্যা। এই সিদ্ধান্তের সমস্যাটি এন. পি-হার্ড এবং পি. এস. পি. এ. সি. ই-তে রয়েছে, যা অস্তিত্বগত কোয়ান্টিফায়ারের সীমাবদ্ধতা ছাড়াই রিয়েলের প্রথম-ক্রম তত্ত্বে বিবৃতি নির্ধারণের জন্য আলফ্রেড টারস্কির কোয়ান্টিফায়ার এলিমিনেশন পদ্ধতির তুলনায় উল্লেখযোগ্যভাবে কম জটিলতা দেয়। যাইহোক, বাস্তবে, প্রথম-ক্রম তত্ত্বের জন্য সাধারণ পদ্ধতিগুলি এই সমস্যাগুলি সমাধানের জন্য পছন্দসই পছন্দ হিসাবে রয়ে গেছে। জটিলতার শ্রেণীকে সংজ্ঞায়িত করা হয়েছে গণনামূলক সমস্যার শ্রেণীকে বর্ণনা করার জন্য যা এই রূপের সমতুল্য বাক্যে অনুবাদ করা যেতে পারে। কাঠামোগত জটিলতা তত্ত্বে, এটি এন. পি এবং পি. এস. পি. এ. সি-এর মধ্যে অবস্থিত। জ্যামিতিক গ্রাফ তত্ত্বের অনেক প্রাকৃতিক সমস্যা, বিশেষত জ্যামিতিক ছেদ গ্রাফগুলি সনাক্তকরণ এবং ক্রসিং সহ গ্রাফ অঙ্কনের প্রান্তগুলি সোজা করার সমস্যাগুলি এই শ্রেণীর অন্তর্গত এবং সম্পূর্ণ। এখানে, সম্পূর্ণতার অর্থ হল বিপরীত দিকে একটি অনুবাদ বিদ্যমান, বাস্তবতার উপর একটি স্বেচ্ছাচারী বাক্য থেকে প্রদত্ত সমস্যার সমতুল্য উদাহরণে। গাণিতিক যুক্তিতে, একটি তত্ত্ব হল একটি আনুষ্ঠানিক ভাষা যা একটি নির্দিষ্ট প্রতীকের সেট ব্যবহার করে লিখিত বাক্যের একটি সেট নিয়ে গঠিত। বাস্তব বদ্ধ ক্ষেত্রগুলির প্রথম-ক্রম তত্ত্বের নিম্নলিখিত প্রতীকগুলি রয়েছেঃ ধ্রুবক 0 এবং 1, চলকগুলির একটি গণনাযোগ্য সংগ্রহ, যোগ, বিয়োগ, গুণ, এবং (ঐচ্ছিকভাবে) বিভাজন ক্রিয়াকলাপ, প্রতীক <, ≤, =, ±,>, এবং বাস্তব মানগুলির তুলনার জন্য  ঒ত্ত, যৌক্তিক সংযোগকারী, ′, ′, এবং ′, বন্ধনী, এবং সর্বজনীন পরিমাণক β এবং অস্তিত্বগত পরিমাণক ′ এই প্রতীকগুলির ক্রমটি একটি বাক্য গঠন করে যা বাস্তবগুলির প্রথম-ক্রম তত্ত্বের অন্তর্গত যদি এটি ব্যাকরণগতভাবে ভালভাবে গঠিত হয়, তবে এর সমস্ত চলকগুলি সঠিকভাবে পরিমাপ করা হয় এবং (যখন প্রকৃত সংখ্যা সম্পর্কে গাণিতিক বিবৃতি হিসাবে ব্যাখ্যা করা হয়) এটি একটি টারস্কি যেমন দেখিয়েছেন, এই তত্ত্বটি একটি স্বতঃসিদ্ধ স্কিমা এবং একটি সিদ্ধান্ত পদ্ধতি দ্বারা বর্ণনা করা যেতে পারে যা সম্পূর্ণ এবং কার্যকরঃ প্রতিটি সম্পূর্ণ পরিমাণগত এবং ব্যাকরণগত বাক্যের জন্য, বাক্য বা এর নেতিবাচকতা (তবে উভয়ই নয়) স্বতঃসিদ্ধ থেকে উদ্ভূত হতে পারে। একই তত্ত্ব শুধুমাত্র বাস্তব সংখ্যা নয়, প্রতিটি বাস্তব বদ্ধ ক্ষেত্রকে বর্ণনা করে। যাইহোক, অন্যান্য সংখ্যা ব্যবস্থা রয়েছে যা এই স্বতঃসিদ্ধ দ্বারা সঠিকভাবে বর্ণনা করা হয় না; বিশেষত, বাস্তব সংখ্যার পরিবর্তে পূর্ণসংখ্যার জন্য একইভাবে সংজ্ঞায়িত তত্ত্বটি অনিশ্চিত, এমনকি মাতিয়াসেভিচের উপপাদ্য দ্বারা অস্তিত্বমূলক বাক্যগুলির (ডায়োফ্যান্টাইন সমীকরণ) জন্যও। বাস্তবগুলির অস্তিত্ব তত্ত্ব হল প্রথম-ক্রম তত্ত্বের একটি অংশ যা বাক্যগুলির সমন্বয়ে গঠিত যেখানে সমস্ত পরিমাপকারী অস্তিত্বগত এবং তারা অন্য যে কোনও প্রতীকের আগে উপস্থিত হয়। অর্থাৎ, এটি ফর্মের সমস্ত সত্য বাক্যের সেট যেখানে বাস্তব বহুপদের সমতা এবং বৈষম্যের সাথে জড়িত একটি পরিমাণ-মুক্ত সূত্র। বাস্তব তত্ত্বের অস্তিত্বগত তত্ত্বের জন্য সিদ্ধান্তের সমস্যা হল প্রদত্ত বাক্যটি এই তত্ত্বের অন্তর্গত কিনা তা পরীক্ষা করার অ্যালগরিদমিক সমস্যা; সমতুল্যভাবে, যে স্ট্রিংগুলি মৌলিক সিনট্যাক্টিকাল চেকগুলি পাস করে (তারা সঠিক সিনট্যাক্স সহ সঠিক চিহ্নগুলি ব্যবহার করে এবং কোনও পরিমাণহীন ভেরিয়েবল নেই) এটি বাক্যটি বাস্তব সংখ্যা সম্পর্কে একটি সত্য বিবৃতি কিনা তা পরীক্ষা করার সমস্যা। বাস্তব সংখ্যার-টুপলগুলির যে সেটটি সত্য, তাকে অর্ধ-বীজগাণিতিক সেট বলা হয়, তাই বাস্তবগুলির অস্তিত্ব তত্ত্বের সিদ্ধান্তের সমস্যাটি প্রদত্ত অর্ধ-বীজগাণিতিক সেটটি অকার্যকর কিনা তা পরীক্ষা হিসাবে সমতুল্যভাবে পুনরায় বলা যেতে পারে। বাস্তব অস্তিত্ব তত্ত্বের জন্য সিদ্ধান্ত সমস্যার জন্য অ্যালগরিদমের সময় জটিলতা নির্ধারণে, ইনপুটের আকারের একটি পরিমাপ থাকা গুরুত্বপূর্ণ। এই ধরনের সহজতম পরিমাপ হল একটি বাক্যের দৈর্ঘ্যঃ অর্থাৎ, এতে থাকা প্রতীকগুলির সংখ্যা। যাইহোক, এই সমস্যার জন্য অ্যালগরিদমের আচরণের আরও সুনির্দিষ্ট বিশ্লেষণ অর্জনের জন্য, ইনপুটের আকারকে বিভিন্ন চলকগুলিতে বিভক্ত করা, পরিমাপ করার জন্য চলকের সংখ্যা, বাক্যের মধ্যে বহুপদের সংখ্যা এবং এই বহুপদের মাত্রা আলাদা করা সুবিধাজনক। উদাহরণস্বরূপ, স্বর্ণ অনুপাতকে বহুপদের মূল হিসাবে সংজ্ঞায়িত করা যেতে পারে। এই বহুপদের দুটি মূল রয়েছে, যার মধ্যে কেবল একটি (সুবর্ণ অনুপাত) একের চেয়ে বেশি। সুতরাং, স্বর্ণ অনুপাতের অস্তিত্ব বাক্য দ্বারা প্রকাশ করা যেতে পারে কারণ স্বর্ণ অনুপাত অতীন্দ্রিয় নয়, এটি একটি সত্য বাক্য, এবং বাস্তবতার অস্তিত্ব তত্ত্বের অন্তর্গত। বাস্তবগুলির অস্তিত্বগত তত্ত্বের সিদ্ধান্ত সমস্যার উত্তর, এই বাক্যটিকে ইনপুট হিসাবে দেওয়া হলে, বুলিয়ান মানটি সত্য। গাণিতিক এবং জ্যামিতিক অর্থের বৈষম্য বলে যে, প্রতি দুটি অ-ঋণাত্মক সংখ্যার জন্য এবং নিম্নলিখিত বৈষম্যটি ধারণ করেঃ উপরে বর্ণিত হিসাবে, এটি বাস্তব সংখ্যা সম্পর্কে একটি প্রথম-ক্রমের বাক্য, তবে অস্তিত্বগত পরিমাণের পরিবর্তে সর্বজনীন, এবং যা বিভাজন, বর্গমূল এবং 2 নম্বরের জন্য অতিরিক্ত প্রতীক ব্যবহার করে যা বাস্তবগুলির প্রথম-ক্রম তত্ত্বে অনুমোদিত নয়। যাইহোক, উভয় পক্ষকে বর্গ করে এটিকে নিম্নলিখিত অস্তিত্বগত বিবৃতিতে রূপান্তরিত করা যেতে পারে যা বৈষম্যের কোনও বিপরীত উদাহরণ আছে কিনা তা জিজ্ঞাসা করা হিসাবে ব্যাখ্যা করা যেতে পারেঃ বাস্তবতার অস্তিত্বগত তত্ত্বের জন্য সিদ্ধান্ত সমস্যার উত্তর, এই বাক্যটিকে ইনপুট হিসাবে দেওয়া হয়েছে, বুলিয়ান মানটি মিথ্যাঃ কোনও বিপরীত উদাহরণ নেই। অতএব, এই বাক্যটি সঠিক ব্যাকরণগত রূপ হওয়া সত্ত্বেও বাস্তবতার অস্তিত্ব তত্ত্বের অন্তর্গত নয়। অ্যালগরিদম আলফ্রেড টারস্কির কোয়ান্টিফায়ার এলিমিনেশন পদ্ধতি (1948) দেখায় যে রিয়েলগুলির অস্তিত্বগত তত্ত্ব (এবং আরও সাধারণভাবে রিয়েলগুলির প্রথম ক্রম তত্ত্ব) অ্যালগরিদমগতভাবে সমাধানযোগ্য, তবে এর জটিলতার উপর কোনও প্রাথমিক সীমা ছাড়াই। জর্জ ই. কলিন্সের (1975) নলাকার বীজগাণিতিক পচন পদ্ধতি সময়ের নির্ভরশীলতাকে দ্বিগুণ সূচকীয় করে তোলে, যেখানে বাক্যের সহগগুলির প্রতিনিধিত্ব করার জন্য প্রয়োজনীয় বিটের সংখ্যা যার মান নির্ধারণ করতে হবে, সেটি হল বাক্যে বহুপদের সংখ্যা, তাদের মোট ডিগ্রি এবং চলকের সংখ্যা। 1988 সালের মধ্যে, ডিমা গ্রিগোরিয়েভ এবং নিকোলাই ভোরোবজভ একটি বহুপদীতে জটিলতাকে সূচকীয় বলে দেখিয়েছিলেন এবং 1992 সালে প্রকাশিত গবেষণাপত্রের একটি ক্রমে জেমস রেনেগার এটিকে এককভাবে সূচকীয় নির্ভরতায় উন্নত করেছিলেন। এই অ্যালগরিদমগুলির অ্যাসিম্পটোটিক গণনামূলক জটিলতা বিভ্রান্তিকর হতে পারে, কারণ বাস্তবে এগুলি কেবল খুব ছোট আকারের ইনপুটগুলিতে চালানো যেতে পারে। 1991 সালের একটি তুলনায়, হুন হং অনুমান করেছিলেন যে কলিন্সের দ্বিগুণ সূচকীয় পদ্ধতি এমন একটি সমস্যা সমাধান করতে সক্ষম হবে যার আকার উপরের সমস্ত পরামিতিগুলি এক সেকেন্ডেরও কম সময়ে 2-এ সেট করে বর্ণনা করা হয়েছে, যেখানে গ্রিগোরিয়েভ, ভর্বজভ এবং রেনেগারের অ্যালগরিদমগুলি পরিবর্তে এক মিলিয়ন বছরেরও বেশি সময় নেবে। 1993 সালে, জুওস, রয় এবং সোলার্নো পরামর্শ দিয়েছিলেন যে সূচকীয়-সময় পদ্ধতিগুলিতে ছোট পরিবর্তন করা সম্ভব হওয়া উচিত যাতে এগুলি নলাকার বীজগাণিতিক সিদ্ধান্তের পাশাপাশি তত্ত্বের দিক থেকেও দ্রুততর হয়। যাইহোক, 2009 সালের হিসাবে, এটি এখনও ছিল যে বাস্তবগুলির প্রথম-ক্রম তত্ত্বের জন্য সাধারণ পদ্ধতিগুলি বাস্তবগুলির অস্তিত্ব তত্ত্বের জন্য বিশেষায়িত একক সূচকীয় অ্যালগরিদমগুলির তুলনায় অনুশীলনে উচ্চতর ছিল। সম্পূর্ণ সমস্যা গণনামূলক জটিলতা এবং জ্যামিতিক গ্রাফ তত্ত্বের বেশ কয়েকটি সমস্যাকে বাস্তব অস্তিত্ব তত্ত্বের জন্য সম্পূর্ণ হিসাবে শ্রেণীবদ্ধ করা যেতে পারে। অর্থাৎ, বাস্তবতার অস্তিত্ববাদী তত্ত্বের প্রতিটি সমস্যার একটি বহুপদী-সময় বহু-এক হ্রাস রয়েছে এই সমস্যাগুলির মধ্যে একটির উদাহরণে, এবং ফলস্বরূপ এই সমস্যাগুলি বাস্তবতার অস্তিত্ববাদী তত্ত্বের জন্য হ্রাসযোগ্য। এই ধরনের বেশ কয়েকটি সমস্যা একটি নির্দিষ্ট ধরনের ছেদ গ্রাফের স্বীকৃতি নিয়ে উদ্বেগ প্রকাশ করে। এই সমস্যাগুলির মধ্যে, ইনপুট হল একটি অনির্দিষ্ট গ্রাফ; লক্ষ্য হল নির্ধারণ করা যে কোনও নির্দিষ্ট শ্রেণীর আকৃতির জ্যামিতিক আকারগুলি গ্রাফের শীর্ষগুলির সাথে এমনভাবে যুক্ত হতে পারে কিনা যাতে দুটি শীর্ষ গ্রাফের সাথে সংলগ্ন থাকে যদি এবং শুধুমাত্র যদি তাদের সম্পর্কিত আকারগুলির একটি অ-খালি ছেদ থাকে। বাস্তব অস্তিত্ব তত্ত্বের জন্য সম্পূর্ণ এই ধরনের সমস্যাগুলির মধ্যে রয়েছে সমতলে রেখাখন্ডগুলির ছেদ গ্রাফের স্বীকৃতি, একক ডিস্ক গ্রাফের স্বীকৃতি এবং সমতলে উত্তল সেটগুলির ছেদ গ্রাফের স্বীকৃতি। ক্রসিং ছাড়াই সমতলে আঁকা গ্রাফগুলির জন্য, ফ্যারির উপপাদ্যটি বলে যে গ্রাফের প্রান্তগুলি সরলরেখার অংশ হিসাবে বা নির্বিচারে বক্ররেখা হিসাবে আঁকা হয় কিনা তা নির্বিশেষে একই শ্রেণীর সমতলীয় গ্রাফ পাওয়া যায়। কিন্তু এই সমতা অন্যান্য ধরনের অঙ্কনের ক্ষেত্রে প্রযোজ্য নয়। উদাহরণস্বরূপ, যদিও একটি গ্রাফের ক্রসিং নম্বর (নির্বিচারে বাঁকানো প্রান্ত সহ একটি অঙ্কনে ক্রসিংয়ের সর্বনিম্ন সংখ্যা) এনপিতে নির্ধারণ করা যেতে পারে, তবে প্রকৃত অস্তিত্ব তত্ত্বের জন্য এটি নির্ধারণ করা সম্পূর্ণ যে আয়তক্ষেত্রাকার ক্রসিং নম্বরের উপর একটি প্রদত্ত সীমা অর্জন করার জন্য একটি অঙ্কন বিদ্যমান কিনা (সমতলে সরলরেখার অংশ হিসাবে আঁকা প্রান্ত সহ যে কোনও অঙ্কনে অতিক্রম করা প্রান্তের জোড়ার সর্বনিম্ন সংখ্যা)। সরলরেখার প্রান্ত সহ সমতলে একটি প্রদত্ত গ্রাফ আঁকা যেতে পারে কিনা এবং তার ক্রসিং হিসাবে প্রান্ত জোড়ার একটি নির্দিষ্ট সেট দিয়ে, বা সমতুল্যভাবে, ক্রসিং সহ একটি বাঁকা অঙ্কন এমনভাবে সোজা করা যেতে পারে কিনা তা পরীক্ষা করার জন্য বাস্তব অস্তিত্ব তত্ত্বের জন্য এটি সম্পূর্ণ। বাস্তব অস্তিত্ব তত্ত্বের অন্যান্য সম্পূর্ণ সমস্যাগুলির মধ্যে রয়েছেঃ একটি প্রদত্ত বহুভুজের সমস্ত বিন্দু যেখান থেকে দৃশ্যমান হয় সেই ক্ষুদ্রতম সংখ্যক বিন্দু খুঁজে বের করার আর্ট গ্যালারি সমস্যা। নিউরাল নেটওয়ার্ক প্রশিক্ষণ। একটি প্রদত্ত বহুভুজ একটি প্রদত্ত বর্গাকার পাত্রে ফিট করতে পারে কিনা তা নির্ধারণ করার প্যাকিং সমস্যা। একক দূরত্বের গ্রাফগুলির স্বীকৃতি, এবং একটি গ্রাফের মাত্রা বা ইউক্লিডীয় মাত্রা সর্বাধিক একটি প্রদত্ত মান কিনা তা পরীক্ষা করা। সিউডোলাইনগুলির প্রসারিততা (অর্থাৎ, সমতলে বক্ররেখার একটি পরিবার দেওয়া হয়েছে, যা নির্ধারণ করে যে তারা একটি রেখা বিন্যাসের সমরূপ কিনা); যে কোনও নির্দিষ্ট মাত্রা> 2-এ জ্যামিতিক কোয়ান্টাম লজিকের দুর্বল এবং শক্তিশালী সন্তোষজনকতা উভয়ই; দ্ব্যর্থহীন স্বয়ংক্রিয়তার ক্ষেত্রে মডেল চেকিং ব্যবধান মার্কভ চেইন। অ্যালগরিদমিক স্টেনিৎজ সমস্যা (একটি জাল দেওয়া, এটি একটি উত্তল পলিটোপের মুখ জাল কিনা তা নির্ধারণ করুন), এমনকি যখন 4-মাত্রিক পলিটোপগুলিতে সীমাবদ্ধ থাকে; নির্দিষ্ট উত্তল বস্তুর বিন্যাসের উপলব্ধি স্থানগুলি মাল্টি-প্লেয়ার গেমগুলির ন্যাশ ইকুইলিব্রিয়ার বিভিন্ন বৈশিষ্ট্যগুলি ত্রি-মাত্রিক ইউক্লিডিয়ান স্পেসে ত্রিভুজ এবং চতুর্ভুজগুলির একটি প্রদত্ত বিমূর্ত জটিল জটিলকে এম্বেড করে; সমতলে সেট করা একটি ভাগ করা শীর্ষে একাধিক গ্রাফ এম্বেড করা যাতে সমস্ত গ্রাফগুলি ক্রসিং ছাড়াই আঁকা হয়; প্ল্যানার পয়েন্ট সেটগুলির দৃশ্যমানতা গ্রাফগুলি স্বীকৃতি দেওয়া; (প্রজেক্টিভ বা নন-ট্রিভিয়াল অ্যাফিন) ক্রস প্রোডাক্টের উপর দুটি পদের মধ্যে একটি সমীকরণের সন্তোষজনকতা; ন্যূনতম ঢাল সংখ্যা নির্ধারণ করা নিম্ন-পদমর্যাদার ম্যাট্রিক্স সমাপ্তি সমস্যা। এর উপর ভিত্তি করে, জটিলতা শ্রেণীকে বাস্তব অস্তিত্ব তত্ত্বের একটি বহুপদী-বহু-এক হ্রাস সহ সমস্যাগুলির সেট হিসাবে সংজ্ঞায়িত করা হয়েছে। হিলবার্টের দশম সমস্যাটিও দেখুন, পূর্ণসংখ্যার (অনির্ধারিত) অস্তিত্ব তত্ত্বের উপর তথ্যসূত্র গাণিতিক গণনামূলক জটিলতা তত্ত্বের আনুষ্ঠানিক তত্ত্ব বাস্তব বীজগাণিতিক জ্যামিতি