Ist das P vs NP problem nicht ein nummerisches Problem?

Hallo Leute

Diejenige die das N vs NP problem kennen, können mir sicher Antworten.

Handelt es sich hier nicht um ein nummerisches Problem oder anderst gefragt: Wenn ich in der lage bin eine Methode zu finden, dass jedes Problem in nicht exponenzaler Zeit lösen kann. So würde ich das P vd NP problem lösen. Solch ein algorythmus kann man evt mit Hilfe von Nummerik zeigt werden? ( evt sogar Programmiert werden )

Freue mich auf eine Antwort.

Grüsse Rolf

1 Antwort

Kelec

17.04.2024, 19:26

Es ist ein Problem aus der Numerik nur ist kein Algorithmus bekannt welcher jedes Problem mit weniger Komplexität löst und es kann auch nicht gezeigt werden, dass das kein so ein Algorithmus existiert.

Also sobald du so einen Algorithmus implementierst hast du auch das Problem gelöst nur ist es bis jetzt eben niemanden gelungen.

Wenn du allgmein fragst ob nur die Frage ob P=NP nummerisch lösbar ist dann Nein. Es ist schwer die Mächtigkeit zweier Mengen nummerisch zu bestimmen wenn die Mengen beliebig groß oder unendlich groß sind.

Ähnliche Beiträge

Wie beweist man Beweisbarkeit?

Hallo liebe Mathefans und Logikisten ;)

Ich bin in letzter Zeit häufig bei meinen Recherchen über mathematische Themen auf diesen Satz gestoßen: "Mathematiker X hat bewiesen, dass man das Problem nicht beweisen kann"

Die Frage die ich mir jetzt stelle, wie funktioniert das? Wie zeigt man, dass sich ein Problem lösen lässt, oder eben nicht? Ist das Problemspezifisch oder kann man ähnliche Methoden auf alle Probleme anwenden? Bei welchen Problemen findet man sowas?

...zum Beitrag

Python: Index einer Numpy Matrix finden?

Hallo,

Ich suche eine Methode um den Index des Maximalwertes einer NP-Matrix-Reihe zu finden.

Bei einer Liste wuede ich ja einfach:

max_value = max(my_list)
max_index = my_list.index(max_value)

verwenden, bei einem Array/Matrix ist das jedoch nicht moeglich.

Kennt jemand einen Weg mein Problem zu loesen ohne jede einzelne Reihe in eine Liste umzuwandeln?

snr = ist in meinem Fall eine [512,6] Matrix
snr_list = []


for i in range(0,6):
  max_snr = max(snr[:, i])
  max_snr_index = ???
    
    
  snr_list.append(np.mean(snr[int(max_snr_index)-10:int(max_snr_index)+10, i]))

Dankeschoen.

...zum Beitrag

Mischungsaufgaben Mathematik HILFE?

Hallo,

Ich brauche Hilfe bei dieser Mischungsaufgaben. Die anderen Aufgaben waren einfacher aber diese verstehe ich irgendwie überhaupt nicht. Vorallem das (240-x) Kennt jemand vielleicht für so eine Rechung eine bessere verständliche Methode oder lässt sich das einfach erklären?.

In einem Labor werden 240ml einer 8%igen Kochsalzlösung benötigt. Dazu mischt man eine 10%igen Kochsalzlösung mit einer 4%igen Kochsalzlösung. Berechne, wie viel Milliliter der 10%igen und der 4%igen Lösung benötigt werden.

(Beim Lösen der Gleichung habe ich keine Probleme, nur das aufstellen der Tabelle)

Das Bild zeigt die richtigen Lösungsschritte, nur verstehe ich sie einfach nicht.

...zum Beitrag

Unity Engine: Wie kann ich das Spiel stoppen (im Code)?

Hallo Community,

ich habe kürzlich einen Klon von Arkanoid in Unity nachgebaut. Dafür habe ich dieses Tutorial befolgt. Mit C# kenne ich mich recht gut aus, nur nicht mit Unity. Leider stellt das Tutorial zwar in Aussicht, dass man noch bestimmte Dinge tun könnte, zeigt aber einige der wirklich wichtigen Dinge davon nicht. Daher möchte ich gern folgende Dinge in Bezug auf Unity wissen:

Wie stellt man fest, ob der Ball den unteren Bildschirmrand verlassen hat? Und wie wird das Spiel dann gestoppt?
Was muss programmiert / eingestellt werden, um zu testen, ob noch Blöcke übrig sind?
Auf welche Weise kann man ein weiteres Level aufrufen?

