Wir wissen, dass DPLL-basierte SAT-Löser auf unbefriedigenden Instanzen von (Pigeon Hole-Prinzip) nicht richtig antworten , zB auf "Es gibt eine injektive Zuordnung von zu ": n + 1 nPHPPHP\mathrm{PHP}n+1n+1n+1nnn
Wenn wir einen großen (gerichteten) Graphen und einen kleineren Stammbaum , welche Komplexität ist am bekanntesten, um zu isomorphe Untergraphen von zu finden ? Mir sind Ergebnisse für Teilbaumisomorphien bekannt, bei denen sowohl als auch Bäume sind und bei denen eben ist oder eine begrenzte...
Hintergrund Eine Read-Once-Formel über eine Reihe von Gattern (auch Basis genannt) ist eine Formel, in der jede Eingabevariable einmal vorkommt. Einmal-Lese-Formeln werden üblicherweise über die De Morgan-Basis (die die 2-Bit-Gatter AND und OR und das 1-Bit-Gatter NOT aufweist) und die vollständige...
Betrachten wir eine Sammlung von Sätzen F = { F 1 , F 2 , ... , F n }F={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\} über einen Basissatz wo und , und sei eine positive ganze Zahl.U = { e 1 , e 2 , … , e n } U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\}| F i | |Fi||F_i| ≪ ≪\ll n nne i ∈ F iei∈Fie_i \in F_i kkk Das...
Dies ist eine Folgefrage zu dieser Frage über unendliche Graphen. Antworten und Kommentare zu dieser Frage listen Objekte und Situationen auf, die auf natürliche Weise durch unendliche Graphen modelliert werden. Es gibt aber auch zahlreiche Sätze über unendliche Graphen (siehe Kapitel 8 in Diestels...
Ich lerne selbst formale Methoden. Ich habe gehört, dass formale Methoden verwendet werden (und in der Regel nur verwendet werden), um unternehmenskritische Software zu erstellen (z. B. Nuklearreaktor-Controller, Flugzeug-Flug-Controller, Raumsonden-Controller). Deshalb bin ich daran interessiert,...
Das probabilistische Beweissystem wird allgemein als Einschränkung von , wobei Arthur nur Zufallsbits verwenden und nur untersuchen kann Bits des von Merlin gesendeten Proof-Zertifikats (siehe http://en.wikipedia.org/wiki/Interactive_proof_system#PCP
Gibt es einen linearen Time-In-Place-Riffle-Shuffle-Algorithmus? Dies ist der Algorithmus, den einige besonders geschickte Hände ausführen können: Ein Eingangsarray mit gerader Größe wird gleichmäßig aufgeteilt und die Elemente der beiden Hälften werden verschachtelt. Mathworld hat eine kurze Seite...
Ich interessiere mich allgemein für die von Baker-Gill-Solovay und Cohen verwendete Forcierungsmethode. Ich suche nach so vielen Quellen, wie ich in Bezug auf die Technik selbst oder ihre Verwendung in die Hände bekommen kann. Hat jemand
Für Systeme ohne abhängige Typen, wie das Hindley-Milner-Typensystem, entsprechen die Typen Formeln der intuitionistischen Logik. Dort wissen wir, dass es sich bei den Modellen um Heyting-Algebren handelt. Um eine Formel zu widerlegen, können wir uns auf eine Heyting-Algebra beschränken, bei der...
Bearbeiten: Da ich seit einer Woche keine Antworten / Kommentare mehr erhalten habe, möchte ich hinzufügen, dass ich froh bin, etwas über das Problem zu hören. Ich arbeite nicht in der Gegend, auch wenn es eine einfache Beobachtung ist, weiß ich es vielleicht nicht. Sogar ein Kommentar wie "Ich...
Ich war ein Kapitel in Lesen Lyah , die nicht wirklich Sinn für mich. Ich verstehe, dass Reißverschlüsse willkürlich eine baumähnliche Struktur durchqueren können, aber ich brauche eine Klärung darüber. Können Reißverschlüsse auf jede Datenstruktur verallgemeinert
Wenn Sie sich die rekursiven Kombinatoren im untypisierten Lambda-Kalkül ansehen, wie den Y-Kombinator oder den Omega-Kombinator: Es ist klar, dass all diese Kombinatoren eine Variable irgendwo in ihrer Definition duplizieren.ωY.==( λ x .xx )( λ x .xx )λ f.( λ x .f( xx ) )( λ x .f( xx )...
Man betrachte einen endlichen Satz über Elementen und ein unbekanntes monotones Prädikat über (dh für jedes , , wenn und dann ). . Ich kann auswerten, indem ich einen Knoten bereitstelle und herausfinde, ob P ( x ) gilt oder nicht. Mein Ziel ist es, die Menge der Knoten x ∈ X so genau zu bestimmen,...
Hintergrund Der externe Speicher oder das DAM-Modell definiert die Kosten eines Algorithmus durch die Anzahl der durchgeführten E / As (im Wesentlichen die Anzahl der Cache-Fehlschläge). Diese Laufzeiten werden im Allgemeinen in Form von MMM , der Speichergröße und BBB , der Anzahl der Wörter, die...
Bei dieser Frage geht es um Aussagenlogik, und alle Vorkommen von "Auflösung" sollten als "Aussagenauflösung" gelesen werden. Diese Frage ist etwas sehr Grundlegendes, aber sie hat mich eine Weile beschäftigt. Ich sehe Leute, die behaupten, dass die Auflösung der Aussagen vollständig ist, aber ich...
Es ist bekannt, dass die Minimierung der Größe eines regulären Ausdrucks PSPACE-vollständig ist, auch wenn wir einen DFA als Sprachspezifikation haben . Was sind die Ergebnisse, wenn die Sprache endlich ist? Man kann dieses Problem in zwei Modellen betrachten: Die Eingabe besteht aus allen...
Ich hatte gehofft, jemand könnte mir erklären, warum genau das Subset-Produktproblem stark NP-hart ist, während das Subset-Summenproblem schwach NP-hart ist. Subset Summe: Bei und , Gibt es eine Teilmenge so dass .X={x1,...,xn}X={x1,...,xn}X = \{x_1,...,x_n\}TTTX′X′X'∑i∈X′xi=T∑i∈X′xi=T\sum_{i\in...
In den letzten zwei Jahrzehnten wurde fantastisch an der Permanenten gearbeitet. Ich habe mich eine Weile über die Möglichkeit eines Smooth-P-Algorithmus für die Permanente von nichtnegativen Matrizen gewundert. Es gibt natürlich den berühmten JSV-Algorithmus, aber das ist ein fpras. Wenn man an...
Als Eingabe wird mir ein DAG GGG von Eckpunkten gegeben, wobei jeder Eckpunkt zusätzlich mit einigen .nnnxxxS(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Eine topologische Art von ist eine Bijektion von den Eckpunkten von nach so dass für alle , , wenn es einen Pfad von nach in dann . Ich...