Ermitteln einer Menge durch Kreuzungsvergleich

8

Das folgende Problem ist kürzlich aus meiner Forschung hervorgegangen, und ich möchte fragen, ob jemand weiß, ob dieses Problem zuvor in Betracht gezogen wurde oder von irgendetwas gehört hat, das damit zusammenhängen könnte.

Die allgemeine Einstellung ist die folgende. Wir erhalten F , eine Familie von t Teilmengen von {1,2,...,n} für einen Parameter t (ich interessiere mich am meisten für den Fall, dass t=n/2 ). Es gibt einen Gegner, der einen Satz in F auswählt, der mit S . Unsere Aufgabe ist es herauszufinden, was S ist. Zu diesem Zweck dürfen wir zwei beliebige Sätze in F an den Gegner senden , z. B. A und Bund der Gegner gibt A wenn |EINS.||B.S.|und B. wenn |B.S.||EINS.|. Beachten Sie, dass wenn |EINS.|=|B.S.|dann kann der Gegner entweder EIN oder ausgeben B..

Dieses Problem kann trivial gelöst werden, wenn es uns egal ist, wie viele Abfragen wir stellen können, da beim Vergleich aller Mengenpaare S. die einzige Menge ist, die beim Senden einer Abfrage immer vom Gegner zurückgegeben wird (S.,B.) , für jeden B.S. . Unser Ziel ist es jedoch, die Anzahl der Abfragen zu minimieren.

Mein Ziel ist es zu zeigen, dass dieses Problem entweder mit Ö(pÖly(n)) Abfragen gelöst werden kann oder dass eine superpolynomielle Anzahl von Abfragen erforderlich ist. Ich interessiere mich besonders für den Fall, dass F. die Menge aller n/.2 Teilmengen von {1,...,n}} .

Alle Hinweise auf alles, was damit zu tun hat, sind willkommen.

Danu
quelle
1
Können Sie die Bedingung "Gegner kann alles beantworten" klarstellen? Meinst du, dass die Antwort entweder wird ? A S | | B S | oder | B S | | A S | und das, da beide wahr sind, wenn | A S | = | B S | kann jede Antwort gegeben werden? |EINS.||B.S.||BS||AS||AS|=|BS|
mjqxxxx
1
Warum ist die triviale Lösung richtig? Sicherlich wird auch jede Obermenge von S | erfüllen S 'S | | B S | für alle B S . S.'S.|S.'S.||B.S.|B.S.'
mjqxxxx
@mjqxxxx: Danke für deine beiden Kommentare. Ich habe die Frage umformuliert, um sie klarer zu machen.
Danu

Antworten:

10

Dies ist eine Variation des berühmten Puzzles, eine gefälschte Münze mithilfe der Waage zu finden . Bevor wir jedoch fortfahren, lösen wir zunächst die Frage, da die Technik zur Lösung auch nützlich ist, um den Zusammenhang mit dem Problem mit gefälschten Münzen zu erkennen.

Angenommen, die Abfragesätze A und B müssen nicht aus der Familie F stammen . Dann können Sie die Menge S durch höchstens Abfragen wie folgt finden. Stellen Sie Abfragen ({ a }, { b }) für 1 ≤ a < bn . Beachten Sie, dass jedes Element i ∈ {1,…, n } in n −1 Abfragen verwendet wird. Wenn ein Element i zu S gehört , wird die Menge { i } zumindest dann beantwortet, wenn der Gegner nicht zu S gehört ( n(n2)=Ö(n2)(n2)und daher wird die Menge { i } mindestens n - t Mal beantwortet . Wenn ein Element i nicht zu S gehört , kann die Menge { i } nicht beantwortet werden, wenn der Gegner zu S gehört , und daher wird die Menge { i } höchstens n - t - 1 Mal beantwortet . Wenn wir also zählen, wie oft jeder Satz beantwortet wird, können wir den gesamten Satz S bestimmen .

Dies erfordert Abfragesätze, die nicht aus der Familie F stammen , was im Problem nicht zulässig ist. Wir können dies jedoch umgehen, indem wir beiden Seiten dieselben t −1-Elemente hinzufügen . Anstatt beispielsweise die Abfrage ({1}, {2}) durchzuführen, können wir die Abfrage ({1,3,4,…, t +1}, {2,3,4,…, t +1) durchführen }). Daher kann das Problem durch O ( n 2 ) -Abfragen gelöst werden.

Jetzt beginnt der lustige Teil. Betrachten Sie n Münzen mit den Bezeichnungen 1,…, n und t als Fälschungen und etwas schwerer als die echten Münzen. Alle gefälschten Münzen haben das gleiche Gewicht. Sie müssen den Satz S der Etiketten der t gefälschten Münzen finden, indem Sie eine Waage nur Poly ( n ) mal verwenden. Jedes Mal, wenn Sie eine Waage verwenden, können Sie höchstens min { t , n - t } Münzen auf jede Seite der Waage legen . Die Waage ist etwas ungenau in dem Sinne, dass bei gleichem Gewicht der beiden Seiten beide Seiten nach unten gehen können (kontrovers). Wie ich hoffe, dass Sie jetzt sehen können, ist dies genau das gleiche Problem wie die Frage.

Bearbeiten : Revision 4 und früher hatte den einen oder anderen Fehler (oops) in der genauen Verbindung zum gefälschten Münzpuzzle.