Zu 1: Hier habe ich bereits das Internet durchforstet. Laut dem, was ich gefunden habe, ist es das Beste, die Methode OnBecomeInvisible() aufzurufen und dort

Time.timeScale = 0;

zu setzen. Das habe ich in der Klasse für den Ball gemacht, aber leider konnte der Schläger immer noch bewegt werden. Was muss ich anders machen?

Zu 3: Ich habe bereits 2 weitere Level zusammengestellt. Jetzt weiß ich leider nicht, wie ich diese laden kann, sobald im vorherigen alle Blöcke zerstört wurden.

Danke schon mal für eure Hilfe.

...zum Beitrag

Integral x*e^x dx. Ist es überhaupt möglich diese Funktion zu integrieren, da mir mein Taschenrechner und auch die Rechner im Netzt kein Ergebnis angeben?

...zum Beitrag

EBNF Aufgaben (Erweiterte Backus-Naur-Form)?

Wie löse ich diese Aufgaben ?

Das Grundverständnis wie die EBNF funktioniert habe ich doch dieses Thema breitet mir einfach Probleme. Meist verstehe ich solche Themen durch die Lösung besser als durch stundenlange Recherche in verschiedenen Skripts.

...zum Beitrag

Wo schlagt ihr nach, wenn ihr euch nicht auskennt beim Programmieren?

Hallo Leute, ich will nur Fragen, was ihr macht, wenn ihr nicht weiter wisst bei einem Projekt, während ihr programmiert.

Weil ich möchte programmieren und ich möchte meiden Internet Seiten (die mit fertig geschriebenen) und YouTube Tutorials zu verwenden, während ich programmiere, da dort die Codes fertig geschrieben sind und ich sie nicht komplett abschreiben möchte, aber ich könnte mir den Code zumindest durchlesen.

Ich würde lieber im Internet die offizielle Dokumentationen der Programmiersprachen zur Hand nehmen und wenn es wirklich ein spezifisches Problem ist, könnte ich diese oben genannten Methoden verwenden, die ich normalerweise Meiden würde und wahrscheinlich auch Foren wie auf Reddit und Stack Overflow verwenden (obwohl mir Stack Overflow immer sehr unsympathisch wirkt).

Mir ist es bewusst, dass das alles Selbstverständlich ist sowas zu tun, aber in der Schule wurde uns sowas nicht so gelehrt sowas zu machen, sondern uns wurden die Zetteln/Word Dateien gegeben, mit Trockenen Erklärungen und meistens stumpfes Auswendiglernen. Die Aufgaben, die uns die Professoren geben sind recht unverständlich und trotz das wir sie Fragen stellen konnten, haben sie niemanden beim Programmieren geholfen, sowie als wollen sie uns dazu bringen das Programmieren zu hassen.

Versteht mich nicht falsch, ich finde Programmieren trotzdem interessant und will es auch erlernen, aber das was man in der Schule lernt ist nichts. Wir haben dort nie wirklich was mit GC oder Memory Allocations gehabt, sondern haben meistens oberflächlich mit VS 2019 mit C# gelernt. Die Sprache ist eigentlich recht verständlich, aber in der Schule war es eben recht schmerzhaft zu lernen.

Programmiersprachen die ich lernen möchte sind C# und Python zurzeit. In der Zukunft auch Rust, aber das würde ich später lernen.

Wie ist es bei euch so?

Danke LG

...zum Beitrag

Java-Code erklärung?

Ich bitte um die genaue ausführliche Erklärung für diese Methode

warum int y=1 und nicht y=0? warum y < höhe-1? warum...

 /**
     * Dieses Bild weichzeichnen.
     */
    public void weichzeichnen()
    {
        int a=0;
        short[][] _kopie = new short[_hoehe][_breite];


        for (int y=1;y<_hoehe-1;y++)
        {
            for (int x=1;x<_breite-1;x++)
            {
                //TODO randbearbeiten y=0...hoehe
                a=(_bilddaten[y+1][x+1]+_bilddaten[y-1][x-1]+_bilddaten[y+1][x-1]+_bilddaten[y-1][x+1]+_bilddaten[y][x+1]+_bilddaten[y][x-1]+_bilddaten[y+1][x]+_bilddaten[y-1][x])/8;
                _kopie[y][x]=(short)a;                
            }
        }
        _bilddaten=_kopie;
        zeichneBild();


    }

...zum Beitrag

Lauflängenkodierung Binärtext?

Hallo, ich habe folgenden Binärtext:

1111100001011000011111100000000011111

Wie kodiere ich den mit Hilfe der Lauflängenkodierung?

Wie errechne ich wie viel % Kompression erreicht wird?

