In beiden Algorithmen Ich habe mit gearbeitet, verwende ich die zwei Funktionen:Kann die Primzahlfunktion und das Produkt von aufeinanderfolgenden Primzahlen in Polynomialzeit berechnet werden?
- pi (n): = Anzahl der Primzahlen < = n und
- R (n): = r, wo prod (p_i, i = 1, r) = n < aber n < prod (p_i, i = 1, r + 1), wop_i den i-te Primzahl ist.
Grundsätzlich pi (n) ist die berühmte prime-Zählfunktion, und R (n) berechnet, nur das Produkt der aufeinanderfolgenden Primzahlen bis Sie die gebundenen n und geben die Menge von Primzahlen verwendet, zu erreichen, so zum Beispiel:
R (12) = 2, da 2 * 3 < = 12, aber 2 * 3 * 5> 12 und beispielsweise
R (100) = 3, weil 2 * 3 * 5 < = 100 aber 2 * 3 * 5 * 7> 100.
Mit meinem Professor haben wir über die Laufzeit der Berechnung dieser Funktionen gesprochen. Ich weiß, dass das pi (n), dass es in etwa x/ln (x) im Laufe der Zeit, aber ich habe meine Zweifel über einige Sachen:
- Kann R (n) in Polynomialzeit berechnet werden? Aus meiner Sicht können wir mit dynamischer Programmierung die Produkte 2 * 3 * 5 * ... * p_i berechnen, indem wir 2 * 3 * 5 * ... * p_ (i-1) kennen, also reduziert sich das Problem auf bekomme die nächste Primzahl, die, soweit ich weiß, in polynomieller Zeit berechnet werden kann (PRIMES ist in P).
- Auch weil wir wissen, dass wir bestimmen können, ob eine Zahl in Polynomialzeit Primzahl ist, sollte das nicht heißen, dass Pi (n) in Polynomialzeit berechnet werden kann? (Auch dynamische Programmierung kann hilfreich sein).
Wenn mir jemand helfen kann, diese Fragen zu klären oder mich auf die richtige Richtung zu weisen, würde ich es wirklich schätzen! Vielen Dank!
Wenn Sie Polynom sagen, meinen Sie Polynom in der Zahl n, oder in der Anzahl der Bits, die es braucht, um n darzustellen?Für Dinge wie Factoring meinen wir normalerweise die Anzahl der Bits, was viel schwieriger ist. Meine Erwartung wäre, dass R (n) Polynom in der Größe der Repräsentation von n ist, während phi (n) etwas wie O (sqrt (n)) sein wird. – btilly