البديل فرعية-مجموع يحتوي $O(1)$ خوارزمية إذا $Goldbach$ صحيح

Question

نظرا $S$ من الاعداد الصحيحه الايجابية $>$ $1$ هل هناك تركيبة مع حتى $مبلغ$ > $2$ هذا هو لا مجموع اثنين يعبي?

$مبلغ$ = 10

$S$ = $[4,6]$

$لا$,

مبلغ اثنين من يعبي $5 + 5 = 10$.

مزيج $4+6=10$

فقد $O(1)$ خوارزمية إذا Goldbach صحيح (الناتج دائما $لا$).وإلا فإنه يبدو أن يكون NP-complete لأنه يتطلب حل فرعية-المبلغ.

السؤال

سوف العديد من واحد-الحد من $فرعية-مبلغ$ العمل على هذا القرار مشكلة في بولي الوقت ؟

Answer 1

إذا كان هناك عدد محدود من الاستثناءات Goldbach الظن ثم أنها لا تزال قابلة للحل في الزمن الخطي.

علما أن هناك غير الصفر احتمال أن Goldbach التخمين غير صحيح.Heuristically ، واحتمال لعدد لا حصر له من الاستثناءات هي صفر.