Logo
Unionpedia
Kommunikation
Jetzt bei Google Play
Neu! Laden Sie Unionpedia auf Ihrem Android™-Gerät herunter!
Herunterladen
Schneller Zugriff als Browser!
 

P-NP-Problem

Index P-NP-Problem

Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik.

57 Beziehungen: Alexander Alexandrowitsch Rasborow, Algorithmus, Approximation, Asymmetrisches Kryptosystem, Automat (Informatik), Berechenbarkeit, Cantor-Diagonalisierung, Circuit Value Problem, Clay Mathematics Institute, Determinismus (Algorithmus), Division mit Rest, Donald E. Knuth, Effizienz (Informatik), Einwegfunktion, Erfüllbarkeitsproblem der Aussagenlogik, EXPTIME, Faktorisierungsverfahren, Färbung (Graphentheorie), Gerhard Woeginger, HP Inc., Isomorphie von Graphen, John Forbes Nash Jr., John von Neumann, Karps 21 NP-vollständige Probleme, Komplexitätstheorie, Kryptologie, Kurt Gödel, Lance Fortnow, Leonid Levin, Mihalis Yannakakis, Millennium-Probleme, National Security Agency, Nichtdeterministische Turingmaschine, NP (Komplexitätsklasse), NP-Schwere, NP-Vollständigkeit, Orakel-Turingmaschine, P (Komplexitätsklasse), Parametrisierter Algorithmus, Polynom, Polynomialzeit, Polynomialzeitreduktion, Problem des Handlungsreisenden, Randomisierter Algorithmus, Richard J. Lipton, Robert M. Solovay, Rucksackproblem, Satz von Ladner, Scott Aaronson, Sortierverfahren, ..., Stephen A. Cook, Steven Rudich, Teilmenge, Theoretische Informatik, Turingmaschine, Zeitkomplexität, Zermelo-Fraenkel-Mengenlehre. Erweitern Sie Index (7 mehr) »

Alexander Alexandrowitsch Rasborow

Alexander Alexandrowitsch Rasborow (englische Transliteration Alexander Razborov; * 6. Februar 1963 in Belowo) ist ein russischer Informatiker und Mathematiker.

Neu!!: P-NP-Problem und Alexander Alexandrowitsch Rasborow · Mehr sehen »

Algorithmus

sowjetischen Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums Ein Algorithmus (benannt nach al-Chwarizmi, von arabisch: Choresmier) ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.

Neu!!: P-NP-Problem und Algorithmus · Mehr sehen »

Approximation

Approximation („der Nächste“) ist zunächst ein Synonym für eine „(An-)Näherung“; der Begriff wird in der Mathematik allerdings als Näherungsverfahren noch präzisiert.

Neu!!: P-NP-Problem und Approximation · Mehr sehen »

Asymmetrisches Kryptosystem

Asymmetrisches Kryptosystem ist ein Public-Key-Verfahren, das zur Public-Key-Authentifizierung und für digitale Signaturen genutzt werden kann.

Neu!!: P-NP-Problem und Asymmetrisches Kryptosystem · Mehr sehen »

Automat (Informatik)

Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.

Neu!!: P-NP-Problem und Automat (Informatik) · Mehr sehen »

Berechenbarkeit

Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie).

Neu!!: P-NP-Problem und Berechenbarkeit · Mehr sehen »

Cantor-Diagonalisierung

Als Cantor-Diagonalisierung werden zwei von Georg Cantor entwickelte Diagonalisierungsbeweisverfahren bezeichnet.

Neu!!: P-NP-Problem und Cantor-Diagonalisierung · Mehr sehen »

Circuit Value Problem

Das Circuit Value Problem (engl., CVP, dt. etwa: Schaltkreis-Auswertungsproblem) ist in der theoretischen Informatik ein P-vollständiges Problem.

Neu!!: P-NP-Problem und Circuit Value Problem · Mehr sehen »

Clay Mathematics Institute

Das Clay Mathematics Institute (CMI) zur Förderung der Mathematik hat seinen Sitz in Peterborough (New Hampshire), USA.

Neu!!: P-NP-Problem und Clay Mathematics Institute · Mehr sehen »