Danke schonmal!

...zum Beitrag

Binärzahlen subtraktion?

Ich verstehe bei der Aufgabe nicht, warum 107 rauskommt und nicht -149, denn 107 würde ja wieder im Wertebereich: -127,...,128 liegen.

...zum Beitrag

Beweis durch strukturelle Induktion?

Wir haben folgende Funktionen:

prod :: [Int] -> Int

prod [] = 1 -- prod.1

prod (x:xs) = x * prod xs -- prod.2

foldl :: (b -> a -> b) -> b -> [a] -> b

foldl f acc [] = acc -- foldl.1

foldl f acc (x:xs) = foldl f (f acc x) xs -- foldl.2

Aufgabe:

Man soll mit struktureller Induktion beweisen, dass folgende Aussage gilt:

foldl (*) 1 xs = prod xs

Ich habe momentan:

foldl (*) 1 xs = prod xs

I.A. (xs = []):

foldl (*) 1 [] = prod []

foldl f acc [] = acc prod [] = 1 -- foldl.1 & plod.1

foldl f 1 [] = 1

1 = 1

I.V.: Wir nehmen an, dass die Aussage gilt für ein beliebiges xs

I.S. (xs -> x:xs):

foldl (*) 1 (x:xs) = prod (x:xs) -- foldl.2 & prod.2

foldl (*) ((*) 1 x) xs = x * prod xs

Problem: Ich weiß nun nicht wie ich mit dem Induktionsschritt fortfahren soll.

...zum Beitrag

Java-Code erklären?

Ich bitte um eine ausführliche Erklärung!

 * Ein Spielfeld besteht aus drei Zeilen mit je drei Spalten. Man kann an den
 * neun Positionen einen der beiden Spieler als Besitzer eintragen und auslesen.
 */
public class SpielfeldString implements Spielfeld 
{
    private String feld;


    /**
     * Initialisiert ein neues, leeres Spielfeld.
     */
    public SpielfeldString() {
        feld = "000000000";
        //012345678
    }


    /**
     * Die Methode berechnet die bestimmte Position.
     *
     * @param zeile   vertikale Position (0-2)
     * @param spalte  horizontale Position (0-2)
     * @return eine Int-Zahl von 0 bis 8
     */
    private int gibPosition(int zeile, int spalte){
        if (zeile < 0 || zeile > 2 || spalte < 0 || spalte > 2){
            throw new IllegalArgumentException("Spalte oder Zeile ist ausser dem Feld!");
        }
        return zeile * 3 + spalte;
    }


    /**
     * Gibt den Besitzer der angegebenen Position auf dem Spielfeld.
     *
     * @param zeile  vertikale Position (0-2)
     * @param spalte horizontale Position (0-2)
     * @return 0 (unbesetzt), 1 (Spieler 1), 2 (Spieler 2)
     */
    @Override
    public int gibBesitzer(int zeile, int spalte) {
        int besitzer = 0;
        char zeichen = feld.charAt(gibPosition(zeile, spalte));
        switch (zeichen){
            case '0':
                besitzer = 0;
                break;
            case '1':
                besitzer = 1;
                break;
            case '2':
                besitzer = 2;
                break;
        }
        return besitzer;
    }


    /**
     * Besetzt die angegebene Position auf dem Spielfeld fuer einen Spieler.
     *
     * @param zeile   vertikale Position (0-2)
     * @param spalte  horizontale Position (0-2)
     * @param spieler 0 (leer), 1 (Spieler 1), 2 (Spieler 2)
     */
    @Override
    public void besetzePosition(int zeile, int spalte, int spieler) {
        int position = gibPosition(zeile, spalte);
        feld = feld.substring(0, position) + spieler + feld.substring (position + 1);
    }


    /**
     * Gibt an, ob das Spielfeld an allen Positionen belegt ist.
     */
    @Override
    public boolean istVoll() {
        return feld.indexOf("0") == -1; // da wenn es kein 0 mehr in der Zeichenkette gibt,
        // wird -1 zurückgegeben.
    }
}

...zum Beitrag

Vorteile bewusst/gezielt Redundanzen in einer Datenbank zuzulassen?

Ein Vorteil ist sicherlich die höhere Sicherheit.

Was für Vorteile gibt es noch für eine Datenbank, wenn man bewusst/gezielt Redundanzen in ihr zulässt?

...zum Beitrag

Zusammenhang zwischen lokalen und globalen Computernetzwerk?

Zusammenhang zwischen den Begriffen „Lokales Computernetzwerk - LAN", „Globales Computernetzwerk - WAN, MAN und GAN

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen