Ein Hindernis wie die ETH

10

Wir wissen, dass wir unter ETHK -SUM nicht in f(K)poly(nK) Zeit unter irgendeiner Funktion f(K) lösen können (normalerweise 2O(K) ).

Gibt es eine Vermutung, die eine (logn)O(K) -Komplexität verhindert (dies stimmt völlig mit der Möglichkeit überein, dass K=Ω(n) wir exponentielle Zeit für die Teilmengen-Summe benötigen) oder ist eine solche Möglichkeit zulässig?

T ....
quelle

Antworten:

16

Die ETH selbst schließt diese Möglichkeit aus.

In https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf zeigen wir, dass jeder nO(1)nk/α(k) -Zeitalgorithmus für k-SUM für jeden monotonen nicht abnehmenden unbegrenzt ist Funktion α würde bedeuten, dass die ETH falsch ist.

Ryan Williams
quelle
3
α
O((logn)O(k))
Hinzugefügt "unbegrenzt" :)
Ryan Williams
@Brout Beachten Sie, dass (log (n)) ^ k eine FPT-Funktion ist, also schließt die ETH dies aus. Mit Poly Size Advice würde dies subexponentielle Größenschaltungen für 3sat bedeuten. Mit einem PPAD-Orakel scheint es zu implizieren, dass die ETH PPAD nicht in P impliziert. Für mich wäre das ein Durchbruch, ich kenne nicht viele bestätigende Beweise dafür, dass PPAD nicht in P ist
Ryan Williams