Determinismus (Algorithmus)

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.

Neu!!: P-NP-Problem und Determinismus (Algorithmus) · Mehr sehen »

Division mit Rest

Die Division mit Rest ist ein mathematischer Satz aus der Algebra und der Zahlentheorie.

Neu!!: P-NP-Problem und Division mit Rest · Mehr sehen »

Donald E. Knuth

Donald Knuth (2005) Donald Ervin „Don“ Knuth (* 10. Januar 1938 in Milwaukee, Wisconsin) ist ein US-amerikanischer Informatiker.

Neu!!: P-NP-Problem und Donald E. Knuth · Mehr sehen »

Effizienz (Informatik)

Die Effizienz eines Algorithmus ist seine Sparsamkeit bezüglich Ressourcen, Rechenzeit und Speicherplatz, die jener zur Lösung eines festgelegten Problems beansprucht.

Neu!!: P-NP-Problem und Effizienz (Informatik) · Mehr sehen »

Einwegfunktion

In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist.

Neu!!: P-NP-Problem und Einwegfunktion · Mehr sehen »

Erfüllbarkeitsproblem der Aussagenlogik

Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von ‚ Erfüllbarkeit‘) ist ein Entscheidungsproblem der theoretischen Informatik.

Neu!!: P-NP-Problem und Erfüllbarkeitsproblem der Aussagenlogik · Mehr sehen »

EXPTIME

Zusammenhang mit anderen Komplexitätsklassen In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine (DTM) in durch \mathcal O\left(2^\right) beschränkter Zeit entschieden werden können.

Neu!!: P-NP-Problem und EXPTIME · Mehr sehen »

Faktorisierungsverfahren

Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie.

Neu!!: P-NP-Problem und Faktorisierungsverfahren · Mehr sehen »

Färbung (Graphentheorie)

Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw.

Neu!!: P-NP-Problem und Färbung (Graphentheorie) · Mehr sehen »

Gerhard Woeginger

Gerhard Woeginger (2011) Gerhard J. Woeginger (* 31. Mai 1964 in Graz; † 1. April 2022) war ein österreichischer Informatiker.

Neu!!: P-NP-Problem und Gerhard Woeginger · Mehr sehen »

HP Inc.

Die HP Inc. (bis 1. November 2015 Hewlett-Packard Company) ist einer der größten US-amerikanischen PC- und Druckerhersteller, registriert in Wilmington, Delaware und mit der Unternehmenszentrale in Palo Alto, Kalifornien.

Neu!!: P-NP-Problem und HP Inc. · Mehr sehen »

Isomorphie von Graphen

Die Isomorphie von Graphen (oder Graphenisomorphie) ist in der Graphentheorie die Eigenschaft zweier Graphen, strukturell gleich zu sein.

Neu!!: P-NP-Problem und Isomorphie von Graphen · Mehr sehen »

John Forbes Nash Jr.

John Forbes Nash (2000er Jahre) John Forbes Nash, Jr. (* 13. Juni 1928 in Bluefield, West Virginia; † 23. Mai 2015 nahe Monroe Township, New Jersey) war ein US-amerikanischer Mathematiker, der besonders in den Bereichen Spieltheorie und Differentialgeometrie sowie auf dem Gebiet der partiellen Differentialgleichungen arbeitete.

Neu!!: P-NP-Problem und John Forbes Nash Jr. · Mehr sehen »

John von Neumann

John von Neumann (um 1940) John von Neumann (* 28. Dezember 1903 in Budapest, Österreich-Ungarn als Neumann János Lajos; † 8. Februar 1957 in Washington, D.C., Vereinigte Staaten) war ein ungarisch-US-amerikanischer Mathematiker.

Neu!!: P-NP-Problem und John von Neumann · Mehr sehen »

Karps 21 NP-vollständige Probleme

Karps 21 NP-vollständige Probleme ist eine in der Komplexitätstheorie gebräuchliche Menge NP-vollständiger Rechenprobleme.

Neu!!: P-NP-Problem und Karps 21 NP-vollständige Probleme · Mehr sehen »

Komplexitätstheorie

Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen.

