هل هذه مشكلة "تعبير رياضي صالح" P أو NP؟

Question

هذا السؤال هو البحتة بدافع الفضول. أنا خارج المدرسة للصيف، وسوف ينفذ خوارزمية لحل هذا فقط للمتعة. التي أدت إلى السؤال أعلاه، ما مدى صعوبة هذه المشكلة؟

المشكلة: تحصل على قائمة بالأعداد الصحيحة الموجبة، مجموعة من المشغلين الرياضيات والعلامة المتساوية (=). هل يمكنك إنشاء تعبير رياضي صالح باستخدام الأعداد الصحيحة (بنفس الترتيب) والمشغلين (أي عدد من المرات)؟

يجب أن يوضح المثال أي أسئلة:

نظرا: {2، 3، 5، 25}، {+، -، *، /}، {=}
الإخراج: نعم

التعبير (واحد فقط أعتقد) هو (2 + 3) * 5 = 25. تحتاج فقط إلى إخراج نعم / لا.

أعتقد أن المشكلة في NP. أقول هذا لأنه مشكلة في القرار (نعم / لا إجابة) ويمكنني أن أجد خوارزمية زمنية غير محددة التي تقرر ذلك.

أ. اختيار غير محدد سلسلة من المشغلين لوضعهم بين الأعداد الصحيحة.
ب. تحقق من الإجابة هو تعبير رياضي صالح (يمكن القيام بذلك في وقت ثابت).

في هذه الحالة، السؤال الكبير هو: هل المشكلة في ص؟ (أي هل هناك خوارزمية وقت بولي محددة تقرر ذلك؟) أو هي المشكلة NP كاملة؟ (أي هل يمكن تخفيض مشكلة NP كاملة معروفة إلى هذا؟ أو ما يتساوي عنها هي كل وقت غير قابل للتخصص في هذه المشكلة؟) أو لا؟ (أي المشكلة في NP ولكن ليس NP كاملة)

ملاحظة: يفترض بيان المشكلة هذه P لا يساوي NP. أيضا، على الرغم من أنني جديد لتجاوز المكدس، فإنني على دراية بالعلامة المنزلية. هذا هو في الواقع فضول فقط، وليس الواجبات المنزلية :)

Answer 1

تخفيض مباشر من مشكلة التقسيم (هذا هو NP-Complete) - نظرا لمجموعة من الأعداد الصحيحة N، فإن المدخلات إلى مشكلة "الرياضيات الصالحة للرياضيات" ستكون - عناصر المشغلين S و N-2 '+' علامة "=".

Answer 2

يبدو أن هناك نوعا من الارتباك حول كيفية التحقق من اكتمال NP. مشكلة NP-Complete هي على الأقل بجد، بمعنى معين، مثل أي مشكلة أخرى في NP. لنفترض أننا كنا نقارن 3SAT، لأن بعض الملصقات تحاول القيام به.

الآن، تقليل المشكلة المعينة إلى 3SAT لا يثبت شيئا. ثم صحيح أنه إذا كان يمكن حل 3SAT بكفاءة (معنى P = NP)، يمكن حل المشكلة المعينة بكفاءة. ومع ذلك، إذا كانت المشكلة المعينة يمكن حلها بكفاءة، فربما يتوافق إلا إلى حالات خاصة سهلة من 3SAT.

علينا أن تقلل 3SAT إلى مشكلة معينة. هذا يعني أن علينا أن نتعامل مع قاعدة لتحويل مشاكل 3SAT التعسفي إلى أمثلة للمشكلة المعينة، بحيث يخبرنا حل المشكلة المعينة إلى كيفية حل مشكلة 3SAT. هذا يعني أن 3SAT لا يمكن أن يكون أصعب من مشكلة معينة. منذ 3SAT هي الأصعب، يجب أن تكون المشكلة المعينة هي الأصعب أيضا.

تخفيض مشكلة القسم يعمل. تعمل هذه المشكلة مثل هذا: نظرا لإحضار عدد صحيح من الأعداد الصحيحة، هل يمكننا تقسيم هذا إلى مجموعة فرعية مفككة بينهما بينهما يشمل كل عضو من أعضاء S، بحيث تكون مبالغ المجموعات الفرعية المفاجئة مساوية؟

للقيام بذلك، نبني تسلسل يبدأ ب 0، يحتوي على كل عنصر من عناصر S، ثم 0. نستخدم {+، -} كقاعدة عملية. وهذا يعني أنه سيتم إضافة أو طرح كل عنصر من عناصر S أو طرحه إلى المجموع إلى 0، مما يعني أن مجموع العناصر المضافة هو نفس مجموع العناصر المطردة.

لذلك، فإن هذه المشكلة هي على الأقل بجد مشكلة القسم، حيث يمكننا حل برنامج قسم مثال إذا استطعنا حل واحد معين، وبالتالي فإن NP-Complete.

Answer 3

انقر أولا، أولا، تحدد "تعيين" من الأعداد الصحيحة ولكن المجموعة بحكم تعريفها غير مرتبة، لذلك تقصد "قائمة" الأعداد الصحيحة.

أيضا، سأقدم افتراضا هنا الذي قد يكون خطأ، وهو أن علامة = تظهر دائما مرة واحدة بالضبط مرة واحدة، بين الثانية إلى الماضي والأعيد الصحيح الأخير في قائمتك. إذا سمحت بتساوي تسجيل الدخول في الوسط، يصبح أكثر تعقيدا.

