Der folgende Begriff eines Destillationsalgorithmus stammt aus "Über Probleme ohne Polynomkerne". Es sei eine Sprache gegeben. Ein Destillationsalgorithmus für nimmt eine gegebene Liste von Eingabezeichenfolgen und berechnet eine Ausgabezeichenfolge :LLL{ x i } i ∈ [ t ] yLLL{xi}i∈[t]{xi}i∈[t]\{...
Let eine Sprache sein, und definiert f L : A * × A * → { 0 , 1 } von F L ( x , y ) = 1 genau dann , wenn x ⋅ y ∈ L . Ich suche eine Referenz für:L⊆A∗L⊆A∗L \subseteq A^*fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\}fL(x,y)=1fL(x,y)=1f_L(x, y) = 1x⋅y∈Lx⋅y∈Lx\cdot y \in L Vorschlag....
Wir haben ein Problem und haben einen Algorithmus gefunden, der 2-nexptime zu sein scheint. Ich würde gerne bekannte 2-Nexptime-vollständige Probleme finden, um eine Untergrenze zu finden. Ich fand in der Literatur hauptsächlich zwei solche Probleme: ob PCP als Lösung mit einer Größe von weniger...
Ich stieß auf einen Artikel in Science "Memcomputing NP-vollständige Probleme in der Polynomzeit unter Verwendung von Polynomressourcen und kollektiven Zuständen" , der einige ziemlich erstaunliche Behauptungen aufstellt . Memcomputing ist ein neuartiges Nicht-Turing- Berechnungsparadigma, bei dem...
Sei ein Alphabet der Größe 2 und betrachte minimale DFAs, deren Größe durch höchstens m begrenzt ist . Es sei f ( m ) die Anzahl verschiedener solcher minimaler DFAs.ΣΣ\Sigma222mmmf(m)f(m)f(m) Können wir eine geschlossene Formel für ?f(m)f(m)f(m) In Anbetracht dessen für Die Übergangsfunktion eines...
Meine Frage bezieht sich auf die Sätze 4.1 und 4.2 in "Geometric Complexity Theory V" . Der erste Satz besagt, dass es einen EXPSPACE- Algorithmus zum Konstruieren von hsop für (siehe Definitionen in der Arbeit) auf (tatsächlich auf einem beliebigen algebraisch geschlossenen Feld des Merkmals Null)...
Wie stark ist es angesichts starker Generatoren für eine Gruppe die auf Bitstrings der Länge und ein Element wirkt , das lexikographisch minimale Element von zu berechnen ? Umlaufbahn von in ?( G ≤ S.n, ∗ )(G≤S.n,∗)(G \leq S_n, *)nnns ∈ { 0 , 1 }ns∈{0,1}}ns \in \{0, 1\}^nG ....
Sei eine Komplexitätsklasse und BP- C das randomisierte Gegenstück von C, das auf die gleiche Weise definiert ist , wie BPP in Bezug auf P definiert ist . Formal stellen wir polynomiell viele zufällige Bits bereit und akzeptieren eine Eingabe, wenn die Wahrscheinlichkeit zu akzeptieren über 2...
Betrachten wir für eine feste Sprache in einem Alphabet A das folgende Problem, das ich L- INTERLEAVING nenne :LL.LAEINALLL Eingabe: zwei Wörter u,v∈A∗u,v∈A∗u, v \in A^* Output: ob eine existiert Verschachtelung von und v , die in ist L .uuuvvvLLL Hier ist eine Verschachtelung von zwei Wörtern und...
Sei ein endliches Alphabet. Ein Code X über Σ ist eine Teilmenge von Σ * , so dass jedes Wort in X * eindeutig als eine Verkettung von Worten dargestellt werden , in X . Ein Code X ist endlich, wenn | X | ist endlich. Was ist über (minimale) Automaten bekannt, die X ∗ für einen endlichen Code X...
Bei einer vollständigen DFA , können wir eine Sammlung von Funktionen definieren , f eine für jedes a ∈ Γ und mit f ein : Q → Q , f einen ( q ) = δ ( q , a ) . Wir können diesen Begriff auf ein Wort w = a 1 , ⋯ , a m und f w verallgemeinernA=(Q,Γ,δ,F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta,...
Quasi-Polynomialzeit, kurz QP, ist eine Komplexitätsklasse auf deterministischen Turing-Maschinen. Hier ist die genaue Definition: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp Während βP eine Komplexitätsklasse mit begrenztem Nichtdeterminismus ist. Hier ist die genaue Definition:...
Gibt es eine bekannte berechenbare transzendentale Zahl, so dass ihre te Ziffer in Polynomzeit berechenbar ist, aber nicht in ?O ( n
Gibt es einen Rahmen / Formalismus, der Rechenmodelle definiert, die auf anderen Proteinen als Adlemans DNA-Modell oder dieser Arbeit von Cherry und Qian basieren
Ich war eine Weile neugierig auf Turingmaschinen mit genau einem Band und genau 3 Zuständen (nämlich dem Startzustand , dem Annahmezustand q a c c e p t und dem Ablehnungszustand q r e j e c t ). Beachten Sie, dass ich beliebige (endliche) Bandalphabete zulasse (dh das Bandalphabet ist nicht auf...
Was ist Razborovs Approximationsmethode? Kann jemand einen Überblick auf hoher Ebene und die Intuition dahinter
Ich suche nach einer Liste von NP-harten Optimierungsproblemen, bei denen es aktive Forschung in der praktischen Heuristik gibt, um sie zu lösen, und es gibt gemeinsame Benchmarks, die die Leute zu schlagen versuchen. Beispiele sind: Phylogenetische Baumrekonstruktion (zum Beispiel hier heuristisch...
Ich erhalte einen Graphen mit einer Baumbreite k und einem beliebigen Grad und möchte einen Teilgraphen H von G (nicht unbedingt einen induzierten Teilgraphen) finden, so dass H einen konstanten Grad hat und seine Baumbreite so hoch wie möglich ist. Formal ist mein Problem das Folgende: Nachdem ich...
SMT-Löser wie Z3 oder Boolector verwenden komplexe Heuristiken, um Probleme zu lösen. Dies macht es jedoch auch sehr schwierig, die Leistung eines solchen Lösers für ein bestimmtes Problem vorherzusagen. Meine Frage lautet also: Frage Gibt es eine Möglichkeit, die Leistung eines SMT-Lösers für...
Bei gegebener Koprime a,ba,ba, b können Sie schnell berechnenminx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Hier sind x,yx,yx, y ganze Zahlen. Offensichtlich ergibt x=y=0x=y=0x = y = 0 eine uninteressante Antwort; Wie nahe können diese Kräfte im Allgemeinen kommen? Wie berechnen...