Neu!!: P-NP-Problem und Komplexitätstheorie · Mehr sehen »

Kryptologie

Mit Zufallstexten aus Ziffern beschriftetes Kryptologen-Denkmal vor dem Residenzschloss Posen Die Kryptologie („versteckt, verborgen, geheim“ und -logie) ist eine Wissenschaft, die sich mit der Verschlüsselung und Entschlüsselung von Informationen und somit mit der Informationssicherheit beschäftigt.

Neu!!: P-NP-Problem und Kryptologie · Mehr sehen »

Kurt Gödel

rahmenlos Kurt Friedrich Gödel (* 28. April 1906 in Brünn, Österreich-Ungarn, heute Tschechien; † 14. Januar 1978 in Princeton, New Jersey, Vereinigte Staaten) war ein österreichischer und später US-amerikanischer Mathematiker, Philosoph und einer der bedeutendsten Logiker des 20. Jahrhunderts.

Neu!!: P-NP-Problem und Kurt Gödel · Mehr sehen »

Lance Fortnow

Lance Jeremy Fortnow (* 1963) ist ein amerikanischer Informatiker.

Neu!!: P-NP-Problem und Lance Fortnow · Mehr sehen »

Leonid Levin

Leonid Levin (2010) Leonid Levin (Leonid Anatoljewitsch Lewin; * 2. November 1948 in Dnepropetrowsk, Ukrainische SSR) ist ein sowjetisch-amerikanischer Informatiker.

Neu!!: P-NP-Problem und Leonid Levin · Mehr sehen »

Mihalis Yannakakis

Mihalis Yannakakis (Michalis Giannakakis; * 13. September 1953 in Athen) ist ein griechischer Informatiker.

Neu!!: P-NP-Problem und Mihalis Yannakakis · Mehr sehen »

Millennium-Probleme

Als Millennium-Probleme werden die im Jahr 2000 vom Clay Mathematics Institute (CMI) in Cambridge (Massachusetts) in einer Liste aufgezählten ungelösten Probleme der Mathematik bezeichnet.

Neu!!: P-NP-Problem und Millennium-Probleme · Mehr sehen »

National Security Agency

NSA-Hauptquartier in Fort Meade, Maryland, 2013 Die National Security Agency, offizielle Abkürzung NSA, ist der größte Auslandsgeheimdienst der Vereinigten Staaten.

Neu!!: P-NP-Problem und National Security Agency · Mehr sehen »

Nichtdeterministische Turingmaschine

Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.

Neu!!: P-NP-Problem und Nichtdeterministische Turingmaschine · Mehr sehen »

NP (Komplexitätsklasse)

In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.

Neu!!: P-NP-Problem und NP (Komplexitätsklasse) · Mehr sehen »

NP-Schwere

NP-vollständigen Probleme. Zu beachten ist, dass auf der rechten Seite die leere Sprache und ihr Komplement außen vor gelassen werden (beide sind zwar in P und NP, aber nicht NP-schwer). NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP.

Neu!!: P-NP-Problem und NP-Schwere · Mehr sehen »

NP-Vollständigkeit

NP-schweren und NP-vollständigen Probleme. In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist.

Neu!!: P-NP-Problem und NP-Vollständigkeit · Mehr sehen »

Orakel-Turingmaschine

Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist.

Neu!!: P-NP-Problem und Orakel-Turingmaschine · Mehr sehen »

P (Komplexitätsklasse)

In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind.

Neu!!: P-NP-Problem und P (Komplexitätsklasse) · Mehr sehen »

Parametrisierter Algorithmus

Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollständigen Problemen effizient zu lösen sind.

Neu!!: P-NP-Problem und Parametrisierter Algorithmus · Mehr sehen »

Polynom

Ein Polynom ist ein algebraischer Term, der sich als Summe von Vielfachen von Potenzen einer Variablen bzw.

Neu!!: P-NP-Problem und Polynom · Mehr sehen »

Polynomialzeit

In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn es mit einer deterministischen Rechenmaschine in einer Rechenzeit lösbar ist, die mit der Problemgröße nicht stärker als gemäß einer Polynomfunktion wächst.

