Wählen Sie eine Teilmenge der Spalten in der Matrix aus. Ist das einfach?

Ich möchte wissen, ob dieses Problem in Polynomzeit lösbar ist oder nicht.

Das Problem ist: Gegeben ist eine nichtnegative Ganzzahlmatrix mit der Größe und zwei nichtnegativen Ganzzahlnummern und . $2\times n$ $b<n$ $c$

Die Frage ist: Finden Sie eine Teilmenge der Kardinalitätsspalten höchstens so dass die Summe jeder Zeile über der Teilmenge der Spalten größer als . Geben Sie no zurück, wenn keine solche Teilmenge vorhanden ist. $b$ $c$

Ich kann nicht zeigen, dass es NP-schwer ist.

BEARBEITEN:

Mein Versuch, die Härte zu beweisen : Nach den Vorschlägen von Filmus habe ich versucht, PARTITION (eine Instanz wird durch die Menge nicht negativer Ganzzahlen ) auf mein Problem zu reduzieren. Ich habe natürlich versagt. Der Gedanke, den ich nicht verstanden habe, ist, wie die Partitionierung einer Reihe nicht negativer Ganzzahlen mit diesem Problem zusammenhängt? Ich meine, in meinem Problem möchte ich eine Teilmenge von auswählen , um etwas zu maximieren. Ich kann nicht sehen, wie dies eine Partition ist. Ich habe viele Gedanken ausprobiert, aber ich kann sie hier nicht alle schreiben: $\{a_1,\ldots,a_n\}$ $\{1,\ldots,n\}$

Ich habe versucht, die Matrix mit nur in der ersten Zeile und in der zweiten Zeile zu erstellen . $a_{2i}$ $a_{2i+1}$
Ich war es leid, die erste Reihe in aufsteigender Reihenfolge und die zweite Reihe in absteigender Reihenfolge zu sortieren.
Ich habe versucht, das in zwei Werte und zu teilen, so dass und dann die Matrix mit in der ersten Zeile und in der zweiten Zeile erstellt. $a_i$ $\alpha_i$ $\beta_i$ $a_i=\alpha_i+\beta_i$ $\alpha_i$ $\beta_i$

Kann mir jemand intuitiv erklären, wie ich PARTITION verwenden kann, um die NP-Härte meines Problems zu zeigen? Sie müssen die Lösung nicht angeben.

Meine Lösung zur Lösung des Problems :

Ich habe diese Lösung ausprobiert. Angenommen, ohne an Allgemeinheit zu verlieren, wird die erste Zeile der Matrix in aufsteigender Reihenfolge sortiert. (Die zweite Zeile der Matrix muss nicht sortiert werden, da das Problem sonst trivial ist.)

Nehmen Sie nun die letzten Spalten der Matrix. $b$

Wenn die Summe über der ersten Zeile kleiner als , sind wir fertig. Es gibt keine Lösung. $c$
Andernfalls ist die Summe der ersten Zeile über den letzten Spalten größer als . Dann sehen Sie die Summe der zweiten Zeile.
- Wenn die Summe der zweiten Zeile über den letzten Spalten größer als , sind wir fertig. Geben Sie die letzten Spalten zurück. $b$ $c$ $b$
- Andernfalls ist die Summe der ersten Zeile über den Spalten größer als aber die Summe der zweiten Zeile über den Spalten ist kleiner als . Hier haben wir ein Problem. $b$ $c$ $b$ $c$

algorithms complexity-classes Brika
quelle

An dieser Stelle ist es schwierig, einen Hinweis zu geben, ohne die Lösung preiszugeben.

Yuval Filmus

Ich habe die Lösung zu meiner Antwort hinzugefügt. Versuchen Sie es das nächste Mal stärker, bevor Sie aufgeben.

Yuval Filmus

Antworten:

Hinweis: Zeigen Sie, dass es NP-schwer ist, indem Sie von EQUAL-PARTITION, der Variante von PARTITION, reduzieren, bei der beide Teile gleich groß sein müssen (siehe eine Frage zu math.se ).

Betrachten Sie bei einer Instanz von EQUAL-PARTITION (mit ) eine Instanz Ihres Problems mit , für groß genug (ich denke, dass ausreichen sollte) und die Matrix $\{x_1,\ldots,x_n\}$ $x_i > 0$ $b = n/2$ $c = \sum_i (M+x_i)/2 - 1$ $M$ $M = \max_i x_i$

[\begin{matrix} M + x_{1} & \dots & M + x_{n} \\ M + \frac{\sum_{i} x_{i}}{n / 2} - x_{1} & \dots & M + \frac{\sum_{i} x_{i}}{n / 2} - x_{n} \end{matrix}] .

$\begin{bmatrix} M+x_1 & \cdots & M+x_n \\ M+\frac{\sum_i x_i}{n/2}-x_1 & \cdots & M+\frac{\sum_i x_i}{n/2}-x_n \end{bmatrix}.$

Yuval Filmus
quelle

Vielen Dank. Ich habe versucht, es mit PARTITION zu tun, wie Sie vorgeschlagen haben. Bei einer Instanz von PARTITION ist . Ich erstelle eine Instanz meines Problems wie folgt: (ich nehme an, dass ist), und die Matrix ist gegeben durch . PARTITION ist gelöst, wenn das Problem gelöst ist, bei dem die Teilmenge der Spalten diejenigen mit Indizes in der ersten Partition oder zweiten Partition sind. Ich denke das ist nicht genau richtig, oder?

A = {a_{1}, \dots, a_{n}}

$A=\{a_1,\ldots,a_n\}$

b = n / 2

$b=n/2$

n

$n$

c = \sum_{i = 1}^{n} a_{i} / 2

$c=\sum_{i=1}^na_i/2$

[\begin{matrix} a_{1} & \dots & a_{n} \\ a_{1} & \dots & a_{n} \end{matrix}]

$\begin{bmatrix}a_1 & \ldots & a_n\\ a_1 & \ldots & a_n\end{bmatrix}$

Brika

Ihre Instanz ist leicht zu lösen - nehmen Sie die größten nicht negativen s und , ob sie mindestens . Also nein, es funktioniert nicht. Versuchen Sie beim nächsten Mal, einen formellen Beweis zu schreiben. Überprüfen Sie auch die genaue Definition von PARTITION (z. B. auf Wikipedia).

n / 2

$n/2$

a_{i}

$a_i$

\sum_{i} a_{i} / 2

$\sum_i a_i/2$

Yuval Filmus

@ Yuval. Die Matrix hat nicht negative Einträge, nicht wahr?

Zighalo

Ah - ich habe diesen Zustand verpasst. Aber vielleicht kann die Reduzierung irgendwie angepasst werden.

Yuval Filmus

@Brika Nicht unbedingt. Die Idee funktioniert, wenn sie entsprechend modifiziert wird.

Yuval Filmus