يجب أن تتكمل مشكلة القرار في $ NP $ استكمالا في $ CO-NP $، إذا استطعت التحقق من الحلول في كثير من الأحيان في الوقت؟

Question

تخمين جولدباخ يقول كل عدد صحيح $> $ يمكن التعبير عن $ 2 $ .الأعداد الأولية.

دعنا نقول $ n $ هو مدخلاتنا و $ 10 $ .وهو عدد صحيح> 2 وليس غريبا.

خوارزمية

1. الإبداع قائمة بالأرقام من $ 1، إلى ~ n $

2. استخدام خوارزمية الاختبار الأولية لإنشاء قائمة ثانية من الأرقام الرئيسية

3. استخدام الحلال الخاص بي 2_sum الذي يسمح لك باستخدام الأعداد الأولية مرتين تلاشى إلى $ n $

giveacodicetagpre.

4.Verify محلول فعال

giveacodicetagpre.

5.UtPut

giveacodicetagpre.

السؤال

إذا كان التخمين صحيحا، فستكون الإجابة دائما نعم.هل هذا يعني أنه لا يمكن أن يكون في $ CO-NP $ لأن الإجابة هي دائما نعم؟

Answer 1

أعتقد أنك قد تكون مربكة بضعة أشياء.

أولا، تكملة أي مشكلة في NP في CONP بالتعريف. لا توجد شروط أخرى مطلوبة. ثانيا، اعتراف خوارزمية وقت متعدد الحدود للتحقق من الحلول، والانتماء إلى فئة NP، هي عبارات مكافئة.

الثالث، تخمين Goldbach هو عبارة رياضية، والتي تحت البديهيات القياسية هي إما صحيحة أو خاطئة. وهذا يعني أنه كملالة قرارات، بنفس الرسم من أي بيان رياضي آخر، فإن تخمين Goldbach لديه حل زمني ثابت: جهاز إجابات "True"، الجهاز B يجيب "False". بالضرورة واحدة منهم على حق، وكلاهما يأخذ وقتا ثابتا. من الواضح أن هذا غير مفيد على الإطلاق.

لذلك ربما تهدف إلى طرح المشكلة التي تعطى حتى عدد صحيح n> 2 يطلب منك أن تقرر ما إذا كان يمكن التعبير عنها كمبلغ من الأعداد الأولية. هذه المشكلة هي بالفعل في NP كما قلت، لأنه إذا كان n= p + q for primes p، q. ثم $ \ اليسرى $ هو حلا يمكن التحقق منها في وقت متعدد الحدود، باستخدام خوارزمية بولي وقت للتحقق من ذلك س هي في الواقع الأعداد الأولية، ثم أي خوارزمية إضافة. لا أعرف إذا كانت هناك خوارزمية زمنية متعددة الحدود لهذه المشكلة، لكنني لن أتفاجأ إذا كان هناك واحد.

إذا كان تخمين Goldbach صحيحا، فإن الجهاز الذي يجيب "نعم" دون النظر إلى الإدخال يقبل اللغة الموضحة أعلاه وتشغيلها في وقت ثابت.