Gibt es einen Polynomzeitalgorithmus für dieses Entscheidungsproblem?
-
29-09-2020 - |
Frage
Gibt es einen Faktor in $ M $ das ist $> $ $ 1 $ , aber $ <$ $ M $ Das ist nicht ein Faktor von $ n $ ?
falsches Ergebnisbeispiel
$ n $ = 8
$ M $ = 16
1, 2, 4, 8, 16
Es gibt keine Ganzzahl, die nicht ein Faktor von $ N $ ist, der $> $
$ N $ = 2
$ M $ = 26
1, 2, 13, 26
Es gibt eine Ganzzahl $ 13 $ , die nicht ein Faktor von $ N $ das ist> 1 aber << span class="Math-Container"> $ M $
Frage
Ich habe eine Pseudo-Polynom-Lösung gefunden, gibt es jedoch eine Polynomlösung für dieses Problem in der Länge der Eingabe?
Lösung
Dies ist schwerwiegend wie das Integer-Factoring-Problem (einfach $ N $ auf 2 oder eine zufällige Prime, die keinen Faktor mit $ M $ ).Ob es einen Polynom-Zeit-Algorithmus zum Factoring gibt, ist ein berühmtes offenes Problem, aber es wird weit verbreitet, dass es wahrscheinlich keinen solchen Algorithmus gibt.