Antworte auf:  n^2+1 nicht Produkt von Funktionen aus O(n)? von sonnenschein96
Forum:  Komplexitätstheorie, moderiert von: Bilbo

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1037
Herkunft:
 Beitrag No.7, eingetragen 2020-09-19 20:51    [Diesen Beitrag zitieren]

Sieht gut aus!


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 218
Herkunft:
 Beitrag No.6, eingetragen 2020-09-19 20:42    [Diesen Beitrag zitieren]

Hallo Kezer,

das ist glaube ich genau das was ich gesucht habe, vielen Dank :)

Mein Beweis sähe dann wie folgt aus:

Sei \(A\) die Menge aller \(n\in\mathbb{N}\), sodass \(n^2+1\) einen Primfaktor \(p_n\) größer als \(n\log(n)\) hat. Nach dem Link den Du angegeben hast enthält \(A\) unendlich viele Elemente. (Die Beweise schaue ich mir später an. Ich würde diese auch nicht gerade als offensichtlich bezeichnen :P)

Es seien nun \(f,g\colon\mathbb{N}\to\mathbb{N}\) mit \(n^2+1=f(n)g(n)\) für alle \(n\in\mathbb{N}\). Für jedes \(n\in A\) muss \(p_n\) dann als Primfaktor in \(f(n)\) oder \(g(n)\) vorkommen, d.h. \(f(n)>n\log(n)\) oder \(g(n)>n\log(n)\).

Sei \(A_f\) (\(A_g\)) die Menge aller \(n\in\mathbb{N}\) mit \(f(n)>n\log(n)\) (\(g(n)>n\log(n)\)). Es gilt dann \(A\subseteq A_f\cup A_g\) und da \(A\) unendlich ist, muss mindestens eine der Mengen \(A_f,A_g\) unendlich sein.

Sagen wir \(A_f\) ist unendlich (für \(A_g\) analog). Angenommen \(f\in\mathcal{O}(n)\). Dann gäbe es \(c,n_0\in\mathbb{N}\) mit \(f(n)\leq cn\) für alle \(n\geq n_0\) und es würde \(n\log(n)<f(n)\leq cn\), also \(\log(n)<c\), für alle \(n\in A_f\) mit \(n\geq n_0\) folgen. Dies widerspricht der Unendlichkeit von \(A_f\). Damit ist \(f\notin\mathcal{O}(n)\).

Für den Fall, dass \(A_g\) unendlich ist, folgt \(g\notin\mathcal{O}(n)\). Auf jeden Fall kann nicht \(f\in\mathcal{O}(n)\) und \(g\in\mathcal{O}(n)\) gelten.


Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1037
Herkunft:
 Beitrag No.5, eingetragen 2020-09-19 19:55    [Diesen Beitrag zitieren]

Dein Vorschlag würde funktionieren, schaue mal hier: MSE/589344. Als offensichtlich würde ich das allerdings nicht bezeichnen :-p



Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 192
Herkunft:
 Beitrag No.4, eingetragen 2020-09-19 19:27    [Diesen Beitrag zitieren]

Ihr habt natürlich völlig recht, da habe ich zu schnell reagiert...


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 218
Herkunft:
 Beitrag No.3, eingetragen 2020-09-19 19:00    [Diesen Beitrag zitieren]

Hallo Ixx,

wir haben \(\mathcal{O}(n)\) definiert als die Menge aller Funktionen \(f\colon\mathbb{N}\to\mathbb{N}\) für dies es \(c,n_0\in\mathbb{N}\) gibt mit \(f(n)\leq cn\) für alle \(n\geq n_0\).

Würde \(\mathcal{O}(n)\) nur lineare Funktionen enthalten, wäre die Frage viel einfacher zu beantworten.

\(\mathcal{O}(n)\) enthält aber viele Funktionen, die sehr kompliziert sein können (wie Nuramon ja schon angedeutet hat), da sie sich von Punkt zu Punkt sehr unterschiedlich verhalten können, solange sie nur nach oben linear beschränkt sind.

Daher meinte ich ja auch, dass man für \(n\in\mathbb{N}\) die Primfaktoren von \(n^2+1\) jeweils auf \(f(n)\) und \(g(n)\) aufteilen kann, was eben zu sehr komplizierten \(f\) und \(g\) führen kann.


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2411
Herkunft:
 Beitrag No.2, eingetragen 2020-09-19 18:43    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
@Ixx: $\mathcal O(n)$ enthält auch nichtlineare Funktionen $\IN\to \IN$. Z.B. $n\mapsto n+(-1)^n$.
\(\endgroup\)

Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 192
Herkunft:
 Beitrag No.1, eingetragen 2020-09-19 18:37    [Diesen Beitrag zitieren]

Wegen $f,g\in\mathcal{O}(n)$ müssen beide linear sein. Seien $x_f, x_g \in \mathbb{Q}$ die Nullstellen von $f,g$. Dann wären es auch Nullstellen von $x^2+1$, Widerspruch.


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 218
Herkunft:
 Themenstart: 2020-09-19 17:00    [Diesen Beitrag zitieren]

Hallo Leute,

in einer meiner Informatik-Übungen wurde einmal behauptet, dass es "offensichtlich" keine Funktionen \(f,g\in\mathcal{O}(n)\) gibt, sodass \(n^2+1=f(n)g(n)\) für alle \(n\in\mathbb{N}\). Dies wurde aber natürlich nicht begründet...

Ich finde es ehrlich gesagt nicht so offensichtlich, ob die Aussage überhaupt wahr ist.

Meine Überlegungen dazu: Für festes \(n\in\mathbb{N}\) kann man anhand der Primfaktorzerlegung von \(n^2+1\) erkennen, wie viele Möglichkeiten es gibt \(n^2+1\) in zwei Faktoren aufzuspalten.

Damit sieht man leicht, dass es unendlich viele Möglichkeiten gibt, Funktionen \(f,g\colon\mathbb{N}\to\mathbb{N}\) zu finden, sodass \(n^2+1=f(n)g(n)\) für alle \(n\in\mathbb{N}\).

Die Frage ist nun, ob stets \(f\notin\mathcal{O}(n)\) oder \(g\notin\mathcal{O}(n)\).

Wüssten wir, dass \(n^2+1\) für unendlich viele \(n\in\mathbb{N}\) prim ist, so müsste \(f(n)=n^2+1\) für unendlich viele \(n\in\mathbb{N}\) oder \(g(n)=n^2+1\) für unendlich viele \(n\in\mathbb{N}\) und wir wären fertig.

Ich habe jedoch festgestellt, dass dies anscheinend eines der Landau-Probleme ist, welche bis heute ungelöst sind.

Die Frage ist daher, ob es eine elementarere Begründung für die zu zeigende Aussage gibt?

Ich könnte mir vorstellen, dass \(n^2+1\) für unendlich viele \(n\in\mathbb{N}\) zumindest große Primfaktoren enthält, sodass stets mindestens eine der beiden Funktionen nicht in \(\mathcal{O}(n)\) liegen kann.

Viele Grüße
sonnenschein96


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]