مسألة كثير حدود وكثير حدود غير قطعي: الفرق بين النسختين

إن العلاقة بين '''مسائل ال[[تعقيد]] [[كثير حدود (تعقيد)|كثيرة الحدود]] و[[مسألة كثيرة حدود غير قطعية كاملة|كثير حدود غير قطعي]]''' هي مسألة غير محلولة في [[علم الحاسوب النظري|المعلوماتية النظرية]].<ref name=":0">{{مرجع ويب|مؤلف=[[John Markoff]] |مسار=https://www.nytimes.com/2009/10/08/science/Wpolynom.html |عنوان=Prizes Aside, the P-NP Puzzler Has Consequences|عمل=The New York Times|تاريخ=8 October 2009| مسار أرشيف = https://web.archive.org/web/20180623062841/https://www.nytimes.com/2009/10/08/science/Wpolynom.html | تاريخ أرشيف = 23 يونيو 2018 }}</ref><ref>[http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].</ref><ref>{{مرجع ويب |عنوان=NP-completeness of Sudoku |مسار=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html| مسار أرشيف = https://web.archive.org/web/20171117002021/http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html | تاريخ أرشيف = 17 نوفمبر 2017 }}</ref> وهي تعتبر من أهم المسائل في هذا الحقل وقد عرض [[معهد كلاي للرياضيات]] جائزة مقدارها مليون دولار أمريكي لأول برهان صحيح لهذه المسألة.

المسالة P =ضد NP هي تحديد اذا ما كل مسألة [[خوارزمية|يمكن]]<ref name=":0" /> تقريرها بواسطة خوارزمية غير قطعية يمكن أيضا حلها بواسطة خوارزمية قطعية . حتى نستطيع تعريف المسألة بشكل دقيق يجب علينا تحديد نموذج حاسوبي . النموذج الأساسي للحاسوب في النظرية الحاسوبية هي [[الة تورنغ]] والتي عرفها [[آلان تورنغ]] عام 1936 و بالرغم من أن هذا النموذج ظهر قبل الحاسوب الذي نعرفه الٱن لكنه أنموذج مقبول نظر لأساسيته الهادفة و الثابتة الهدف أجلا و أملا في تعريف المصطلح كدالة قابلة للحساب .