Lösen einer linearen Diophantingleichung ungefähr

Betrachten Sie das folgende Problem:

Eingabe : eine Hyperebene $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$ , gegeben durch einen Vektor $\mathbf{a} \in \mathbb{Z}^n$ und $b \in \mathbb{Z}$ in binärer Standarddarstellung.

$\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

In der obigen Notation ist für und definiert als , dh es ist der natürliche euklidische Abstand zwischen einer Menge von Punkten und einem einzelnen Punkt . $d(\mathbf{x}, S)$ $\mathbf{x} \in \mathbb{R}^n$ $S \subseteq \mathbb{R}^n$ $d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$

In Worten, wir erhalten eine Hyperebene und suchen den Punkt im Ganzzahlgitter, der der Hyperebene am nächsten liegt.

Die Frage ist:

Wie komplex ist dieses Problem?

Beachten Sie, dass Polynomzeit hier Polynom in der Bitgröße des Eingangs bedeutet. Soweit ich sehen kann, ist das Problem auch in zwei Dimensionen interessant. Dann ist es nicht schwer zu erkennen, dass es ausreicht, nur die Lösungen $(x_1, x_2)$ mit $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ aber das sind superpolynomiell viele Optionen.

Ein eng verwandtes Problem ist das Lösen einer linearen diophantinen Gleichung, dh das Finden eines so dass oder das Bestimmen, dass kein solches existiert. Das Lösen einer linearen Diophantingleichung ist also gleichbedeutend mit der Feststellung, ob für das oben definierte Problem eine Lösung mit dem Wert 0 vorliegt. Eine lineare Diophantingleichung kann in Polynomzeit gelöst werden; Tatsächlich können sogar Systeme linearer diophantiner Gleichungen in Polynomzeit gelöst werden, indem die Smith-Normalform der Matrix berechnet wird , die das System ergibt. Es gibt polynomielle Zeitalgorithmen, die die Smith-Normalform einer Ganzzahlmatrix berechnen, die erste, die durch gegeben ist $\mathbf{x} \in \mathbb{Z}^n$ $\mathbf{a}^T\mathbf{x} = b$ $\mathbf{x}$ $\mathbf{A}$ Kannan und Bachem .

Um einen Einblick in lineare diophantische Gleichungen zu erhalten, können wir den zweidimensionalen Fall noch einmal betrachten. Es ist klar, dass es keine genaue Lösung gibt, wenn nicht teilt . Wenn , können Sie den erweiterten GCD-Algorithmus ausführen, um zwei Zahlen und so zu erhalten, dass und und . Jetzt können Sie sehen, wie sich die ungefähre Version unterscheidet: Wenn nicht teilt , wie finden wir die Ganzzahlen $\mathsf{gcd}(a_1, a_2)$ $b$ $b$ $s$ $t$ $a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$ $x_1 = sb/\mathsf{gcd}(a_1, a_2)$ $x_2 = tb/\mathsf{gcd}(a_1, a_2)$ $\mathsf{gcd}(a_1, a_2)$ $b$ $x_1, x_2$ so dass der Abstand zwischen $(x_1, x_2)$ und der Linie $a_1x_1 + a_2x_2 =b$ minimiert wird?

Das Problem klingt für mich ein bisschen wie das nächstliegende Vektorproblem in Gittern, aber ich sehe keine offensichtliche Reduktion von einem Problem zum anderen.

cc.complexity-theory optimization linear-algebra integer-lattice Sasho Nikolov
quelle

Ist die Annäherung an gute simultane diophantische Näherungen nahezu NP-hart , C Rössner und JP Seiffert, MFCS 96, um Ihre Frage zu beantworten?

Kai

Nein, das ist nicht der Fall: Die Diophantin-Approximation ist ein anderes Problem als die Lösung einer Diophantin-Gleichung. In einem diophantinen Approximationsproblem erhalten Sie reelle Zahlen, und Sie möchten sie alle mit einer einzelnen ganzen Zahl multiplizieren, so dass alle von einer ganzen Zahl innerhalb von . Das Problem besteht darin, den optimalen Kompromiss zwischen der Größe von und . Ich sehe keinen Zusammenhang zwischen meinem Problem und diesem.

n

$n$

Q

$Q$

ϵ

$\epsilon$

Q

$Q$

ϵ

$\epsilon$

Sasho Nikolov

Was ist Ihr Eingabeformat? Es scheint, als wären zwei Koordinatenwerte von inkommensurat, dann ist das fragliche Minimum Null (schneide mit der entsprechenden zweidimensionalen Ebene, um eine Gleichung der Form mit und incommensurat zu erhalten , dh irrational, und verwenden dann die Standard - Ergebnisse auf zu zeigen , dass die Leitung zum Gitterpunkten beliebig nahe passiert.

a

$\mathbf{a}$

s x + t y = w

$sx+ty=w$

s

$s$

t

$t$

α \equiv \frac{s}{t}

$\alpha \equiv \frac{s}{t}$

{n α} (\mod 1)

$\left\{n\alpha\right\}\pmod 1$

Steven Stadnicki

Dies bedeutet insbesondere, dass Ihre 'min' eine 'inf' sein sollte (da Sie unendlich viele Punkte übernehmen) und das Problem, ob unterscheidet sich von der Frage, ob mit . Dies bedeutet, dass die Koeffizienten von rationale Zahlen sein müssen, damit das Problem keine triviale Lösung findet. Dann scheint das Problem eine sehr euklidische Form anzunehmen, die eng an mehrdimensionale GCD-Algorithmen gekoppelt ist. Vermisse ich etwas?

i n f d (x, H) = 0

$\mathrm{inf}\ d(\mathbf{x},H)=0$

x

$\mathbf{x}$

d (x, H) = 0

$d(\mathbf{x},H)=0$

a

$\mathbf{a}$

Steven Stadnicki

@StevenStadnicki richtig. Sie können annehmen, dass und (das werde ich der Frage hinzufügen, ich muss es verpasst haben). Die Eingabe erfolgt in Standard-Binärdarstellung. Die Frage ist auch dann interessant, wenn . dann ist es ausreichend, alle möglichen Lösungen mit , aber die Bruteforce-Suche wird in der binären Darstellung von superpolynomial sein .

a \in Z^{n}

$\mathbf{a} \in \mathbb{Z}^n$

b \in Z

$b \in \mathbb{Z}$

n = 2

$n = 2$

(x_{1}, x_{2})

$(x_1, x_2)$

x_{1} \leq | a_{1} | / g c d (a_{1}, a_{2})

$x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$

a_{1}, a_{2}

$a_1, a_2$

Sasho Nikolov

Gut, nachdem ich mehr darüber nachgedacht habe, glaube ich, dass ich eine explizite Reduktion von diesem Problem auf erweitertes GCD habe; Ich werde es im Fall erklären , aber ich glaube, dass es sich auf beliebiges . Beachten Sie, dass dies ein ergibt , das den Abstand zur Hyperebene minimiert, aber nicht unbedingt den kleinsten (es gibt tatsächlich unendlich viele Werte, die den gleichen Mindestabstand erreichen) - ich glaube, das letztere Problem ist auch machbar, habe aber noch nicht wirklich darüber nachgedacht. Der Algorithmus basiert auf einigen einfachen Prinzipien: $n=2$ $n$ $\mathbf{x}$ $\mathbf{x}$

Wenn , dann ist die Menge der Werte, die von werden, genau ; Außerdem können Werte und mit effizient gefunden werden (dies ist genau der erweiterte euklidische Algorithmus). $g=\mathrm{GCD}(a_1, a_2)$ $\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$ $\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$ $x_1$ $x_2$ $a_1 x_1 + a_2 x_2 = g$
Der minimale Abstand von der Hyperebene zu einem Punkt auf dem Gitter ist der minimale Abstand von einem Punkt auf dem Gitter zur Hyperebene (offensichtlich, aber eine nützliche Umkehrung des Problems).
Der Abstand von einem gegebenen Punkt zur Hyperebene ist proportional zu(Insbesondere ist es das -fache dieses Werts. Da jedoch das Multiplizieren aller Abstände mit diesem Wert keine Auswirkung auf die Position des Minimums hat, können wir den Normalisierungsfaktor ignorieren.) $\mathbf{x}$ $\mathbf{a}\cdot\mathbf{y} = b$ $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ $1/|\mathbf{a}|$

Dies schlägt die folgende Prozedur vor:

Berechne zusammen mit so dass . $g=\mathrm{GCD}(a_1,a_2)$ $x^0_1, x^0_2$ $a_1x^0_1+a_2x^0_2 = g$
Berechne und berechne ; ist der (skalierte) Mindestabstand vom Gitter zur Hyperebene. Let entweder oder ( , es sei denn ein Vielfaches von ist ) in Abhängigkeit von der man erreicht den minimalen Abstand. $r = \left\lfloor{b\over g}\right\rfloor$ $d =\min(b-rg, (r+1)g-b)$ $d$ $s$ $r$ $r+1$ $=\left\lceil{b\over g}\right\rceil$ $b$ $g$
Berechne und ; dann ist das nächste Vielfache von zu und somitErreicht das Minimum dieser Distanz über alle Gitterpunkte. $x_1 = sx^0_1$ $x_2 = s x^0_2$ $\mathbf{a}\cdot\mathbf{x} = sg$ $g$ $b$ $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$

Soweit ich weiß, sollte das gleiche Verfahren in beliebigen Dimensionen korrekt funktionieren. Der Schlüssel ist, dass die dimensionale GCD immer noch Bezouts Identität erfüllt. Um den Mindestabstand zu einem Gitterpunkt zu finden, muss nur das nächste Vielfache von zu . $n$ $g$ $b$

Steven Stadnicki
quelle

Lösen einer linearen Diophantingleichung ungefähr

Antworten: