Veröffentlichung

[biter]

Also kommt seid nicht böse hier:

Sei M eine beliebige Menge, das können Zahlen, boolsche Werte, Buchstaben, oder irgendwelche komplexe Datenstrukuren sein.

InitG elementvon M, InitK elementvon M,
fg eine beliebige zweistellige Funktion: M x M --> M
fk eine beliebige zweistellige Funktion: M x M --> M
im folgendem Pseudocode:

function G(N): if N==1 then return InitG else return K(N-1) fg K(N-2) fg .... fg. K(1)
function K(N): if N==1 then return InitK else return G(N-1) fk G(N-2) fk .... fk. G(1)

function Expo(N) return G(N)

function iter1(N) if N==1 return InitG; if N==2 return InitK;
KIter=InitG; GIter=InitK; // Stimmt !
for(int i=3; i<=N; i++) { S=KIter; KIter=fk(GIter, KIter); GIter=fg(S, GIter); };
return GIter;

Behauptung: Expo(N) == iter1(N);

G und K sind extrem exponetiell, iter1 linear !
Also das ist die erste Arbeit, bei weiteren Fragen stehe ich zur Verfügung.

Hier ein kleines Beispiel: M gleich Ganzzahlen; InitG =1, InitK =2,
fk(x, y) = x * y; fg(x, y) = x + y;
KIter 2 | 1 2 6 30
GIter 1 | 2 3 5 11
N 1 | 2 3 4 5

GIter(5) == 11 == KIter(4) + KIter(3) + KIter(2) + KIter(1) = 6 + 2 + 1 + 2

[Schlangenmensch]

Ich persönliche verstehe grade deine Definition von G(N) und K(N) nicht. Ist das
G(N) = K(N-1) * fg * ... (was sind dann die Parameter von fg?) oder ist das K(N-1) * fg(K(N-2), K(N-3))?

Das alte Forum konnte auch Latex, dass ist für mathematische Schreibweisen ganz angenehm, ich weiß grade nicht, ob das immer noch geht.
Pseudocode würde ich auch mit Syntax Highlighting einstellen, ist dann auch besser zu lesen.

Zur Struktur: Was genau ist dein Ziel? Eine lineare Lösung für G(N)? (=Expo(N) )? Stell das mehr heraus.

Wenn du schon ein Beispiel machst, wie entwickeln sich denn G(N) und K(N) für das Beispiel? (Zumindest für einige Glieder).

Ansonsten: Deine Behauptung ist, das iter1() alle rekursiven Probleme, die sich in der Form formulieren lassen, linear und korrekt Lösen lassen. Kannst du die Korrektheit beweisen?

[SeppJ]

@Schlangenmensch sagte in Veröffentlichung:

Das alte Forum konnte auch Latex, dass ist für mathematische Schreibweisen ganz angenehm, ich weiß grade nicht, ob das immer noch geht.

Geht noch: Mit Dollarzeichen: $\sum_{i=0}^{n-1}q^i=\frac{1-q^n}{1-q}$
bzw. doppeltem Dollarzeichen:

$\sum_{i=0}^{n-1}q^i=\frac{1-q^n}{1-q}$

[biter]

Also GIter beim Schleifendurchlauf N ist immer gleich G(N) nenne ihn Giter'N, den Beweis liefere ich nach, bin momentan etwas geschafft. Und bei dem Beispiel heisst es fg(x, y) = x+ y; Das heisst oben G(N) für N>=3 ist gleich K(n-1) + K(N-2) + .... + K(1) und bei dem Besipiel ist fk(x, y) = x * y; also K(N) = G(N-1) * G(N-2) * ... * G(1). Versuche den Beweis: mit vollständiger Induktion allerdings nur schematsich: Die Basis ist trivial, Der Induktionsschritt: sei für N schon bewiesen. Es gelte also G(N) == GIter'N = K(N-1) fg ... fg K(1) beim Schleifefdurchlauf N also dann ist GIter'N+1 = fg(KIter'N, GIter'N) nach Vorraussetzung ist aber GIter'N = K(N-1) fg ... fg K(1) also ist G(N+1) = K(N) fg GITer'N == K(N) fg K(N-1) fg ....fg K(1) == GIter'N+1momentan bin ich etwas geschafft vielleich weisst Du was ich meine. wenn Du möchtest versuche ich es später nochmal. Dann habe ich noch gefunden einfach abzuleiten die Funktion Gs

function Gs(N) if N==1 return InitG; if N==2 return InitK
else return (Gs(N-2) fk Gs(N-3) fl ... fk Gs(1)) fg Gs(N-1)
Also iter1(N) == Gs(N) !
Wählt man InitG=1, InitK=1; fk(x, y)=x und fg(x, y)=x+y, erhält man den Beweis dass es für die rekursive Lösung des Fibonacci-Problems eine lineare gibt.

[wob]

Ich verstehe schon deine Notation nicht.

Sei M eine beliebige Menge, das können Zahlen, boolsche Werte, Buchstaben, oder irgendwelche komplexe Datenstrukuren sein.

Der Zusatz verwirrt nur. Sei $\mathbb{M}$ eine beliebige Menge. Wirklich beliebig? Oder hast du doch Einschränkungen wie dass es einen Mal-Operator geben muss? usw.

