Bedingte Ergebnisse implizieren Schwierigkeiten bei der Verbesserung der oberen / unteren Grenzen für dauerhafte

8

Sei eine gegebene quadratische Matrix. Gibt es Hinweise darauf, dass es schwierig sein könnte, quadratische Untergrenzen für B zu schlagen, so dass det ( B ) = per ( A ) schwierig sein könnte?ABdet(B)=per(A)

Gibt es eine plausible Vermutung, die impliziert, dass es schwierig ist, untere Grenzen zu beweisen? Gibt es Hinweise darauf, dass es schwierig ist, eine Untergrenze von Zeilen (oder Spalten) für einige ϵ > 0 zu beweisen (z. B. äquivalent zu V PV N P )?Ω(n2+ϵ)ϵ>0VPVNP

Gibt es eine plausible Vermutung, die impliziert, dass es schwierig ist, Obergrenzen zu beweisen? Gibt es Hinweise darauf, dass es schwierig ist, eine -Obergrenze für einige ϵ ( 0 , 1 ) zu beweisen ?O(2nϵ)ϵ(0,1)

vs.
quelle
3
Ich denke, dass diese Frage etwas mehr Erklärung gebrauchen könnte. Ich glaube, ich habe herausgefunden, was du meinst, aber ich bin mir nicht ganz sicher.
Peter Shor
1
B
1
@SureshVenkat Bedeutet das folgende Ergebnis nicht eine quadratische Untergrenze? pages.cs.wisc.edu/~jyc/papers/per-det.pdf
vs
1
Nun, das ist mein Punkt. es wäre nützlich, in der Frage darauf zu verweisen.
Suresh Venkat
@ SureshVenkat Oh ok!
gegen

Antworten:

15

O(2nϵ) ϵ<1

Holger Dell, Thore Husfeldt und Martin Wahlén .

Exponentielle Zeitkomplexität des permanenten und des Tutte-Polynoms.

Vollständiges Papier bei ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

n×nO(2nϵ)×O(2nϵ)

  1. Transformieren Sie eine 3SAT-Instanz in eine permanente Instanz wie im obigen Artikel

  2. Transformiere die Permanente in eine Determinante über der größeren Matrix

  3. Berechnen Sie die Determinante, um die Anzahl der Lösungen für die ursprüngliche 3SAT-Instanz zu ermitteln.

nO(2nϵ)ϵ<1ϵ

Andreas Björklund
quelle