Neu!!: P-NP-Problem und Polynomialzeit · Mehr sehen »

Polynomialzeitreduktion

Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik.

Neu!!: P-NP-Problem und Polynomialzeitreduktion · Mehr sehen »

Problem des Handlungsreisenden

größten Städte Deutschlands. Die angegebene Route ist die kürzeste von formatnum:43589145600 möglichen. Das Problem des Handlungsreisenden (auch Problem des Handelsreisenden, Botenproblem, Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem (TSP)) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik.

Neu!!: P-NP-Problem und Problem des Handlungsreisenden · Mehr sehen »

Randomisierter Algorithmus

Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) ist ein Algorithmus, der versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw.

Neu!!: P-NP-Problem und Randomisierter Algorithmus · Mehr sehen »

Richard J. Lipton

Richard Jay Lipton (* 6. September 1946) ist ein US-amerikanischer Informatiker (Theoretische Informatik, Kryptologie, DNA-Computer).

Neu!!: P-NP-Problem und Richard J. Lipton · Mehr sehen »

Robert M. Solovay

Robert Solovay, 1983 Robert Martin Solovay (* 1938 in Brooklyn) ist ein US-amerikanischer Mathematiker, der sich mit axiomatischer Mengenlehre beschäftigt.

Neu!!: P-NP-Problem und Robert M. Solovay · Mehr sehen »

Rucksackproblem

Das Rucksackproblem: Welche der Gewichte können in den Rucksack mit Maximallast von 15 kg gepackt werden, so dass der Geldwert maximal wird? (Lösung in diesem Fall: Alle Gewichte außer dem schwersten einpacken.) Das Rucksackproblem (auch) ist ein Optimierungsproblem der Kombinatorik.

Neu!!: P-NP-Problem und Rucksackproblem · Mehr sehen »

Satz von Ladner

Der Satz von Ladner ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP in Bezug auf P befasst.

Neu!!: P-NP-Problem und Satz von Ladner · Mehr sehen »

Scott Aaronson

Scott Aaronson Scott Joel Aaronson (* 21. Mai 1981 in Philadelphia) ist ein US-amerikanischer Informatiker.

Neu!!: P-NP-Problem und Scott Aaronson · Mehr sehen »

Sortierverfahren

Unter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren.

Neu!!: P-NP-Problem und Sortierverfahren · Mehr sehen »

Stephen A. Cook

Stephen Arthur Cook OOnt (* 14. Dezember 1939 in Buffalo, New York) ist Professor der Informatik an der University of Toronto in Kanada.

Neu!!: P-NP-Problem und Stephen A. Cook · Mehr sehen »

Steven Rudich

Steven Rudich (* 4. Oktober 1961) ist ein US-amerikanischer Informatiker, der sich mit Komplexitätstheorie, Kryptographie und Kombinatorik beschäftigt.

Neu!!: P-NP-Problem und Steven Rudich · Mehr sehen »

Teilmenge

Mengendiagramm: ''A'' ist eine (echte) Teilmenge von ''B''. Die mathematischen Begriffe Teilmenge und Obermenge beschreiben eine Beziehung zwischen zwei Mengen.

Neu!!: P-NP-Problem und Teilmenge · Mehr sehen »

Theoretische Informatik

Mind-Map zu einem Teilbereich der theoretischen Informatik Die theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen in Zusammenhang stehen.

Neu!!: P-NP-Problem und Theoretische Informatik · Mehr sehen »

Turingmaschine

Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.

Neu!!: P-NP-Problem und Turingmaschine · Mehr sehen »

Zeitkomplexität

Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe.

Neu!!: P-NP-Problem und Zeitkomplexität · Mehr sehen »

Zermelo-Fraenkel-Mengenlehre

Die Zermelo-Fraenkel-Mengenlehre ist eine verbreitete axiomatische Mengenlehre, die nach Ernst Zermelo und Abraham Adolf Fraenkel benannt ist.

Neu!!: P-NP-Problem und Zermelo-Fraenkel-Mengenlehre · Mehr sehen »

Leitet hier um:

P versus NP, P!=NP, P-NP, P/NP-Problem, P=NP, P=NP-Problem, P≟NP.

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »