Arithmetische Schaltungen mit

Stellen Sie sich eine Schaltung vor, die in Zahlen als Eingaben verwendet und Gatter hat, die aus den Funktionen , , und $[0,1]$ $\max(x, y)$ $\min(x, y)$ $1 - x$ . Der Ausgang der Schaltung ist dann auch eine Zahl in. $\frac{x+y}{2}$ $[0,1]$

Weiß jemand, ob dieses Modell oder ein eng verwandtes Modell untersucht wurde?

Insbesondere versuche ich, das Erfüllbarkeitsproblem für diese Schaltung zu lösen, nämlich den Maximalwert zu berechnen, der von dieser Schaltung erreicht werden kann (sie erreicht tatsächlich ein Maximum, da sie eine kontinuierliche Funktion in einem kompakten Bereich darstellt).

Bemerkung: Mein Studium dieses Modells erfolgt über gewichtete zeitliche Logiken, daher können auch Modelle nützlich sein, die sich auf letztere beziehen.

arithmetic-circuits Shaull
quelle

Sicher ist dieses Problem NP-schwer. (Über die Erfüllbarkeit: Sie haben

und

, mit denen Sie AND, OR und NOT ausführen können.) Ihre Frage ist also, ob dieses Problem in NP liegt oder nicht ? Die Entscheidungsfrage, ob eine solche Schaltung einen Eingang hat, der den Wert 1 ergibt, scheint in NP zu sein, da es, wenn es einen solchen Eingang gibt, einen gibt, der 0/1 ist.

x \lor y \equiv max {x, y}

$x\vee y \equiv \max\{x,y\}$

\neg x \equiv 1 - x

$\neg x \equiv 1 - x$

Neal Young

Wenn wir nicht deterministisch einen der

möglichen Wahrheitswerte für

wählen , wobei

alle Knotenpaare sind, so dass ein

oder

Knoten in der Schaltung erscheint, dies wird zu einem linearen Programmierproblem, das in P lösbar ist. Somit ist die Entscheidungsversion des ursprünglichen Maximierungsproblems in NP. (Dies ist eine Variante des Erfüllbarkeitsproblems in der Łukasiewicz-Logik. Weitere Informationen finden Sie in Hanikovás Kapitel im Handbuch der mathematischen Fuzzy-Logik.)

\leq 2^{n}

$\le2^n$

x \leq y

$x\le y$

x, y

$x,y$

min (x, y)

$\min(x,y)$

max (x, y)

$\max(x,y)$

Emil Jeřábek 3.0

@Shaull: Lass es mich genauer beschreiben. Sei

die Knoten der Schaltung, die Min- oder Max-Gates sind (hier ist

durch die Größe der Schaltung begrenzt), und seien

und

die Eingangsknoten des Gates

. Wählen Sie für jedes

eine zusätzliche Bedingung

oder

. Es sind

{a_{i} : i < m}

$\{a_i:i<m\}$

m

$m$

b_{i}

$b_i$

c_{i}

$c_i$

a_{i}

$a_i$

i < m

$i<m$

b_{i} \leq c_{i}

$b_i\le c_i$

c_{i} \leq b_{i}

$c_i\le b_i$

2^{m}

$2^m$ solche Entscheidungen. Wenn eine solche Auswahl festgelegt ist, können Sie die Schaltung vereinfachen, indem Sie

durch

oder

ersetzen. Daher wird daraus ein System linearer Gleichungen, deren Variablen die ursprünglichen Variablen des Problems sind, und zusätzliche Variablen, die diesen entsprechen. ..

a_{i}

$a_i$

b_{i}

$b_i$

c_{i}

$c_i$

Emil Jeřábek 3.0

... Knoten in der Schaltung. Schließen Sie

Ungleichungen ein, die angeben, dass die zusätzlichen Bedingungen erfüllt sind, Ungleichungen, die die ursprünglichen Variablen auf

, und eine Ungleichung, die angibt, dass der Ausgabeknoten den Wert

. Dann ist dies ein lineares Programm, das von der Wahl der zusätzlichen Einschränkungen abhängt, und die Schaltung erreicht den Wert

wenn eine Auswahl der Bedingungen existiert, so dass das zugehörige lineare Programm eine Lösung hat.

m

$m$

[0, 1]

$[0,1]$

\geq u

$\ge u$

\geq u

$\ge u$

Emil Jeřábek 3.0

Beachten Sie auch, dass der optimale Wert eines linearen Programms an einem Scheitelpunkt des Polytops erreicht wird. Dies bedeutet, dass der Nenner der optimalen Lösung als Determinante einer Matrix der Dimension

ausgedrückt werden kann, deren Einträge Ganzzahlen konstanter Größe sind, und dass es in jeder Zeile nur

Einträge ungleich Null gibt, und als solche ist durch

O (n)

$O(n)$

O (1)

$O(1)$

2^{O (n)}

$2^{O(n)}$

Emil Jeřábek 3.0

Dieses Problem ist NP-schwer.

Sie können 3-SAT mit den Gates min ( x , y ), max ( x, y ) und 1− x erhalten .

Was wir wollen, ist, ein 3-SAT-Problem auf eine Schaltung zu reduzieren, für die Sie 1 erhalten können, wenn alle Variablen erfüllt sind, und Sie können sonst nur etwas erreichen, das streng kleiner als 1 ist.

Wir können erzwingen, dass alle Variablen entweder 0 oder 1 sind, indem wir mindestens viele Ausdrücke verwenden und diese Ausdrücke auf max ( x , 1 - x ) setzen.

Nun setzen wir für jede Klausel im 3-SAT-Problem x ∨ y ∨ z den Ausdruck max ( x , y , z ) auf das Minimum.

Ich weiß nicht, was der optimale Wert für ein nicht erfüllbares 3-SAT-Problem ist, aber es wird streng weniger als 1 sein.

Peter Shor
quelle

Ja, NP-Härte ist die "einfache Richtung", wie in einem Kommentar oben angegeben. Wenn Sie nicht das durchschnittliche Gate verwenden, sondern nur min und max, können Sie leicht zeigen, dass der Maximalwert 1 ist, wenn die entsprechende Boolesche Schaltung erfüllt werden kann, und 1/2, wenn Sie einfach 1/2 an alle anschließen die Variablen). Wie auch immer, das Problem wurde in den obigen Kommentaren gelöst.

Shaull

Arithmetische Schaltungen mit

Antworten: