Existential theory of the reals
ریاضیاتی منطق، کمپیوٹیشنل پیچیدگی تھیوری، اور کمپیوٹر سائنس میں، حقیقی کا وجودی نظریہ اس شکل کے تمام حقیقی جملوں کا مجموعہ ہے جہاں متغیرات کی تشریح حقیقی تعداد کی اقدار کے طور پر کی جاتی ہے، اور جہاں ایک مقداری آزاد فارمولا ہے جس میں مساوات اور عدم مساوات شامل ہیں۔ اس شکل کا ایک جملہ درست ہے اگر ان تمام متغیرات کے لیے اقدار تلاش کرنا ممکن ہو جو فارمولے میں تبدیل ہونے پر اسے درست بناتی ہیں۔ حقیقی وجود کے نظریہ کے لیے فیصلہ کا مسئلہ ایک الگورتھم تلاش کرنے کا مسئلہ ہے جو اس طرح کے ہر جملے کے لیے فیصلہ کرتا ہے کہ آیا یہ درست ہے یا غلط۔ اسی طرح، یہ جانچنے کا مسئلہ ہے کہ آیا دیا گیا نیم الجبرائی سیٹ خالی نہیں ہے۔ یہ فیصلہ کا مسئلہ این پی سخت ہے اور پی ایس پی اے سی ای میں مضمر ہے، جو اسے وجود کے مقداریوں کی پابندی کے بغیر حقیقی کے پہلے درجے کے نظریہ میں بیانات کا فیصلہ کرنے کے لیے الفریڈ ٹارسکی کے مقداری خاتمے کے طریقہ کار سے نمایاں طور پر کم پیچیدگی دیتا ہے۔ تاہم، عملی طور پر، ان مسائل کو حل کرنے کے لیے فرسٹ آرڈر تھیوری کے لیے عمومی طریقے ترجیحی انتخاب ہیں۔ پیچیدگی کلاس کی تعریف کمپیوٹیشنل مسائل کی کلاس کو بیان کرنے کے لیے کی گئی ہے جن کا ترجمہ اس شکل کے مساوی جملوں میں کیا جا سکتا ہے۔ ساختی پیچیدگی کے نظریہ میں، یہ این پی اور پی ایس پی اے سی ای کے درمیان ہے۔ جیومیٹرک گراف تھیوری میں بہت سے قدرتی مسائل، خاص طور پر جیومیٹرک انٹرسیکشن گراف کو پہچاننے اور کراسنگ کے ساتھ گراف ڈرائنگ کے کناروں کو سیدھا کرنے کے مسائل، اس کلاس سے تعلق رکھتے ہیں، اور اس کے لیے مکمل ہیں۔ یہاں، مکمل ہونے کا مطلب یہ ہے کہ الٹی سمت میں ترجمہ موجود ہے، حقیقی پر من مانی جملے سے دیئے گئے مسئلے کے مساوی مثال میں۔ ریاضیاتی منطق میں، نظریہ ایک رسمی زبان ہے جو علامتوں کے ایک مقررہ سیٹ کا استعمال کرتے ہوئے لکھے گئے جملوں کے ایک سیٹ پر مشتمل ہوتی ہے۔ حقیقی بند فیلڈز کے فرسٹ آرڈر تھیوری میں درج ذیل علامتیں ہوتی ہیں: مستقل 0 اور 1، متغیرات کا ایک قابل شمار مجموعہ، اضافہ، گھٹاؤ، ضرب، اور (اختیاری طور پر) تقسیم کی کارروائیاں، علامتیں <، ≤، =، ±،>، اور حقیقی اقدار کے موازنہ کے لیے، منطقی کنیکٹیوز، ′، ′، اور ′، قوسین، اور یونیورسل کوانٹیفایر ′ اور ان علامتوں کا وجودی کوانٹیفایر ′ ایک ایسا جملہ تشکیل دیتا ہے جو حقیقی کے فرسٹ آرڈر تھیوری سے تعلق رکھتا ہے اگر یہ گراماتی طور پر اچھی طرح سے تشکیل شدہ ہے، تو اس کے تمام متغیرات کو مناسب طریقے سے مقداری کیا جاتا ہے، اور (جب حقیقی اعداد کے بارے میں ریاضیاتی بیان کے طور پر تشریح کی جاتی ہے) جیسا کہ تارسکی نے دکھایا، اس نظریہ کو ایک محوری سکیم اور ایک ایسے فیصلہ سازی کے طریقہ کار سے بیان کیا جا سکتا ہے جو مکمل اور موثر ہو: ہر مکمل مقداری اور گرائمیکل جملے کے لیے، یا تو جملہ یا اس کی نفی (لیکن دونوں نہیں) محوریوں سے اخذ کی جا سکتی ہے۔ یہی نظریہ ہر حقیقی بند فیلڈ کو بیان کرتا ہے، نہ کہ صرف حقیقی اعداد کو۔ تاہم، دوسرے نمبر سسٹم بھی ہیں جنہیں ان محوریوں کے ذریعے درست طریقے سے بیان نہیں کیا گیا ہے۔ خاص طور پر، حقیقی اعداد کے بجائے انٹیجرز کے لیے اسی طرح بیان کیا گیا نظریہ ناقابل فیصلہ ہے، یہاں تک کہ میٹیسیویچ کے نظریہ کے ذریعے موجود جملے (ڈیوفنٹین مساوات) کے لیے بھی۔ حقیقی کا وجودی نظریہ فرسٹ آرڈر تھیوری کا وہ ٹکڑا ہے جو جملوں پر مشتمل ہوتا ہے جس میں تمام مقداری موجود ہوتے ہیں اور وہ کسی بھی دوسری علامت سے پہلے ظاہر ہوتے ہیں۔ یعنی، یہ اس شکل کے تمام حقیقی جملوں کا مجموعہ ہے جہاں ایک مقداری آزاد فارمولا ہے جس میں حقیقی کثیر الجہتی کی مساوات اور عدم مساوات شامل ہیں۔ حقیقی کے وجودی نظریہ کے لیے فیصلہ کا مسئلہ یہ جانچنے کا الگورتھمک مسئلہ ہے کہ آیا دیا گیا جملہ اس نظریہ سے تعلق رکھتا ہے۔ مساوی طور پر، ان تاروں کے لیے جو بنیادی نحو چیک پاس کرتے ہیں (وہ صحیح نحو کے ساتھ صحیح علامتوں کا استعمال کرتے ہیں، اور ان میں کوئی غیر متغیر متغیر نہیں ہوتے ہیں) یہ جانچنے کا مسئلہ ہے کہ آیا جملہ حقیقی اعداد کے بارے میں درست بیان ہے یا نہیں۔ حقیقی اعداد کے-tuples کا مجموعہ جس کے لیے درست ہے اسے سیمی الجبری سیٹ کہا جاتا ہے، اس لیے حقیقی کے وجودی نظریہ کے لیے فیصلہ کے مسئلے کو مساوی طور پر جانچ کے طور پر دوبارہ بیان کیا جا سکتا ہے کہ آیا دیا گیا سیمی الجبری سیٹ غیر خالی ہے۔ حقیقی وجود کے نظریہ کے لیے فیصلہ کے مسئلے کے لیے الگورتھم کی وقت کی پیچیدگی کا تعین کرنے میں، ان پٹ کے سائز کی پیمائش کرنا ضروری ہے۔ اس قسم کی سب سے آسان پیمائش کسی جملے کی لمبائی ہے: یعنی اس میں موجود علامتوں کی تعداد۔ تاہم، اس مسئلے کے لیے الگورتھم کے رویے کا زیادہ درست تجزیہ حاصل کرنے کے لیے، ان پٹ سائز کو کئی متغیرات میں تقسیم کرنا آسان ہے، جس میں متغیرات کی تعداد، جملے کے اندر کثیر الجہتی کی تعداد، اور ان کثیر الجہتی کی ڈگری کو الگ کیا جائے۔ مثالیں سنہری تناسب کو کثیر الجہتی کی جڑ کے طور پر بیان کیا جا سکتا ہے۔ اس کثیر الجہتی کی دو جڑیں ہیں، جن میں سے صرف ایک (سنہری تناسب) ایک سے زیادہ ہے۔ اس طرح، سنہری تناسب کے وجود کا اظہار جملے کے ذریعے کیا جا سکتا ہے کیونکہ سنہری تناسب ماورائی نہیں ہے، یہ ایک حقیقی جملہ ہے، اور حقیقی کے وجودی نظریہ سے تعلق رکھتا ہے۔ حقیقی کے وجودی نظریہ کے لیے فیصلہ کے مسئلے کا جواب، اس جملے کو ان پٹ کے طور پر دیا گیا ہے، بولین ویلیو درست ہے۔ ریاضی اور ہندسی ذرائع کی عدم مساوات یہ بتاتی ہے کہ، ہر دو غیر منفی نمبروں کے لیے اور، مندرجہ ذیل عدم مساوات برقرار ہے: جیسا کہ اوپر بیان کیا گیا ہے، یہ حقیقی اعداد کے بارے میں ایک فرسٹ آرڈر جملے ہے، لیکن ایک وجود کے مقداری کے بجائے عالمگیر کے ساتھ، اور وہ جو تقسیم، مربع جڑوں، اور نمبر 2 کے لیے اضافی علامتوں کا استعمال کرتا ہے جس کی حقیقی کے فرسٹ آرڈر تھیوری میں اجازت نہیں ہے۔ تاہم، دونوں اطراف کو مربع کرنے سے اسے درج ذیل وجودی بیان میں تبدیل کیا جا سکتا ہے جس کی تشریح یہ پوچھنے کے طور پر کی جا سکتی ہے کہ آیا عدم مساوات میں کوئی جوابی مثالیں ہیں: حقیقی کے وجودی نظریہ کے لیے فیصلہ کے مسئلے کا جواب، اس جملے کو ان پٹ کے طور پر دیا گیا ہے، بولین ویلیو غلط ہے: کوئی جوابی مثالیں نہیں ہیں۔ لہذا، یہ جملہ صحیح گرائمیکل شکل کا ہونے کے باوجود، حقیقی کے وجودی نظریہ سے تعلق نہیں رکھتا ہے۔ الگورتھم الفریڈ ٹارسکی کا مقداری خاتمے کا طریقہ (1948) نے حقیقی کے وجودی نظریہ (اور زیادہ عام طور پر حقیقی کے پہلے ترتیب کے نظریہ) کو الگورتھم کے لحاظ سے حل کرنے کے قابل دکھایا، لیکن اس کی پیچیدگی پر کسی ابتدائی پابند کے بغیر۔ جارج ای کولنز (1975) کے بیلناکار الجبرائی سڑنے کے طریقہ کار نے وقت کے انحصار کو دوگنا ایکسپونینشل تک بہتر بنایا، اس شکل کی جہاں جملے میں کوفشنٹس کی نمائندگی کرنے کے لیے درکار بٹس کی تعداد ہے جس کی قیمت کا تعین کیا جانا ہے، جملے میں کثیر الجہتی کی تعداد ہے، ان کی کل ڈگری ہے، اور متغیرات کی تعداد ہے۔ 1988 تک، دیما گریگوریف اور نیکولائی ووروبجوف نے پیچیدگی کو کثیر الجہتی میں متغیر دکھایا تھا، اور 1992 میں شائع ہونے والے کاغذات کے سلسلے میں جیمز رینیگر نے اسے واحد متغیر انحصار میں بہتر بنایا۔ اس دوران، 1988 میں، جان کینی نے ایک اور الگورتھم بیان کیا جس میں وقت کا متغیر انحصار بھی ہے، لیکن صرف کثیر الجہتی خلائی پیچیدگی ہے۔ یعنی، اس نے دکھایا کہ مسئلہ کو پی ایس پی اے سی ای میں حل کیا جاسکتا ہے۔ ان الگورتھم کی ایسمپٹوٹک کمپیوٹیشنل پیچیدگی گمراہ کن ہو سکتی ہے، کیونکہ عملی طور پر انہیں صرف بہت چھوٹے سائز کے ان پٹ پر چلایا جا سکتا ہے۔ 1991 کے موازنہ میں، ہون ہانگ نے اندازہ لگایا کہ کولنز کا دوگنا ایکسپونینشل طریقہ کار ایک ایسے مسئلے کو حل کرنے کے قابل ہو گا جس کے سائز کو ایک سیکنڈ سے بھی کم وقت میں مذکورہ بالا تمام پیرامیٹرز کو 2 پر ترتیب دے کر بیان کیا گیا ہے، جبکہ گریگوریف، وربجوف اور رینیگر کے الگورتھم میں اس کے بجائے دس لاکھ سال سے زیادہ کا وقت لگے گا۔ 1993 میں، جوس، رائے اور سولرنو نے تجویز پیش کی کہ ایکسپونینشل ٹائم کے طریقہ کار میں چھوٹی تبدیلیاں کرنا ممکن ہونا چاہیے تاکہ انہیں عملی طور پر سلنڈریکل الجبرائی فیصلے کے ساتھ ساتھ نظریہ میں بھی تیز تر بنایا جا سکے۔ تاہم، 2009 تک، یہ اب بھی معاملہ تھا کہ حقیقی کے فرسٹ آرڈر تھیوری کے لیے عمومی طریقے عملی طور پر حقیقی کے وجودی نظریہ کے لیے مخصوص واحد ایکسپونینشل الگورتھم سے بہتر رہے۔ مکمل مسائل کمپیوٹیشنل پیچیدگی اور ہندسی گراف تھیوری میں متعدد مسائل کو حقیقی کے وجودی نظریہ کے لیے مکمل کے طور پر درجہ بند کیا جا سکتا ہے۔ یعنی، حقیقی کے وجودی نظریہ میں ہر مسئلے میں ان مسائل میں سے کسی ایک کی مثال کے لیے کثیر الجہتی-کئی-ایک کمی ہوتی ہے، اور اس کے نتیجے میں یہ مسائل حقیقی کے وجودی نظریہ کے لیے قابل تخفیف ہوتے ہیں۔ اس قسم کے متعدد مسائل ایک مخصوص قسم کے انٹرسیکشن گراف کی شناخت سے متعلق ہیں۔ ان مسائل میں، ان پٹ ایک غیر ہدایت شدہ گراف ہے ؛ مقصد یہ طے کرنا ہے کہ آیا شکلوں کی ایک مخصوص کلاس سے ہندسی شکلیں گراف کے عمودی حصوں کے ساتھ اس طرح سے منسلک کی جا سکتی ہیں کہ گراف میں دو عمودی حصے ملحقہ ہوں اگر اور صرف اس صورت میں جب ان سے وابستہ شکلوں کا غیر خالی چوراہا ہو۔ اس قسم کے مسائل جو حقیقت کے وجودی نظریہ کے لیے مکمل ہیں ان میں طیارہ میں لکیر کے حصوں کے انٹرسیکشن گراف کی شناخت، یونٹ ڈسک گراف کی شناخت، اور طیارہ میں کنویکس سیٹوں کے انٹرسیکشن گراف کی شناخت شامل ہیں۔ کراسنگ کے بغیر طیارہ میں تیار کردہ گرافوں کے لیے، فیری کا نظریہ بیان کرتا ہے کہ کسی کو پلانر گراف کی ایک ہی کلاس ملتی ہے اس سے قطع نظر کہ آیا گراف کے کناروں کو سیدھی لکیر کے حصوں کے طور پر کھینچا گیا ہے یا من مانی منحنی خطوط کے طور پر۔ لیکن یہ مساوات دیگر اقسام کی ڈرائنگ کے لیے درست نہیں ہے۔ مثال کے طور پر، اگرچہ گراف کی کراسنگ نمبر (من مانی مڑے ہوئے کناروں کے ساتھ ڈرائنگ میں کراسنگ کی کم از کم تعداد) کا تعین این پی میں کیا جا سکتا ہے، لیکن حقیقی کے وجودی نظریہ کے لیے یہ طے کرنا مکمل ہے کہ آیا کوئی ڈرائنگ موجود ہے جو ریکٹلینیر کراسنگ نمبر پر دی گئی حد کو حاصل کرتی ہے (کناروں کے جوڑوں کی کم از کم تعداد جو کسی بھی ڈرائنگ میں کراس کرتی ہے جس کے کناروں کو ہوائی جہاز میں سیدھی لکیر کے حصوں کے طور پر کھینچا جاتا ہے)۔ حقیقی کے وجودی نظریہ کے لیے یہ جانچنا بھی مکمل ہے کہ آیا ایک دیا ہوا گراف سیدھی لکیر کے کناروں کے ساتھ اور کنارے کے جوڑوں کے دیئے گئے سیٹ کے ساتھ اس کے کراسنگ کے طور پر کھینچا جا سکتا ہے، یا مساوی طور پر، کیا کراسنگ کے ساتھ مڑے ہوئے ڈرائنگ کو اس طرح سے سیدھا کیا جا سکتا ہے جس سے اس کی کراسنگ کو محفوظ رکھا جا سکے۔ حقیقی وجود کے نظریہ کے لیے دیگر مکمل مسائل میں شامل ہیں: پوائنٹس کی سب سے چھوٹی تعداد کو تلاش کرنے کا آرٹ گیلری کا مسئلہ جس سے کسی دیئے گئے کثیر الاضحی کے تمام نکات نظر آتے ہیں۔ نیورل نیٹ ورکس کی تربیت۔ پیکنگ کا مسئلہ یہ فیصلہ کرنے کا ہے کہ آیا کثیر الاضحی کا دیا ہوا سیٹ دیئے گئے مربع کنٹینر میں فٹ ہو سکتا ہے۔ یونٹ ڈسٹنس گراف کی شناخت، اور یہ جانچنا کہ آیا گراف کا طول و عرض یا یوکلڈین طول و عرض زیادہ سے زیادہ ایک دی گئی قیمت ہے۔ سڈوولینز کی پھیلاؤ (یعنی، ہوائی جہاز میں منحنی خطوط کے ایک خاندان کو دیکھتے ہوئے، اس بات کا تعین کرتے ہوئے کہ آیا وہ لائن کے انتظام کے لیے ہومومورفک ہیں) ؛ کسی بھی مقررہ طول و عرض> 2 میں ہندسی کوانٹم منطق کی کمزور اور مضبوط اطمینان بخش دونوں ؛ غیر واضح آٹومیٹا کے حوالے سے ماڈل چیکنگ وقفہ مارکوف زنجیر۔ الگورتھمک اسٹینٹز مسئلہ (ایک جالی دی گئی ہے، اس بات کا تعین کریں کہ آیا یہ ایک کنویکس پولیٹوپ کا چہرہ جالی ہے)، یہاں تک کہ جب 4 جہتی پولی ٹاپس تک محدود ہے۔ بعض کنویکس باڈیز کے انتظامات کی وصولی خالی جگہیں کثیر کھلاڑی کھیلوں کے نیش توازن کی مختلف خصوصیات کو تین جہتی یوکلڈین اسپیس میں مثلث اور چوطرفہ کے دیئے گئے تجریدی کمپلیکس کو سرایت کرتی ہیں۔ ہوائی جہاز میں مشترکہ ورٹیکس سیٹ پر متعدد گرافوں کو سرایت کرنا تاکہ تمام گراف بغیر کراسنگ کے تیار کیے جائیں۔ پلانر پوائنٹ سیٹوں کے مرئیت گرافوں کو پہچاننا ؛ (پروجیکٹو یا غیر معمولی تعلق) کراس پروڈکٹ پر دو اصطلاحات کے درمیان مساوات کی اطمینان بخشیت ؛ کم از کم ڈھلوان نمبر کا تعین کرنا۔ کم درجہ میٹرکس کی تکمیل کا مسئلہ۔ اس کی بنیاد پر، پیچیدگی کی کلاس کو مسائل کے اس مجموعے کے طور پر بیان کیا گیا ہے جس میں حقیقی کے وجودی نظریہ میں کثیر الجہتی-کئی بار-ایک کمی ہوتی ہے۔ ہلبرٹ کا دسواں مسئلہ بھی دیکھیں، انٹیجرز کے (ناقابل فیصلہ) وجودی نظریہ پر حوالہ جات ریاضیاتی کمپیوٹیشنل پیچیدگی کے رسمی نظریات حقیقی الجبرائی جیومیٹری