Ein Hindernis wie die ETH

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

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

cc.complexity-theory subset-sum T ....
quelle

Antworten:

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

In https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf zeigen wir, dass jeder $n^{O(1)} n^{k/\alpha(k)}$ -Zeitalgorithmus für k-SUM für jeden monotonen nicht abnehmenden unbegrenzt ist Funktion $\alpha$ würde bedeuten, dass die ETH falsch ist.

Ryan Williams
quelle

α

$\alpha$

O ((\log n)^{O (k)})

$O((\log n)^{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