InitG elementvon M, InitK elementvon M,
fg eine beliebige zweistellige Funktion: M x M --> M
fk eine beliebige zweistellige Funktion: M x M --> M

In der Mathematik sind mehrbuchstabige Namen unüblich. Ich würde dazu tendieren, die Startwerte $g_0$ und $k_0$ zu nennen.

Seien $k: \mathbb{M} \times \mathbb{M} \rightarrow \mathbb{M}$ und $g: \mathbb{M} \times \mathbb{M} \rightarrow \mathbb{M}$ zwei beliebige Funktionen.

Wirklich beliebig?

(Und was jetzt? Wo kommt der Pseudocode her? Wofür gilt er?)
Was sind G und K für Funktionen?
$G: \mathbb{N} \rightarrow \text{?}$, $n \mapsto \left\{ ^{g_0\ \text{ fuer }\ n=1}_{K(N-1) g K(N-2) g .... g. K(1) \ \text{sonst}} \right.$

Genau wie @Schlangenmensch wirft das Rätsel auf. Deine Funktion hat doch 2 Argumente - du zeigst hier keine. Verstehe ich so nicht. Und was bedeutet der Punkt in der Mitte von "fg. K(1)"?

Von daher kann ich spätestens ab hier nichts mehr nachvollziehen.

G und K sind extrem exponetiell, iter1 linear !

Wie ist "extrem exponentiell" definiert?

[Bashar]

Die Funktionen werden als binäre Operationen geschrieben, d.h. $a\,f\,b$ steht für $f(a,b)$. Ein typisches Beispiel für so ein $f$ wäre $+$.

Allerdings kann man dann $a\,f\,b\,f\,c$ normalerweise nur schreiben, wenn $f$ assoziativ ist (oder wenn es anderweitig etablierte Assoziationsregeln gibt, wie bspw. bei $-$). Ich würde, ohne das im Detail weitergelesen zu haben, davon ausgehen, dass hier stillschweigend von assoziativen Verknüpfungen ausgegangen wird.

[biter]

Also jetzt der Beweis:
Mit GIter'N meine ich den Wert von GIter nach dem N-ten Schleifendurchlauf.
G(N) = K(N-1) fg ......fg K(1)
Behauptung: GIter'N == G(N) darauf führe ich es zurück:
InduktionsBasis: trivial ...
InduktionsSchritt: G(N+1) = K(N) fg K(N-1) fg ... fg K(1)
= K(N) fg G(N) = K(N) fg GInit'N
= fg(K(N), GInit'N) = GInit'N+1

Die Funktion fk ,fg sind zweistellig, hier aber in InfixNotation, sowie + zweistellig ist, aber aber in InfixNotation 3 + 4 + 5 geschrieben wird.

[wob]

@Bashar sagte in Veröffentlichung:

Die Funktionen werden als binäre Operationen geschrieben, d.h. afba,f,bafb steht für f(a,b)f(a,b)f(a,b)

Ah, hatte ich so noch nie gesehen. Ich kenne das so, dass man dann ein neues Symbol einsetzt wie z.B. $\circ$ oder $\oplus$.

[biter]

Nein, es werden keine assoziativen Verknüpfungen vorrausgesetzt, die Berechnung muss immer rechtsassoziativ ausgeführt werden. Bei + und * egal ...

[biter]

Die Wahl der Grundmenge M, ist wirklich beliebig, der Beweis nimmt nirgends auf den Mengentyp Bezug. Ich habe das Programm auch schon für boolesche Werte, für Lisp-Objekte ( Lisp heisst Lisp-Processing, Listenverarbeitung eine Programmiersprache ) getestet. Dadurch hat meine Lösung 5 Freiheitsgrade, die Wahl der Grundmenge, die beiden Funktionen fg, und fk ( wirklich beliebig ) InitG und InitK. Denke, dass das Prinzip viele Anwendungen hat. Jetzt muss ich der Arbeit noch einen Namen geben, schlage "expolin1" vor. Für Pseudocode gibt es keine Definition, man schreibt einfach etwas hin, was richtig verstanden werden soll.

[biter]

Was ist mein Ziel ? Ich würde gern mit anderen Menschen zusammenarbeiten, und unter anderem meine Ansätze weiterentwickeln. Habt Ihr keine Lust dazu ? Vielleicht bekommt Ihr noch das Preisgeld für P = NP .10^6 $ Dazu müsste man sich erst kennenlernen ..

[It0101]

@biter
10^6 USD nur? für P=NP ? Die Lösung ist Milliarden wert. Da heuerst du bei Google an, lässt dir drei Dienstwohnungen, 5 Dienstwagen und 10 Mio lebenslanges Jahresgehalt geben. Einfach nur dafür, dass Google dein Zeug benutzen darf

[SeppJ]

P=NP ist eines der Millennium Prize Problems (selbst wenn man das viel wahrscheinlichere P!=NP beweist). Somit also schon einmal $1M sicher. Und das ist halt wie eine Goldmedaille im Sport: Das Preisgeld ist nur Kleingeld, der wahre Gewinn sind die Sponsoren.