فيما يلي دليل فعلي على أن "تعبير رياضي صالح" (VME) هو NP Complete. يمكننا أن نفعل تخفيض من مجموع مجموعة فرعية. وبعد لاحظ أن تعريف Wikipedia للمبلغ الفرعي يتطلب مجموعة فرعية غير فارغة. في الواقع، صحيح أن المشكلة العامة للمجموعة الفرعية التي تسمح بدقة فرعية فارغة كاملة، إذا كان المبلغ المطلوب هو أيضا جزء من الإدخال. لن أعطي هذا الدليل إلا إذا طلب ذلك. بالنظر إلى مثيل مجموع الفرعي {i_1, i_2, ..., i_n} جنبا إلى جنب مع المبلغ المطلوب s, ، قم بإنشاء مثيل VME التالي:

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

إذا كان مثيل المجموع الفرعي قابل للحل، فهناك مجموعة فرعية من الأعداد الصحيحة التي تضيف إلى 0. إذا كان عدد صحيح i1 هو جزء من المبلغ، أضفه مع الصفر المقابل (على الفور إلى اليسار) وإذا i1 ليس جزءا من المجموع، مضاعفة ذلك. بين كل صفر ومصطلح إلى اليمين، أدخل علامة الإضافة.

أخذ مثال ويكيبيديا

{−7, −3, −2, 5, 8}

أين { −3, −2, 5} المبالغ إلى 0، ونحن سوف تشفصها كما

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

والتعبير الناتج سيكون

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

الآن نحتاج أيضا إلى إظهار أن أي حل لهذا مثيل VME ينتج عنه حل لمثيل مجموعة فرعية. هذا أسهل مما تعتقد. عندما ننظر إلى تعبير ناتج، يمكننا تجميع الأرقام في تلك التي تضاعفت مع 0 (بما في ذلك كجزء من الضرب السلسلة) وأولئك الذين ليسوا كذلك. لا يتم تضمين أي عدد مضروب مع صفر في المبلغ النهائي. يجب إضافة أي عدد غير مضروب مع صفر إلى المبلغ النهائي.

لذلك أظهرنا أن مثيل VME هذا قابل للحل إذا وفقط إذا كان المثال المقابل للمجموع الفرعي قابل للحل، لذلك اكتمال التخفيض.

تعديل: يعمل تخفيض التقسيم (مع التعليق) كذلك، وهو أفضل لأنه يسمح لك بوضع علامة التساوي في أي مكان. مرتب!

Answer 4

لم يكن لديك الوقت للحصول على الإجابة الكاملة الآن، ولكن يمكنك وصف تخفيض من هذه المشكلة إلى مشكلة napsack.

باستخدام البرمجة الديناميكية التي يمكنك تحقيقها pseudo- متعدد الحدود الحل الزمني. لاحظ أن هذا لا تعارض مع حقيقة أن المشكلة هي في الواقع NP كاملة.

Answer 5

هناك خصائص يجب أن تكون راضيا عنها لتكون NP كاملة.

مشكلة القرار C هي NP كاملة إذا:

1. ج في NP، و
2. كل مشكلة في NP متوفرة ل C في الوقت متعدد الحدود.

لقد أنشأنا 1. 2 نتائج من حقيقة أن كل مشكلة في NP متوقفة إلى 3SAT و 3SAT لا تقلل من المشكلة الحالية.

لذلك هو np-complete.

(تحرير) الإجابة على التعليق أدناه:

سأثبت أن SAT متوقل للمشكلة الحالية، ومنذ 3SAT غير متوقل إلى SAT، فإن النتيجة التالية.

صيغة الإدخال هي بالتزامن بين التعبيرات التالية:

(X.₁ الخامس عشر₂ الخامس عشر₃ الخامس ... X._ن الخامس ص₁)

(X.₁ الخامس عشر₂ الخامس عشر₃ الخامس ... X._ن الخامس ص₂)

(X.₁ الخامس عشر₂ الخامس عشر₃ الخامس ... X._ن الخامس ص₃)

.

.

.

(X.₁ الخامس عشر₂ الخامس عشر₃ الخامس ... X._ن الخامس ص₆₄)

حيث كل Y._أنا هو منطقية بناء على ما ينطبق ترتيب المشغلين بين كل X_أناهو هو. أي، Y._أنا يمكن أن تتخذ ما مجموعه قيم 4x4x4x4x1 (على افتراض أن فقط +، -، X، / هي المشغلين = هو دائما المشغل الأخير؛ يمكن تغيير هذا إذا تم تعديل مجموعة المشغل لتضمين مشغلين آخرين)

إذا كان أي من التعبيرات صحيحة، فسيقوم التعبير الكامل بتقييمه إلى FALSE، ولا توجد وسيلة للتحقق ما لم نسيل كل القيم الممكنة، أي X₁ من خلال X._ن كما الأرقام n و y₁ من خلال Y.₆₄ كما الطرق المختلفة التي يمكن بها تطبيق المشغلين (هذا يعتني بالطلب)

هذا التحويل في بولي وقت، والصيغة المنطقية المحددة مرضية IFF التعبير الرياضي صالح، إلخ.

أي شخص لاحظ عيب؟

Answer 6

هذه ليست إجابة حقا لسؤالك التعقيد، ولكن مشكلتك تبدو مثل العد التنازلي مشكلة. تبحث البحث السريع هذه الورقة: http://www.cs.nott.ac.uk/~gmh/countdown.pdf.

Answer 7

ليس لدي وقت للعمل دليلا في الوقت الحالي، لكن الهنبة تخبرني أنه قد لا يكون في P. يمكنك تحديد قواعد قواعدية للحساب، ثم يبلغ هذا السؤال لإيجاد ما إذا كان هناك شجرة تحليل صالحة يستخدم كل هذه المحطات. أنا يصدق أن هذه المشكلة في NP ولكن خارج P.