الخوارزميات التي تعمل في وقت متعدد الحدود إذا P= NP

Question

href="https://en.wikipedia.org/wiki/p_versus_np_problem#polynomial-time_algorithms" rel="noreferrer"> على Wikipedia ، تقول أن هناك بعض الخوارزميات التي من شأنها تشغيلفي الوقت متعدد الحدود إذا وفقط إذا P= NP.أعطوا مثالا واحدا (بدون استشهاد)، ولكن هل هناك أي الآخرين؟حاولت البحث عنها ولم أتمكن من العثور على أي.

Answer 1

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