Schneller Zugriff als Browser!
130 Beziehungen: Addition, Adjazenzmatrix, Akzeptieren (Automaten- und Komplexitätstheorie), Alan Cobham, Alan Turing, Algorithmus, Allan Borodin, Alphabet (Informatik), Alternierende Turingmaschine, Amortisierte Laufzeitanalyse, Andrew Yao, Approximationsalgorithmus, Asymptote, Asymptotische Analyse, Aussagenlogik, Automat (Informatik), Automatentheorie, Berechenbarkeitstheorie, Beweis (Mathematik), Bit, Boolescher Operator, BPP (Komplexitätsklasse), Brechen (Kryptologie), Chomsky-Hierarchie, Christos Papadimitriou, Church-Turing-These, Co-NP, Compiler, Computer, Datenstruktur, David Stifler Johnson, Determinismus (Algorithmus), DSPACE, DTIME, Dualsystem, Einwegfunktion, Endlicher Automat, Entscheidbar, Erfüllbarkeitsproblem der Aussagenlogik, Exponentialfunktion, EXPTIME, Extremwert, Formale Sprache, Funktion (Mathematik), Graph (Graphentheorie), Hardware, Hisao Yamada, Implementierung, Infimum und Supremum, Ingo Wegener, ..., Integrierter Schaltkreis, Jack Edmonds, Jan van Leeuwen (Informatiker), John Myhill, John T. Gill, Juris Hartmanis, Kellerautomat, Komplexes System, Komplexität (Informatik), Komplexitätsklasse, Kontextsensitive Sprache, Kryptographie, L (Komplexitätsklasse), Lance Fortnow, Landau-Symbole, Leonid Levin, Lineare Abbildung, Liste von Komplexitätsklassen, Logarithmus, Mailand, Manuel Blum, Michael Garey, Michael Sipser, Multiplikation, Natürliche Zahl, NC (Komplexitätsklasse), NEXPTIME, Nichtdeterminismus, Nichtdeterministische Turingmaschine, NL (Komplexitätsklasse), NP (Komplexitätsklasse), NP-Vollständigkeit, NSPACE, NTIME, Optimierungsproblem, P (Komplexitätsklasse), P-NP-Problem, Parallel Random Access Machine, Paralleler Algorithmus, Platzkomplexität, Polynom, Polynomialzeit, Potenzmenge, Praktische Informatik, Probabilistische Polynomialzeit, Probabilistische Turingmaschine, Problem, Problem des Handlungsreisenden, PSPACE, Quantencomputer, Quanteninformatik, Raymond Smullyan, Reduktion (theoretische Informatik), Registermaschine, Ressource, Richard E. Stearns, Richard M. Karp, RP (Komplexitätsklasse), Sanjeev Arora, Satz von Cook, Sowjetunion, Speedup-Theorem, Stephen A. Cook, Systemtheorie, Tautologie (Logik), Teilmenge, Theoretische Informatik, Transcomputationales Problem, Tupel, Turingmaschine, Ungleichung, Union-Theorem, Verschlüsselungsverfahren, Wahrscheinlichkeitsmaß, Wort (theoretische Informatik), Wortproblem (Berechenbarkeitstheorie), Wurzel (Mathematik), Zeitkomplexität, ZPP (Komplexitätsklasse), Zusammenhang (Graphentheorie). Erweitern Sie Index (80 mehr) »
Addition
Die Addition (von addere „hinzufügen“), umgangssprachlich auch Plus-Rechnen oder Und-Rechnen genannt, ist eine der vier Grundrechenarten in der Arithmetik.
Neu!!: Komplexitätstheorie und Addition · Mehr sehen »
Adjazenzmatrix
Eine Adjazenzmatrix (manchmal auch Nachbarschaftsmatrix) eines Graphen ist eine Matrix, die speichert, welche Knoten des Graphen durch eine Kante verbunden sind.
Neu!!: Komplexitätstheorie und Adjazenzmatrix · Mehr sehen »
Akzeptieren (Automaten- und Komplexitätstheorie)
Akzeptieren ist ein Begriff aus der Automaten- und Komplexitätstheorie, Teilgebieten der theoretischen Informatik.
Neu!!: Komplexitätstheorie und Akzeptieren (Automaten- und Komplexitätstheorie) · Mehr sehen »
Alan Cobham
Alan Cobham Sir Alan John Cobham, KBE (* 6. Mai 1894 in Southwark, London, England; † 21. Oktober 1973 in Bournemouth, England) war ein britischer Luftfahrtpionier und -unternehmer.
Neu!!: Komplexitätstheorie und Alan Cobham · Mehr sehen »
Alan Turing
Alan Turing (ca. 1938)Andrew Hodges: ''http://www.turing.org.uk/scrapbook/ww2.html The Alan Turing Internet Scrapbook.'' In: ''turing.org'', (englisch), abgerufen am 19. August 2017. Seine Unterschrift Alan Mathison Turing OBE, FRS (* 23. Juni 1912 in London; † 7. Juni 1954 in Wilmslow, Cheshire) war ein britischer Logiker, Mathematiker, Kryptoanalytiker und Informatiker.
Neu!!: Komplexitätstheorie und Alan Turing · 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!!: Komplexitätstheorie und Algorithmus · Mehr sehen »
Allan Borodin
Allan Bertram Borodin (* 1941) ist ein kanadischer Informatiker.
Neu!!: Komplexitätstheorie und Allan Borodin · Mehr sehen »
Alphabet (Informatik)
In der Informatik und der mathematischen Logik ist ein Alphabet eine endliche Menge voneinander unterscheidbarer Symbole, die auch Zeichen oder Buchstaben genannt werden.
Neu!!: Komplexitätstheorie und Alphabet (Informatik) · Mehr sehen »
Alternierende Turingmaschine
In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert.
Neu!!: Komplexitätstheorie und Alternierende Turingmaschine · Mehr sehen »
Amortisierte Laufzeitanalyse
In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen («sequences») dieser Operation.
Neu!!: Komplexitätstheorie und Amortisierte Laufzeitanalyse · Mehr sehen »
Andrew Yao
Andrew Yao 2005 Andrew Chi-Chih Yao (* 24. Dezember 1946 in Shanghai, Republik China) ist ein chinesischer Informatiker an der Tsinghua-Universität, China.
Neu!!: Komplexitätstheorie und Andrew Yao · Mehr sehen »
Approximationsalgorithmus
Ein Approximationsalgorithmus (oder auch Näherungsalgorithmus) ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst.
Neu!!: Komplexitätstheorie und Approximationsalgorithmus · Mehr sehen »
Asymptote
Eine Asymptote (altgr. ἀσύμπτωτος asýmptōtos „nicht übereinstimmend“,Duden, das große Fremdwörterbuch, Mannheim & Leipzig, 2000, ISBN 3-411-04162-5. von altgr. πίπτω pípto „ich falle“) ist in der Mathematik eine Kurve, häufig eine Gerade, der sich der Graph einer Funktion im Unendlichen immer weiter annähert.
Neu!!: Komplexitätstheorie und Asymptote · Mehr sehen »
Asymptotische Analyse
In der Mathematik und ihren Anwendungen bezeichnet asymptotische Analyse (auch asymptotische Analysis) einerseits eine Methode, um das Grenzverhalten von Funktionen oder Folgen zu klassifizieren, indem man nur den wesentlichen Trend des Grenzverhaltens beschreibt, andererseits aber auch die zugrundeliegende Theorie als Ganzes.
Neu!!: Komplexitätstheorie und Asymptotische Analyse · Mehr sehen »
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!!: Komplexitätstheorie und Aussagenlogik · 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!!: Komplexitätstheorie und Automat (Informatik) · Mehr sehen »
Automatentheorie
Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen Automaten lösbaren Problemen beschäftigt.
Neu!!: Komplexitätstheorie und Automatentheorie · Mehr sehen »
Berechenbarkeitstheorie
Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind.
Neu!!: Komplexitätstheorie und Berechenbarkeitstheorie · Mehr sehen »
Beweis (Mathematik)
Beispielhafter, schematischer Aufbau eines Beweises Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit bzw.
Neu!!: Komplexitätstheorie und Beweis (Mathematik) · Mehr sehen »
Bit
Der Begriff Bit (Kofferwort aus) Duden, Bibliographisches Institut, 2016 wird in der Informatik, der Informationstechnik, der Nachrichtentechnik sowie verwandten Fachgebieten in folgenden Bedeutungen verwendet.
Neu!!: Komplexitätstheorie und Bit · Mehr sehen »
Boolescher Operator
Die 16 booleschen Operatoren mit 2 Variablen.Jede Kombination der Inputs A und B („true“ oder „false“) ist durch eines der vier Gebiete innerhalb des kleinen Rechteckes repräsentiert; für jede Kombination von A und B in jedem Rechteck gilt: falls die Kombination mit einem eingefärbten Gebiet korrespondiert, ist der boolesche Operator „true“; falls die Kombination mit einem nicht eingefärbten Gebiet korrespondiert, ist der boolesche Operator „false“. Ein boolescher Operator ist ein logischer Operator, also ein Operator, der auf Wahrheitswerten operiert.
Neu!!: Komplexitätstheorie und Boolescher Operator · Mehr sehen »
BPP (Komplexitätsklasse)
In der Komplexitätstheorie steht BPP (englische Abkürzung für bounded error probabilistic polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen.
Neu!!: Komplexitätstheorie und BPP (Komplexitätsklasse) · Mehr sehen »
Brechen (Kryptologie)
Als brechen oder entziffern (umgangssprachlich oft auch als knacken) wird in der Kryptanalyse, also in dem Wissenschaftszweig der Kryptologie, der sich mit der Entzifferung von Geheimschriften befasst, die Tätigkeit eines Kryptoanalytikers oder Codebrechers bezeichnet, einem Geheimtext ohne Kenntnis des Schlüssels die Nachricht zu entringen, also ihn in den Klartext zurückzuwandeln.
Neu!!: Komplexitätstheorie und Brechen (Kryptologie) · Mehr sehen »
Chomsky-Hierarchie
Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der theoretischen Informatik.
Neu!!: Komplexitätstheorie und Chomsky-Hierarchie · Mehr sehen »
Christos Papadimitriou
Christos Charilaos Papadimitriou (* 1949 in Athen) ist ein griechischer Informatiker.
Neu!!: Komplexitätstheorie und Christos Papadimitriou · Mehr sehen »
Church-Turing-These
Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine.
Neu!!: Komplexitätstheorie und Church-Turing-These · Mehr sehen »
Co-NP
In der Komplexitätstheorie bezeichnet Co-NP eine Komplexitätsklasse.
Neu!!: Komplexitätstheorie und Co-NP · Mehr sehen »
Compiler
Ein Compiler (auch Kompilierer; von ‚zusammentragen‘ bzw. ‚aufhäufen‘) ist ein Computerprogramm, das Quellcodes einer bestimmten Programmiersprache in eine Form übersetzt, die von einem Computer (direkter) ausgeführt werden kann.
Neu!!: Komplexitätstheorie und Compiler · Mehr sehen »
Computer
Ein Computer (englisch; deutsche Aussprache) oder Rechner ist ein Gerät, das mittels programmierbarer Rechenvorschriften Daten verarbeitet.
Neu!!: Komplexitätstheorie und Computer · Mehr sehen »
Datenstruktur
thumb In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient.
Neu!!: Komplexitätstheorie und Datenstruktur · Mehr sehen »
David Stifler Johnson
David Stifler Johnson (* 9. Dezember 1945 in Washington, D.C.; † 8. März 2016) war ein US-amerikanischer Informatiker.
Neu!!: Komplexitätstheorie und David Stifler Johnson · Mehr sehen »
Determinismus (Algorithmus)
Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.
Neu!!: Komplexitätstheorie und Determinismus (Algorithmus) · Mehr sehen »
DSPACE
Der Begriff DSPACE stammt aus der Komplexitätstheorie in der theoretischen Informatik.
Neu!!: Komplexitätstheorie und DSPACE · Mehr sehen »
DTIME
In der Komplexitätstheorie steht DTIME(f) oder auch kurz TIME(f) für die Menge der Zeitkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine.
Neu!!: Komplexitätstheorie und DTIME · Mehr sehen »
Dualsystem
Das Dualsystem (lat. dualis „zwei enthaltend“), auch Zweiersystem oder Binärsystem genannt, ist ein Zahlensystem, das zur Darstellung von Zahlen nur zwei verschiedene Ziffern benutzt.
Neu!!: Komplexitätstheorie und Dualsystem · Mehr sehen »
Einwegfunktion
In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist.
Neu!!: Komplexitätstheorie und Einwegfunktion · Mehr sehen »
Endlicher Automat
Abbildung 1: Beispiel eines EA, der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat;, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.
Neu!!: Komplexitätstheorie und Endlicher Automat · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: Komplexitätstheorie und Entscheidbar · Mehr sehen »
Erfüllbarkeitsproblem der Aussagenlogik
Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von ‚ Erfüllbarkeit‘) ist ein Entscheidungsproblem der theoretischen Informatik.
Neu!!: Komplexitätstheorie und Erfüllbarkeitsproblem der Aussagenlogik · Mehr sehen »
Exponentialfunktion
In der Mathematik bezeichnet man als Exponentialfunktion eine Funktion der Form x \mapsto a^x mit einer reellen Zahl a > 0\text a \neq 1 als Basis (Grundzahl).
Neu!!: Komplexitätstheorie und Exponentialfunktion · 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!!: Komplexitätstheorie und EXPTIME · Mehr sehen »
Extremwert
Minima und Maxima der Funktion cos(3π''x'')/''x'' im Bereich 0.1≤'' x ''≤1.1 In der Mathematik ist Extremwert (oder Extremum; Plural: Extrema) der Oberbegriff für ein lokales oder globales Maximum oder Minimum.
Neu!!: Komplexitätstheorie und Extremwert · Mehr sehen »
Formale Sprache
Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die Definition und Anwendung formaler Systeme im engeren Sinn und der Logik im weiteren, allgemeinen Sinn.
Neu!!: Komplexitätstheorie und Formale Sprache · Mehr sehen »
Funktion (Mathematik)
In der Mathematik ist eine Funktion oder Abbildung eine Beziehung (Relation) zwischen zwei Mengen, die jedem Element der einen Menge (Funktionsargument, unabhängige Variable, x-Wert) genau ein Element der anderen Menge (Funktionswert, abhängige Variable, y-Wert) zuordnet.
Neu!!: Komplexitätstheorie und Funktion (Mathematik) · Mehr sehen »
Graph (Graphentheorie)
Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.
Neu!!: Komplexitätstheorie und Graph (Graphentheorie) · Mehr sehen »
Hardware
Hardware (im britischen bzw. im amerikanischen Englisch, gelegentlich mit „HW“ abgekürzt) ist der Oberbegriff für die physischen Komponenten (die elektronischen und mechanischen Bestandteile) eines datenverarbeitenden Systems, als Komplement zu Software (den Programmen und Daten).
Neu!!: Komplexitätstheorie und Hardware · Mehr sehen »
Hisao Yamada
Hisao M. Yamada (* 8. Juni 1930 in der Präfektur Tokio; † 21. Mai 2008) war ein japanischer Informatiker.
Neu!!: Komplexitätstheorie und Hisao Yamada · Mehr sehen »
Implementierung
Eine Implementierung – auch Implementation (über ‚Ausführung‘, ‚Durchführung‘; von spätlateinisch implementum ‚Gerät‘ zu ‚anfüllen‘, ‚erfüllen‘) genannt – ist das Implementieren oder das Implementiertwerden, also die Realisierung oder Umsetzung von festgelegten Strukturen und Prozessabläufen in einem System unter Berücksichtigung von Rahmenbedingungen, Regeln und Zielvorgaben, im Sinne einer Spezifikation.
Neu!!: Komplexitätstheorie und Implementierung · Mehr sehen »
Infimum und Supremum
Die Bildmenge der abgebildeten Funktion ist beschränkt, damit ist auch die Funktion beschränkt. In der Mathematik treten die Begriffe Supremum und Infimum sowie kleinste obere Schranke bzw.
Neu!!: Komplexitätstheorie und Infimum und Supremum · Mehr sehen »
Ingo Wegener
Ingo Wegener (vollständiger Name Ingo Werner Wegener; * 4. Dezember 1950 in Bremen; † 27. November 2008 in Bielefeld) war ein deutscher Informatiker, der auf dem Gebiet der theoretischen Informatik arbeitete.
Neu!!: Komplexitätstheorie und Ingo Wegener · Mehr sehen »
Integrierter Schaltkreis
Funktionseinheiten wie Rechenwerk und Cache des Prozessors zu erkennen. Aktuelle Prozessor-Chips umfassen bei ähnlichen Abmessungen mittlerweile etwa 4000 Mal so viele Transistoren. Ein integrierter Schaltkreis, auch integrierte Schaltung (kurz IC; die Buchstaben werden einzeln gesprochen: bzw. veraltet IS) ist eine auf einem dünnen, meist einige Millimeter großen Plättchen aus Halbleiter-Material aufgebrachte elektronische Schaltung.
Neu!!: Komplexitätstheorie und Integrierter Schaltkreis · Mehr sehen »
Jack Edmonds
Jack Edmonds Jack R. Edmonds (* 5. April 1934) ist ein kanadischer Informatiker und Mathematiker, der sich mit kombinatorischer Optimierung befasst.
Neu!!: Komplexitätstheorie und Jack Edmonds · Mehr sehen »
Jan van Leeuwen (Informatiker)
Jan van Leeuwen (* 17. Dezember 1946 in Waddinxveen) ist ein niederländischer theoretischer Informatiker.
Neu!!: Komplexitätstheorie und Jan van Leeuwen (Informatiker) · Mehr sehen »
John Myhill
John R. Myhill (* 11. August 1923 in Birmingham; † 15. Februar 1987) war ein britischer Mathematiker, Logiker, Philosoph, Informatiker und Hochschullehrer an der State University of New York at Buffalo.
Neu!!: Komplexitätstheorie und John Myhill · Mehr sehen »
John T. Gill
John T. Gill (John Thomas Gill, III) ist ein US-amerikanischer Informatiker und Hochschullehrer an der Stanford University.
Neu!!: Komplexitätstheorie und John T. Gill · Mehr sehen »
Juris Hartmanis
Juris Hartmanis (2002) Juris Hartmanis (* 5. Juli 1928 in Riga, Lettland; † 29. Juli 2022) war ein lettisch-US-amerikanischer Informatiker, der gemeinsam mit Richard E. Stearns 1993 den Turing Award für seine Forschungsleistungen auf dem Gebiet der Komplexitätstheorie erhielt.
Neu!!: Komplexitätstheorie und Juris Hartmanis · Mehr sehen »
Kellerautomat
Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen.
Neu!!: Komplexitätstheorie und Kellerautomat · Mehr sehen »
Komplexes System
Das Erdklima extrem vereinfacht: Eines der am besten untersuchten komplexen natürlichen Systeme Komplexe Systeme sind nach außen offene, hochgradig geordnete und organisierte, uneinheitlich aufgebaute (heterogene) Ganzheiten von funktionalen Strukturen (.
Neu!!: Komplexitätstheorie und Komplexes System · Mehr sehen »
Komplexität (Informatik)
Der Begriff Komplexität wird in der Informatik in verschiedenen Teilbereichen verwendet.
Neu!!: Komplexitätstheorie und Komplexität (Informatik) · 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!!: Komplexitätstheorie und Komplexitätsklasse · Mehr sehen »
Kontextsensitive Sprache
Die kontextsensitiven Sprachen (englisch context-sensitive languages, abgekürzt durch CSL) sind eine Klasse der formalen Sprachen, einem Teilgebiet der Theoretischen Informatik.
Neu!!: Komplexitätstheorie und Kontextsensitive Sprache · Mehr sehen »
Kryptographie
Kryptographie bzw.
Neu!!: Komplexitätstheorie und Kryptographie · 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!!: Komplexitätstheorie und L (Komplexitätsklasse) · Mehr sehen »
Lance Fortnow
Lance Jeremy Fortnow (* 1963) ist ein amerikanischer Informatiker.
Neu!!: Komplexitätstheorie und Lance Fortnow · Mehr sehen »
Landau-Symbole
Landau-Symbole (auch O-Notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.
Neu!!: Komplexitätstheorie und Landau-Symbole · 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!!: Komplexitätstheorie und Leonid Levin · Mehr sehen »
Lineare Abbildung
Achsenspiegelung als Beispiel einer linearen Abbildung Eine lineare Abbildung (auch lineare Transformation oder Vektorraumhomomorphismus genannt) ist in der linearen Algebra ein wichtiger Typ von Abbildung zwischen zwei Vektorräumen über demselben Körper.
Neu!!: Komplexitätstheorie und Lineare Abbildung · Mehr sehen »
Liste von Komplexitätsklassen
Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden.
Neu!!: Komplexitätstheorie und Liste von Komplexitätsklassen · Mehr sehen »
Logarithmus
Logarithmische Skaleneinteilung eines Rechenschiebers (Detail) e (rot) und 1/2 (blau) Logarithmus zur Basis 10. Als Logarithmus (Plural: Logarithmen; von, „Verständnis, Lehre, Verhältnis“, und ἀριθμός, arithmós, „Zahl“) einer Zahl bezeichnet man den Exponenten, mit dem eine vorher festgelegte Zahl, die Basis, potenziert werden muss, um die gegebene Zahl, den Numerus, zu erhalten.
Neu!!: Komplexitätstheorie und Logarithmus · Mehr sehen »
Mailand
Mailand ist mit rund 1,4 Millionen Einwohnern die zweitgrößte Stadt Italiens und Hauptstadt der Region Lombardei sowie der Metropolitanstadt Mailand.
Neu!!: Komplexitätstheorie und Mailand · Mehr sehen »
Manuel Blum
Manuel Blum (links), Lenore Blum, Avrim Blum, 1973 Manuel Blum (* 26. April 1938 in Caracas, Venezuela) ist ein US-amerikanischer Informatiker, der 1995 „in Anerkennung seiner Beiträge zu den Grundlagen der algorithmischen Komplexitätstheorie sowie deren Anwendung in der Kryptographie und der Fehlerüberprüfung von Programmen“ den Turing Award erhielt.
Neu!!: Komplexitätstheorie und Manuel Blum · Mehr sehen »
Michael Garey
Michael Randolph Garey (* 19. November 1945 in Manitowoc, Wisconsin) ist ein US-amerikanischer Informatiker.
Neu!!: Komplexitätstheorie und Michael Garey · Mehr sehen »
Michael Sipser
Michael Sipser, 2013 Michael Fredric Sipser (* 17. September 1954) ist ein US-amerikanischer Informatiker.
Neu!!: Komplexitätstheorie und Michael Sipser · Mehr sehen »
Multiplikation
Beispiel einer Multiplikation: 3\cdot4.
Neu!!: Komplexitätstheorie und Multiplikation · Mehr sehen »
Natürliche Zahl
reellen Zahlen (ℝ) sind. Die natürlichen Zahlen sind die beim Zählen verwendeten Zahlen 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 usw.
Neu!!: Komplexitätstheorie und Natürliche Zahl · Mehr sehen »
NC (Komplexitätsklasse)
NC steht in der Informatik als Abkürzung für Nick's Class (nach Nick Pippenger), die Komplexitätsklasse der parallel effizient lösbaren Entscheidungsprobleme.
Neu!!: Komplexitätstheorie und NC (Komplexitätsklasse) · Mehr sehen »
NEXPTIME
In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch \mathcal(2^) (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können.
Neu!!: Komplexitätstheorie und NEXPTIME · Mehr sehen »
Nichtdeterminismus
Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt.
Neu!!: Komplexitätstheorie und Nichtdeterminismus · Mehr sehen »
Nichtdeterministische Turingmaschine
Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
Neu!!: Komplexitätstheorie und Nichtdeterministische Turingmaschine · 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!!: Komplexitätstheorie und NL (Komplexitätsklasse) · 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!!: Komplexitätstheorie und NP (Komplexitätsklasse) · 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!!: Komplexitätstheorie und NP-Vollständigkeit · Mehr sehen »
NSPACE
NSPACE (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik.
Neu!!: Komplexitätstheorie und NSPACE · Mehr sehen »
NTIME
In der Komplexitätstheorie steht NTIME(f) für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können.
Neu!!: Komplexitätstheorie und NTIME · Mehr sehen »
Optimierungsproblem
Ein Optimierungsproblem ist ein mathematisches Problem.
Neu!!: Komplexitätstheorie und Optimierungsproblem · 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!!: Komplexitätstheorie und P (Komplexitätsklasse) · Mehr sehen »
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.
Neu!!: Komplexitätstheorie und P-NP-Problem · Mehr sehen »
Parallel Random Access Machine
Als Parallel Random Access Machine, kurz PRAM, bezeichnet man in der Informatik einen Automaten zur Analyse paralleler Algorithmen.
Neu!!: Komplexitätstheorie und Parallel Random Access Machine · Mehr sehen »
Paralleler Algorithmus
Ein paralleler Algorithmus ist ein Algorithmus, welcher zum Beispiel ein Problem der Komplexitätsklasse NC (Nick’s Class nach Nick Pippenger) in polynomieller Zeit lösen bzw.
Neu!!: Komplexitätstheorie und Paralleler Algorithmus · Mehr sehen »
Platzkomplexität
Unter der Platzkomplexität eines Problems versteht man den (minimalen) Bedarf an Speicherplatz eines Algorithmus zur Lösung dieses Problems, in Abhängigkeit von der Länge der Eingabe.
Neu!!: Komplexitätstheorie und Platzkomplexität · Mehr sehen »
Polynom
Ein Polynom ist ein algebraischer Term, der sich als Summe von Vielfachen von Potenzen einer Variablen bzw.
Neu!!: Komplexitätstheorie 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!!: Komplexitätstheorie und Polynomialzeit · Mehr sehen »
Potenzmenge
Die Potenzmenge von ''x'', ''y'', ''z'', dargestellt als Hasse-Diagramm. Als Potenzmenge bezeichnet man in der Mengenlehre die Menge aller Teilmengen einer gegebenen Grundmenge.
Neu!!: Komplexitätstheorie und Potenzmenge · Mehr sehen »
Praktische Informatik
Die Praktische Informatik (PI) ist eines der Hauptgebiete der Informatik.
Neu!!: Komplexitätstheorie und Praktische Informatik · Mehr sehen »
Probabilistische Polynomialzeit
In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die in von einer probabilistischen Turingmaschine in Polynomialzeit lösbar ist und die Antwort in mindestens der Hälfte der Fälle richtig ist.
Neu!!: Komplexitätstheorie und Probabilistische Polynomialzeit · Mehr sehen »
Probabilistische Turingmaschine
Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik.
Neu!!: Komplexitätstheorie und Probabilistische Turingmaschine · Mehr sehen »
Problem
Ein Problem („Vorsprung, Klippe, Hindernis; das, was vorgelegt wurde“) entsteht in einer Situation, in der ein oder mehrere Ziele erreicht werden müssen, wobei nicht unmittelbar sicher ist, welche Maßnahmen ergriffen oder welche Mittel eingesetzt werden müssen, um diese Ziele zu erreichen.
Neu!!: Komplexitätstheorie und Problem · 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!!: Komplexitätstheorie und Problem des Handlungsreisenden · Mehr sehen »
PSPACE
In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können.
Neu!!: Komplexitätstheorie und PSPACE · Mehr sehen »
Quantencomputer
Ein Quantenprozessor bzw.
Neu!!: Komplexitätstheorie und Quantencomputer · Mehr sehen »
Quanteninformatik
Die Quanteninformatik oder Quanteninformationsverarbeitung ist die Wissenschaft von einer Informationsverarbeitung, die quantenmechanische Phänomene nutzt.
Neu!!: Komplexitätstheorie und Quanteninformatik · Mehr sehen »
Raymond Smullyan
Raymond Smullyan (2008) Raymond Merrill Smullyan (* 25. Mai 1919 in Far Rockaway, Queens, New York City; † 6. Februar 2017 in New York City) war ein US-amerikanischer Mathematiker und Logiker, der vor allem durch seine populärwissenschaftlichen Bücher mit logischen Rätseln und philosophischen Geschichten bekannt wurde.
Neu!!: Komplexitätstheorie und Raymond Smullyan · 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!!: Komplexitätstheorie und Reduktion (theoretische Informatik) · Mehr sehen »
Registermaschine
Die Registermaschine (RM) ist eine abstrakte Maschine der theoretischen Informatik.
Neu!!: Komplexitätstheorie und Registermaschine · Mehr sehen »
Ressource
Eine Ressource (von) ist Mittel, Gegebenheit wie auch Merkmal bzw.
Neu!!: Komplexitätstheorie und Ressource · Mehr sehen »
Richard E. Stearns
Richard Edwin „Dick“ Stearns (* 5. Juli 1936 in Caldwell, New Jersey) ist ein US-amerikanischer Informatiker, der 1993 gemeinsam mit Juris Hartmanis den Turing Award für seine Leistungen auf dem Gebiet der Komplexitätstheorie erhielt.
Neu!!: Komplexitätstheorie und Richard E. Stearns · Mehr sehen »
Richard M. Karp
Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston) ist ein amerikanischer Informatiker.
Neu!!: Komplexitätstheorie und Richard M. Karp · Mehr sehen »
RP (Komplexitätsklasse)
RP im Verhältnis zu anderen probabilistischen Komplexitätsklassen RP (manchmal auch nur mit R bezeichnet) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe eine Fehlerwahrscheinlichkeit von höchstens 1/2 hat.
Neu!!: Komplexitätstheorie und RP (Komplexitätsklasse) · Mehr sehen »
Sanjeev Arora
Sanjeev Arora Sanjeev Arora (* Januar 1968 in JodhpurGemäß den biographischen Angaben auf seiner Homepage http://www.cs.princeton.edu/~arora/bio.html, Indien) ist ein US-amerikanischer Informatiker indischer Herkunft.
Neu!!: Komplexitätstheorie und Sanjeev Arora · Mehr sehen »
Satz von Cook
Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie.
Neu!!: Komplexitätstheorie und Satz von Cook · Mehr sehen »
Sowjetunion
Die Sowjetunion (kurz SU,; vollständige amtliche Bezeichnung: Union der Sozialistischen Sowjetrepubliken, kurz UdSSR, russisch Audio) war ein von der Kommunistischen Partei der Sowjetunion (KPdSU) zentralistisch regierter, föderativer Vielvölker- und Einparteienstaat, dessen Territorium sich über Osteuropa und den Kaukasus bis nach Zentral- und über das gesamte Nordasien erstreckte.
Neu!!: Komplexitätstheorie und Sowjetunion · Mehr sehen »
Speedup-Theorem
In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme oder Beschleunigungssätze für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer Algorithmus bekannt ist.
Neu!!: Komplexitätstheorie und Speedup-Theorem · 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!!: Komplexitätstheorie und Stephen A. Cook · Mehr sehen »
Systemtheorie
Systemtheorie ist eine interdisziplinäre Betrachtungsweise, in der grundlegende Aspekte und Prinzipien von Systemen zur Beschreibung und Erklärung unterschiedlich komplexer Phänomene herangezogen werden.
Neu!!: Komplexitätstheorie und Systemtheorie · Mehr sehen »
Tautologie (Logik)
Eine Tautologie (von ταὐτό t’autó „dasselbe“ und -logie), auch Verum („wahr“) genannt, ist in der Logik eine allgemein gültige Aussage, das heißt eine Aussage, die aus logischen Gründen immer wahr ist.
Neu!!: Komplexitätstheorie und Tautologie (Logik) · Mehr sehen »
Teilmenge
Mengendiagramm: ''A'' ist eine (echte) Teilmenge von ''B''. Die mathematischen Begriffe Teilmenge und Obermenge beschreiben eine Beziehung zwischen zwei Mengen.
Neu!!: Komplexitätstheorie 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!!: Komplexitätstheorie und Theoretische Informatik · Mehr sehen »
Transcomputationales Problem
In der Komplexitätstheorie ist ein transcomputationales Problem ein Problem, das die Verarbeitung von mehr als 1093 (circa 2309) Bits erfordert.
Neu!!: Komplexitätstheorie und Transcomputationales Problem · Mehr sehen »
Tupel
Tupel (abgeleitet von mittellateinisch quintuplus ‚fünffach‘, septuplus ‚siebenfach‘, centuplus ‚hundertfach‘ etc.) sind in der Mathematik neben Mengen eine wichtige Art und Weise, mathematische Objekte zusammenzufassen.
Neu!!: Komplexitätstheorie und Tupel · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: Komplexitätstheorie und Turingmaschine · Mehr sehen »
Ungleichung
Eine Ungleichung ist ein Gegenstand der Mathematik, mit dem Größenvergleiche formuliert und untersucht werden können.
Neu!!: Komplexitätstheorie und Ungleichung · Mehr sehen »
Union-Theorem
Das Union-Theorem ist ein Ergebnis aus der Frühzeit der Forschung zur Komplexitätstheorie.
Neu!!: Komplexitätstheorie und Union-Theorem · Mehr sehen »
Verschlüsselungsverfahren
Mit einem Verschlüsselungsverfahren kann ein Klartext in einen Geheimtext umgewandelt werden (Verschlüsselung) und umgekehrt der Geheimtext wieder in den Klartext rückgewandelt werden (Entschlüsselung).
Neu!!: Komplexitätstheorie und Verschlüsselungsverfahren · Mehr sehen »
Wahrscheinlichkeitsmaß
Ein Wahrscheinlichkeitsmaß dient dazu, den Begriff der Wahrscheinlichkeit zu quantifizieren und Ereignissen, die durch Mengen modelliert werden, eine Zahl im Intervall zuzuordnen.
Neu!!: Komplexitätstheorie und Wahrscheinlichkeitsmaß · Mehr sehen »
Wort (theoretische Informatik)
In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets.
Neu!!: Komplexitätstheorie und Wort (theoretische Informatik) · Mehr sehen »
Wortproblem (Berechenbarkeitstheorie)
Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört oder nicht.
Neu!!: Komplexitätstheorie und Wortproblem (Berechenbarkeitstheorie) · Mehr sehen »
Wurzel (Mathematik)
Grafische Darstellung der Quadratwurzel-Funktion y.
Neu!!: Komplexitätstheorie und Wurzel (Mathematik) · 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!!: Komplexitätstheorie und Zeitkomplexität · Mehr sehen »
ZPP (Komplexitätsklasse)
Die Komplexitätsklasse ZPP beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine gibt, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt und folgende Eigenschaften besitzt.
Neu!!: Komplexitätstheorie und ZPP (Komplexitätsklasse) · Mehr sehen »
Zusammenhang (Graphentheorie)
Ein zusammenhängender Graph: Je zwei Knoten sind durch eine Kantenfolge verbunden. Exemplarisch ist eine Kantenfolge zwischen den Knoten v und w rot hervorgehoben. Der Zusammenhang ist ein mathematischer Begriff aus der Graphentheorie.
Neu!!: Komplexitätstheorie und Zusammenhang (Graphentheorie) · Mehr sehen »
