Hilfe bei folgendem kombinatorischen Problem?

Ich habe Bitvektoren, von denen jeder aus Bits besteht. Bezeichnen wir mit das te Bit des ten Vektors . Jeder Bitvektor unterliegt den folgenden 2 Einschränkungen:$m$$m$$v_i[j]$$j$$i$$i,j \in [1, m]$$v_i$

1. $v_i[j] = 0\ \forall j \geq i$ .
2. $v_i[j] = 1\ \forall j < i - \frac{m}{log(m)}$ .
3. Die Bits, die nicht unter die oben genannten Einschränkungen fallen, können entweder oder , aber in diesem Fall kann die Anzahl der höchstens . $0$$1$$0$$12$

Jetzt habe ich einen anderen Bitvektor mit Bits: Anfangs werden alle Bits von auf . Mit "Anwenden von auf " meine ich, ein bitweises UND zwischen und durchzuführen und dann das Ergebnis in speichern . Ich interessiere mich für die Entwicklung von nach wiederholten Anwendungen der in der Eingabe angegebenen Vektoren . m m s 1 v i s s v i s s v 1 , . . . , v $s$$m$$m$$s$$1$$v_i$$s$$s$$v_i$$s$$s$$v_1, ..., v_m$

Nennen wir diese "wiederholten Anwendungen" eine Trajektorie und definieren wir diese Trajektorie formeller. Eine Trajektorie ist eine Sequenz, die aus höchstens Vektoren (ausgewählt aus den in der Eingabe angegebenen ) besteht, so dass, wenn in der Sequenz ist, alle danach . So ist beispielsweise eine Trajektorie, während nicht ist (weil ). v 1 , . . . , v m v i v j j < i < v 8 , v 3 > < v 3 , v 8 , v 7 > 8 ≥ $m$$v_1, ..., v_m$$v_i$$v_j$$j < i$$<v_8, v_3>$$<v_3, v_8, v_7>$$8\geq3$

Offensichtlich gibt es verschiedene Flugbahnen. Sei . Nehmen wir nehmen und lassen es eine Bahn durchlaufen : für jeden Schritt der Bahn , setzen Sie den neuen Wert genommen von in . Wiederholen Sie dann den gleichen Vorgang für eine andere Trajektorie (immer beginnend mit und immer jeden neuen Wert von in ). Andererseits, bis Sie alle möglichen Trajektorien ausprobiert haben . Am Ende enthält die Menge alle möglichen Werte, die S = ∅ s = 1 m T $2^m$$S=\emptyset$$s = 1^m$$T_1$ s S T 2 s = 1 m s S 2 m S $T_1$$s$$S$$T_2$$s=1^m$$s$$S$$2^m$$S$$s$ kann angesichts der eingegebenen Vektoren jemals annehmen.

Fragen

1. Ich habe in der Eingabe. Ich möchte wissen , Das heißt , wie viele verschiedene Werte kann je annehmen. Natürlich möchte ich berechnen effizient, dh ohne alle möglichen Trajektorien einzeln auszuprobieren.| S | s | S $v_i, ..., v_m$$|S|$$s$$|S|$
2. Angenommen , der 2 entfernen ^nd Beschränkung der Vektoren in Eingangs. Wie sich dies auf auswirkt ? $|S|$
3. Noch wichtiger ist, wie mich am meisten interessiert wächst mit . Isthöchstens Polynom in ? Isthöchstens subexponentiell in ? Oder gibt es schlechte Instanzen, auf denenist notwendigerweise exponentiell in ?m | S | m | S | m | S | $|S|$$m$$|S|$$m$$|S|$$m$$|S|$$m$

Die folgende Abbildung ist ein Beispiel mit : $m=17$

Ich sammle experimentelle Daten, um herauszufinden, welche Beziehung zwischen und. Bisher scheinen Experimente darauf hinzudeuten, dasswächst schneller als und langsamer als . Im Moment haben diese Daten jedoch keine große Bedeutung: Ich konnte nur Tests bis zu , daher kann es eine große versteckte Konstante oder einen anderen Faktor geben, der ein Exponentialgesetz wie ein Polynomgesetz für kleines aussehen lässt . Ich brauche Hilfe, um das asymptotische Verhalten von herauszufinden in Bezug auf . | S | | S | m 3 m 4 m = 90 m | S | $m$$|S|$$|S|$$m^3$$m^4$$m = 90$$m$$|S|$$m$

Ich habe das überdacht und meine anfängliche Bindung war korrekt. Im schlimmsten Fall$|S| = \Theta(m \; 2^\frac{m}{\lg m})$

Der Beweis besteht aus zwei Teilen. Erstens . Betrachten Sie die möglichen Werte von einer Trajektorie, die bei endet . Jedes Bit für ist 0, und jedes Bit für ist 1. Daher gibt es nur Werte, die annehmen können. Multiplizieren Sie mit der Anzahl von und wir haben die Obergrenze.$|S| = O(m \; 2^\frac{m}{\lg m})$$s$$v_x$$s[j]$$j \ge x$$s[j]$$j < x - \frac{m}{\lg m}$$2^\frac{m}{\lg m}$$s$$v_x$

Zweitens betrachten

    0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 
    0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 
    0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
    0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 
    0 0 0 0  1 1 1 0 1 1 1 1 1 1 1 1 
    0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    ...
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Ich behaupte, dass dieses Schema Ihnen . Berücksichtigen Sie für jede Spalte auch die Spalten rechts davon. Jede der -Kombinationen ergibt ein anderes , und in jedem dieser das oberste gesetzte Bit das oberste gesetzte Bit von , so dass es kein Doppel gibt -Zählen zwischen verschiedenen .$|S| = \Omega(m \; 2^\frac{m}{\lg m})$$v_x$$(\frac{m}{\lg m}-2)$$2^{\frac{m}{\lg m}-2}$$s$$s$$v_x$$v_x$