Algorithmisches Vektorproblem

13

Ich habe ein algebraisches Problem im Zusammenhang mit Vektoren im Feld GF (2). Sei v1,v2,,vm (0,1) -Vektoren der Dimension n und m=nÖ(1) . Finden Sie einen polynomialen Zeitalgorithmus, der einen (0,1) -Vektor u mit der gleichen Dimension findet, sodass u nicht die Summe aller (Logn)Ö(1) -Vektoren unter v1,v2,,vm . Die Addition von Vektoren erfolgt über das Feld GF (2), das zwei Elemente 0 und 1 aufweist (0+1=0+1=1 und0+0=1+1=0 ).

Es ist leicht, die Existenz eines solchen Vektors u durch ein einfaches Zählargument zu erkennen. Können wir finden u in einem Polynom Zeit? Es ist trivial, u in exponentieller Zeit zu finden . Ich werde einen 200-Dollar-Scheck für die erste richtige Lösung senden.

Bin Fu
quelle
es scheint vage mit dem Teilmengen-Summenproblem zu tun zu haben, das NP-vollständig ist. Dabei wird jedoch die ganze Zahl anstelle von XOR verwendet.
vzn
1
Seltsamerweise habe ich kürzlich versucht, ein ähnliches Problem zu formulieren und zu betrachten. Versuchen Sie Abschnitt 13.5 des stasys jukna Buches über die Komplexität von Booleschen Funktionen. Es sieht so aus, als ob Ihr q in diesem Kapitel in Form von linearen Schaltkreisen formuliert werden kann.
vzn
1
Wie wäre es mit Super-Poly-Algorithmen, dh m ^ log (n)?
Dimitris
1
@Niel de Beaudrap: aber die Anzahl der zu überprüfenden XORs ist super-poly (dh ungefähr ), nicht poly. Ist das nicht ein Problem? (mLog(n))
Dimitris
1
Um die Bemerkung von vzn zu erweitern: Es scheint, dass fast jeder Vektor Ihren Anforderungen mit dem gleichen Zählargument entspricht. Ich stelle mir vor, Sie möchten auch den Beweis, dass ein (möglicherweise zufällig erzeugter) Vektor in keinem von Polylog ( n ) der Vektoren überspannten Unterraum enthalten ist : Ihre Frage kommt also dem Aufzeigen des Problems gleich, ob ein Kandidat oder nicht Der Vektor u gehört nicht zu einem durch eine Dimension f ( n ) ∈ Polylog ( n ) der Vektoren erzeugten Unterraum ist in NP . vj
Niel de Beaudrap

Antworten:

8

Es scheint ein Tippfehler zu sein; Ich nehme an, Sie wollen was nicht die Summe von Vektoren unter (nicht ) ist. ( log n ) O ( 1 ) v 1 , , v m nu{0,1}n(Logn)Ö(1)v1,,vmn

Mir ist nicht klar, ob eine Konstante in für Sie funktioniert. Wenn Sie sich mit Summen von weniger als Vektoren zufrieden geben können, ist vielleicht etwas zu tun. Aber wenn Sie wollen, dass diese Menge , dann denke ich, dass es ziemlich schwierig ist (ich habe lange an diesem Problem gearbeitet). log m ( log m ) 1 + δ(Logn)Ö(1)Logm(Logm)1+δ

Es könnte Sie dennoch interessieren, dass dies ein Beispiel für das Fernpunktproblem von Alon, Panigrahy und Yekhanin ("Deterministische Approximationsalgorithmen für das nächste Codewortproblem") für bestimmte Parameter ist. Sei und die Spalten der Paritätsprüfungsmatrix eines linearen Codes in der Dimension (wenn diese Matrix nicht den vollen Rang hatte) wäre das Problem trivial). Dann ist Ihr Problem gleichbedeutend mit dem Finden von , dh aus dem Code. Diese Parametereinstellung, bei der die Abmessung sehr nahe an m liegt, wird in der Arbeit nicht untersucht. Sie können jedoch nur die Fernem>nv1,,vm{0,1}md=m-nu{0,1}n(Logn)Ö(1)Logmbis zur Dimension für eine Konstante . Ich glaube nicht, dass wir ein polynomgroßes Zertifikat kennen, mit dem wir beweisen können, dass ein Vektor mehr als von einem Raum der Dimension , geschweige denn zu finden ist es.d=cmcω(Logm)Ω(m)

Ein weiterer Zusammenhang besteht mit dem Lernen von Paritäten im fehlergebundenen Modell. Wenn man effizient -Paritäten (definiert auf ) mit einer Fehlergrenze von weniger als lernen kann, kann man beliebige Werte auf das erste Bits von und "einen Fehler erzwingen" auf das letzte Bit, indem es auf den entgegengesetzten Wert gesetzt wird, den der Lernende vorhergesagt hat. Dies scheint jedoch viel stärker zu sein.(Logn)Ö(1)0,1mnn-1u

Das Problem hängt auch mit der Trennung der EXP von bestimmten Reduktionen auf dünn besetzte Mengen zusammen.

David
quelle
1
Vielen Dank für den Hinweis auf den Tippfehler. Das letzte "v_n" sollte "v_m" sein. Hoffe, jemand wird es beheben. Ihre Antwort enthält hilfreiche Informationen. +1
Bin Fu