Argument bei der Beweis, dass die Funktion keine Polynomzeit in der Bitlänge des Eingangs ist, scheint fehlerhaft zu sein

Question

Ich löse derzeit eine Frage, die fragt, welche der folgenden Funktionen in der Polynomzeit berechnet werden kann:

$$ N! \ Binom {n} {5}, \ Binom {2n} {n}, n ^ {\ lfloor \ lg n \ rfloor}, \ lfloor\ sqrt {n} \ rfloor, \ text {der kleinste Prime-Faktor von} n, \ text {die Anzahl der Hauptfaktoren weniger als} n. $$

Bei der Beweis der ersten, dachte ich $ n!\ geq n $ und die Eingabegröße ist $ \ log_2 n $ , so dass der Ausgang nicht einmal in der Polynomzeit geschrieben werden kann.Dann kann die Berechnung also nicht in der Polynomzeit erfolgen.

aber dann dachte ich, ich muss etwas Missverständnissen haben, da durch diese Logik sogar nur $ N $ von der Eingabe (dh der Identitätsfunktion) nicht berechnet werden solltePolynomzeit sein.Aber das ist eindeutig nicht möglich.

Was ist das Problem in meinem Denken, und wie sollte ich darüber nachdenken?

Answer 1

Sie sollten die Länge der Ausgabe auf dieselbe Weise messen, wie Sie die Länge des Eingangs messen.

Zum Beispiel beim Berechnen der Identitätsfunktion $ F (m)= M $ , eine Eingabe $ M $ hat eingegebene länge $ n=theta (\ log m) $ und -ausgangslänge auch $ n $ , das Polynom in $ n $ ist.

Die Fabrikfunktion hat dagegen eine viel zu lange Ausgangslänge.Wenn der Eingang $ N $ ist, dann ist die Länge des Ausgangs $ \ theta (N\ log n) $ , was in der Eingabelänge $ \ theta (\ log n) $ ist.