هل هناك خوارزمية زمنية متعددة الحدود لمشكلة هذه القرار؟

Question

هل هناك عامل في $ m $ هذا $> $ $ 1 $ ، ولكن $ <$ $ m $ هذا ليس عامل $ n $ ؟

النتيجة الخاطئة مثال

$ n $ = 8

$ m $ = 16

1، 2، 4، 8، 16

لا يوجد عدد صحيح ليس عاملا من $ n $ هذا $> $ < Span Class="حاوية الرياضيات"> $ 1 $ ولكن << span class="حاوية الرياضيات"> $ m $

<قوية> مثال حقيقي

$ n $ = 2

$ m $ = 26

1، 2، 13، 26

هناك عدد صحيح 13 دولارا $ وهو ليس عامل $ n $ هذا هو> 1 ولكن < $ M $

السؤال

لقد وجدت حل متعدد الحدود الزائفة، ولكن هل هناك حل متعدد الحدود لهذه المشكلة في طول المدخلات؟

Answer 1

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