Schneller Zugriff als Browser!
24 Beziehungen: Aussagenlogik, Éva Tardos, Belegung (Mathematik), Cliquenproblem, Disjunktionsterm, Erfüllbarkeitsproblem der Aussagenlogik, Formel, Gzip, Hamiltonkreisproblem, Jon Kleinberg, Komplexitätsklasse, Konjunktive Normalform, L (Komplexitätsklasse), Literal, NL (Komplexitätsklasse), NP-Schwere, NP-Vollständigkeit, Peter Gritzmann, Polynomialzeitreduktion, Reduktion (theoretische Informatik), Rucksackproblem, Satz von Cook, Uwe Schöning, 3sat.
Aussagenlogik
Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen ein Wahrheitswert zugeordnet wird.
Neu!!: 3-SAT und Aussagenlogik · Mehr sehen »
Éva Tardos
Éva Tardos (2007) Éva Tardos (* 1. Oktober 1957 in Budapest) ist eine ungarische Mathematikerin und Informatikerin.
Neu!!: 3-SAT und Éva Tardos · Mehr sehen »
Belegung (Mathematik)
Wird in der Mathematik einer Variablen ein konkreter Wert zugewiesen, wird das als Belegung bezeichnet.
Neu!!: 3-SAT und Belegung (Mathematik) · Mehr sehen »
Cliquenproblem
Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie.
Neu!!: 3-SAT und Cliquenproblem · Mehr sehen »
Disjunktionsterm
Ein Disjunktionsterm (auch als Disjunktionsglied oder Klausel bezeichnet) ist eine Boolesche Funktion, die ausschließlich durch die disjunktive Verknüpfung von Literalen gebildet wird.
Neu!!: 3-SAT und Disjunktionsterm · Mehr sehen »
Erfüllbarkeitsproblem der Aussagenlogik
Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von ‚ Erfüllbarkeit‘) ist ein Entscheidungsproblem der theoretischen Informatik.
Neu!!: 3-SAT und Erfüllbarkeitsproblem der Aussagenlogik · Mehr sehen »
Formel
Eine Kugel, deren Volumen durch die mathematische Formel V.
Neu!!: 3-SAT und Formel · Mehr sehen »
Gzip
gzip ist ein freies Kompressionsprogramm, das – ebenso wie das entsprechende Dateiformat gzip – praktisch für alle Computerbetriebssysteme verfügbar ist (unter den Bedingungen der GPL auch im Quelltext).
Neu!!: 3-SAT und Gzip · Mehr sehen »
Hamiltonkreisproblem
Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält.
Neu!!: 3-SAT und Hamiltonkreisproblem · Mehr sehen »
Jon Kleinberg
Jon Kleinberg auf dem ICM in Madrid 2006 Jon Michael Kleinberg (* Oktober 1971 in Boston) ist Professor für Informatik an der Cornell University in Ithaca.
Neu!!: 3-SAT und Jon Kleinberg · Mehr sehen »
Komplexitätsklasse
Komplexitätsklassen In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands.
Neu!!: 3-SAT und Komplexitätsklasse · Mehr sehen »
Konjunktive Normalform
Als konjunktive Normalform (kurz KNF, für conjunctive normal form) wird in der Aussagenlogik eine bestimmte Form von Formeln bezeichnet.
Neu!!: 3-SAT und Konjunktive Normalform · Mehr sehen »
L (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können.
Neu!!: 3-SAT und L (Komplexitätsklasse) · Mehr sehen »
Literal
Ein Literal ist ein spezieller Bestandteil einer formalen Sprache.
Neu!!: 3-SAT und Literal · Mehr sehen »
NL (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können.
Neu!!: 3-SAT und NL (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!!: 3-SAT 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!!: 3-SAT und NP-Vollständigkeit · Mehr sehen »
Peter Gritzmann
Gritzmann in Oberwolfach 2010 Peter Gritzmann (* 17. Dezember 1954 in Dortmund) ist ein deutscher Mathematiker.
Neu!!: 3-SAT und Peter Gritzmann · Mehr sehen »
Polynomialzeitreduktion
Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik.
Neu!!: 3-SAT und Polynomialzeitreduktion · Mehr sehen »
Reduktion (theoretische Informatik)
Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird.
Neu!!: 3-SAT und Reduktion (theoretische Informatik) · 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!!: 3-SAT und Rucksackproblem · Mehr sehen »
Satz von Cook
Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie.
Neu!!: 3-SAT und Satz von Cook · Mehr sehen »
Uwe Schöning
Uwe Schöning (* 28. Dezember 1955 in Ulm) ist ein deutscher Informatiker.
Neu!!: 3-SAT und Uwe Schöning · Mehr sehen »
3sat
3sat ist ein werbefreies deutschsprachiges öffentlich-rechtliches Fernsehprogramm.
Neu!!: 3-SAT und 3sat · Mehr sehen »
