Ist die folgende Graphklasse in der Literatur bekannt? Die Klasse von Graphen ist durch positive ganze Zahlen parametrisiert und , und enthält jeden Graph , so dass für jeden Scheitelpunkt , der Teilgraph von an allen Ecken im Abstand induzierte höchstens von in hat eine Baumbreite von höchstens .t...
Es ist bekannt, dass die minimale Größe von -Schaltungen, die die Paritätsfunktion genau berechnen, gleich 3 ( n - 1 ) ist . Der untere Grenznachweis basiert auf der Gate-Eliminierungsmethode.U2U2U_23 ( n - 1 )3(n-1)3(n-1) Kürzlich ist mir aufgefallen, dass die Gate-Eliminierungsmethode auch für...
Ich lese über Klassen von Graphen, für die Graph Isomorphism ( ) in . Ein solcher Fall sind die hier erläuterten Graphen der begrenzten Valenz (Maximum über Grad jedes Scheitelpunkts) . Aber ich fand es zu abstrakt. Ich wäre dankbar, wenn mir jemand Referenzen von Expository-Art vorschlagen könnte....
Kontext: Beziehungen zwischen Logik und Automaten Der Satz von Büchi besagt, dass die monadische Logik zweiter Ordnung über Strings (MSO) die Klasse der regulären Sprachen erfasst. Der Beweis zeigt tatsächlich, dass existenzielles MSO ( oder EMSO ) über Zeichenfolgen ausreicht, um reguläre Sprachen...
Es ist allgemein bekannt, dass der am meisten geladene Behälter mit hoher Wahrscheinlichkeit O(logn)O(logn)O(\log n) Bälle enthält , wenn Sie n Bälle in n Behälter werfen . Im Allgemeinen kann man nach m>nm>nm > n Bällen in nnn Behältern fragen . Eine Veröffentlichung von RANDOM 1998 von...
Mir wurde gesagt, dass es einige gute polynomielle Zeitalgorithmen gibt, um die Anzahl einfacher Pfade in einem gerichteten Graphen von einem gegebenen Startscheitelpunkt zu einem gegebenen Endscheitelpunkt t zu approximieren . Kennt jemand eine gute Referenz zu diesem Thema?sssttt Hintergrund: Das...
Während ich Dick Liptons Blog las, stieß ich gegen Ende seines Bourne-Factor- Posts auf folgende Tatsachen : Wenn für jedes nnn eine Beziehung der Form (2n)!=∑k=0m−1akbckk(2n)!=∑k=0m−1akbkck (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} wobei m=poly(n)m=poly(n)m = poly(n) , und jedes der akaka_k ,...
Ich werde mein Problem mit einem Beispiel vorstellen. Angenommen, Sie entwerfen eine Prüfung, die aus einer bestimmten Menge von nnn unabhängigen Fragen besteht (die die Kandidaten entweder richtig oder falsch beantworten können). Sie möchten sich für eine Punktzahl entscheiden, die für jede der...
Wie im Bereich der Arbeiten im ACM Journal on Experimental Algorithmic JEA . Welches waren die grundlegenden Arbeiten? Was sind die Hauptergebnisse? Wie zeichnen sie sich aus? Interessante Verbindungen zu anderen Bereichen der
Ein gemischtes Diagramm ist ein Diagramm, das sowohl gerichtete als auch ungerichtete Kanten haben kann. Das zugrunde liegende ungerichtete Diagramm wird erhalten, indem die Ausrichtungen der gerichteten Kanten vergessen werden, und in der anderen Richtung wird eine Ausrichtung eines gemischten...
X-freie Graphen sind solche, die keinen Graphen von X als induzierten Untergraphen enthalten. Ein Loch ist ein Zyklus mit mindestens 4 Eckpunkten. Ein ungerades Loch ist ein Loch mit einer ungeraden Anzahl von Eckpunkten. Ein Anti- Loch ist das Komplement eines Lochs. Die (ungeradzahligen,...
Angenommen, Sie haben zwei willkürlich mächtige Teilnehmer, die sich nicht vertrauen. Sie haben Zugriff auf Bit-Commitments (z. B. versiegelte Umschläge mit Daten, die ein Spieler dem anderen übergeben kann, die jedoch erst geöffnet werden können, wenn der erste Spieler dem zweiten einen Schlüssel...
Ich bin daran interessiert, ob es gute Expository-Artikel oder Umfragen gibt, auf die ich mich beziehen kann, wenn ich über Komplexitätsklassenoperatoren schreibe : Operatoren, die Komplexitätsklassen transformieren, indem sie ihnen beispielsweise Quantifizierer hinzufügen. Beispiele für Operatoren...
Das Zählen von Dreiecken in allgemeinen Diagrammen kann trivial in und ich denke, dass es schwierig ist, viel schneller zu arbeiten (Referenzen erwünscht). Was ist mit planaren Graphen? Das folgende unkomplizierte Verfahren zeigt, dass es in O ( n log n ) Zeit durchgeführt werden kann. Meine Frage...
π 1 : A × B → A π 2 : A × B → BA × B≜ ∀ & agr; .( A → B → α ) → αA×B≜∀α.(A→B→α)→α A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha π1: A × B → Aπ1:A×B→A\pi_1 : A \times B \to Aπ2: A × B → Bπ2:A×B→B\pi_2 : A \times B \to B Dies ist nicht so überraschend, obwohl die...
Es ist bekannt, dass zufällige CNF-Formeln über Variablen mit Klauseln mit hoher Wahrscheinlichkeit für eine ausreichend große Konstante erfüllt werden können (dh sie sind Widersprüche) . Zufällige CNF-Formeln (für groß genug) bilden somit eine natürliche Verteilung über nicht erfüllbare Boolesche...
Es gibt nur sehr wenige Informationen über das NP-vollständige Problem der Lösung der linearen Diophantingleichung in nicht-negativen ganzen Zahlen. Das heißt, gibt es eine Lösung in nicht-negativen zu der Gleichung a 1 x 1 + a 2 x 2 + . . . + a n x n = b , wo alle Konstanten positiv sind? Die...
Nehmen Sie einen gerichteten Graphen bei dem die Kanten mit einer natürlichen Zahl verziert sind. Wir wollen die Menge aller Pfade P zwischen zwei Eckpunkten v 1 und v 2 so, dass jede aufeinanderfolgende Kante im Pfad mit einer natürlichen Zahl verziert wird, die größer ist als die natürliche Zahl,...
Ist das folgende Manuskript öffentlich verfügbar? Dana Scott, 1969, Eine Theorie von berechenbaren Funktionen höheren Typs . Unveröffentlichte Seminarunterlagen, 7 Seiten, University of Oxford. In Abschnitt 8.1.2, Typen als Mengen , in Cardone & Hindley, 2006 History of Lambda-calculus and...
Eine Kantenabdeckung ist eine Teilmenge von Kanten eines Diagramms, sodass jeder Scheitelpunkt des Diagramms an mindestens eine Kante der Abdeckung angrenzt. Die folgenden beiden Papiere sagen , dass Zählflanke Abdeckungen ist #P -komplette: Eine einfache FPTAS für Zählflanke Covers und Generieren...