Tsuyoshi Ito
quelle
Dies beantwortet meine Frage gut! Vielen Dank auch für die Verbindung zum Problem mit gefälschten Münzen.
Danu
@ Tsuyoshi Großartig ... Ich dachte, es war exponentiell! Können Sie zeigen, wie der Algorithmus - im Fall von n = 4, t = 2 ... - in n ^ 2 Abfragen zwischen Lösung {1,2} und Lösung {1,3} unterscheiden kann (siehe alle möglichen Abfragen und möglich Antworten in meinem Beispiel ausgleichen)?
Marzio De Biasi
2
@Vor: Ich denke, dass ich in der Antwort klar genug angegeben hatte, wie das geht. Wenn ein Teil unklar ist, erkläre ich ihn gerne oder schreibe ihn neu.
Tsuyoshi Ito
@Vor: So startet der Algorithmus nicht. Ich empfehle Ihnen, die Antwort sorgfältig zu lesen, insbesondere den zweiten Absatz (der eine Lösung für die entspannte Version des Problems beschreibt, bei der Abfragesätze nicht auf Sätze in F beschränkt sind). Wir machen zuerst Abfragen und treffen dann eine Entscheidung. Wir „pflücken“ bis zum letzten Schritt nichts. (n2)
Tsuyoshi Ito
1
@Vor: Was Ihren Kommentar um 22:02 UTC betrifft, wenn F die Familie aller Teilmengen der Größe t (1 ≤ t ≤ n - 1) wie in der ursprünglichen Frage ist und der Gegner eine Lüge erzählen kann, wenn der absolute Unterschied zwischen | A∩S | und | B∩S | ist höchstens 1, dann kann der Gegner so tun, als ob S = [t] wäre, wenn die wahre Antwort S = [t - 1] ∪ {t + 1} ist, und daher kann die Menge S im Allgemeinen selbst mit exponentiell nicht eindeutig bestimmt werden viele Fragen.
Tsuyoshi Ito
2

... ähm ... Ich versuche einen Polynomalgorithmus herauszufinden ... arbeite noch daran ... aber ich denke, das Problem sollte besser umformuliert werden, da es Fälle gibt, in denen es unmöglich ist zu gewinnen (zumindest) wenn F die Familie aller Teilmengen ist)

Zum Beispiel:

Let n=3

F={{1},{2},{3},{1,2},{1,3},{2,3}}

Queries     S={1}    S={1,2}
{1}>={2}      T      lie
{1}>={3}      T       T
{2}>={1}      F      lie 
{2}>={3}     lie      T
{3}>={1}      F       F
{3}>={2}     lie      F
{1}>={2,3}    T      lie
{2}>={1,3}    F      lie
{3}>={1,2}    F       F
{2,3}>={1}    F      lie
{1,3}>={2}    T      lie 
{1,2}>={3}    T       T

Wie Sie sehen können - wenn der Gegner ein Fuchs ist - kann er die beiden Spalten gleich machen, so dass es keine Möglichkeit gibt, zwischen Lösung und Lösung S = { 1 , 2 } zu unterscheiden ... selbst mit einem Exponential Anzahl der Abfragen.S.={1}}S.={1,2}}

Und ich denke, selbst wenn Sie die Familie F einschränken, können Sie in ein unmögliches Spiel "fallen". Wenn Sie beispielsweise das Element irgendwo in einem oder mehreren der Sätze von F im Beispiel hinzufügen , wird der Fuchs nicht getötet :-)))4


Es sieht aus wie eine Variante des Master Mind Game, die normalerweise polynomisch ist, aber eine statische Version hat, die NP-vollständig ist ( siehe Beweis ).

... Das ursprüngliche Mastermind-Spiel wurde 1970 von Meirowitz als Brettspiel mit Löchern für Sequenzen der Länge N = 4 und K = 6 erfunden. Knuth (1) zeigte anschließend, dass diese Instanz des Mastermind-Spiels in fünf oder weniger Vermutungen gelöst werden kann. Chv´atal (2) untersuchte die Kombinatorik des allgemeinen Masterminds und zeigte, dass sie im Fall K> = N in Polynomzeit gelöst werden kann. Stuckman und Zhang (3) zeigten, dass es NP-vollständig ist, um festzustellen, ob Eine Folge von Vermutungen und Antworten im Allgemeinen ist Mastermind mit doppelter Zählung zufriedenstellend. ...

(1) D. Knuth. Der Computer als Meistergeist. Journal of Recreational Mathematics, 9: 1–5, 1977.

(2) V. Chv´atal. Mastermind. Combinatorica, 3 (3/4): 325–329, 1983.

(3) J. Stuckman und G.-Q. Zhang. Mastermind ist np-complete, 2005. http://arxiv.org/abs/cs/0512049 .

Marzio De Biasi
quelle
@Vor: Kann Master Mind auf dieses Problem reduziert werden?
Marcus Ritt
pich|EINS.||B.S.|EINB.
Danu
F.
@Danu ... ok ... mmm ... wenn jede Teilmenge in F dieselbe Größe hat, hat der Algorithmus die Komplexität O (N ^ 2): Wählen Sie einfach die Menge aus, die bei allen Abfragen im Vergleich zur anderen | WAHR ist F | -1 setzt?!? Oder betrachten Sie F nicht als Eingabe des Algorithmus?
Marzio De Biasi
... (Kommentare können nach 5 Minuten nicht bearbeitet werden) ... Wenn Sie benötigen, dass alle Mengen von F dieselbe Größe haben müssen (einschließlich der Lösung), muss diese Größe ein Eingabeparameter sein , es sei denn, Sie geben jede Teilmenge von F an (aber In diesem Fall fallen Sie in die triviale O (N ^ 2) -Lösung.
Marzio De Biasi