حجة في إثبات أن الوظيفة ليست وقت متعدد الحدود في طول الإدخال يبدو خلل

Question

أنا حاليا حل سؤال يسأل أي من الوظائف التالية يمكن حسابها في وقت متعدد الحدود:

$$ ن!، \ binom {5} {5}، \ binom {n}، n {\ lfloor \ lg n \ rfloor}، \ lloor\ SQRT {n} \ rfloor، \ text {أصغر عامل رئيس الوزراء} n، \ text {عدد العوامل الرئيسية أقل من} N.

في إثبات أول واحد، اعتقدت $ n!\ GEQ N $ وحجم الإدخال هو $ \ log_2 n $ لذلك لا يمكن كتابة الإخراج في وقت متعدد الحدود.لذلك من الواضح أنه لا يمكن إجراء الحساب في وقت متعدد الحدود.

ولكن بعد ذلك اعتقدت أنه يجب أن يكون لدي بعض سوء الفهم، لأنه من خلال هذا المنطق فقط حساب $ N $ من المدخلات (أي وظيفة الهوية) لا ينبغيأن تكون الوقت متعدد الحدود.لكن هذا بوضوح غير ممكن.

ما هي المشكلة في تفكيري، وبدلا من ذلك كيف ينبغي أن أفكر في هذه؟

Answer 1

يجب عليك قياس طول الإخراج بنفس طريقة قياس طول الإدخال.

على سبيل المثال، عند الحوسبة وظيفة الهوية $ f (m)= m $ ، إدخال $ m $ لديه طول الإدخال $ n=theta (\ log m) $ وطول الإخراج أيضا $ n $ ، وهو متعدد الحدود في $ n $ .

وظيفة العاصمة، على النقيض من طول الإنتاج طويل جدا.في الواقع، إذا كانت الإدخال $ n $ ، ثم عن طريق صيغة Stirling، طول الإخراج هو $ \ theta (n\ Log n) $ ، والذي هو الأسي في طول الإدخال $ \ theta (\ log n) $ .