Сложно ли найти оптимальные цепочки сложений?

Дополнение цепь представляет собой последовательность положительных целых чисел , где х 1 = 1 , и каждый индекс я ≥ 2 , мы имеем й я = х J + х K для некоторых индексов 1 ≤ J , к < я . Длина прибавления цепи п ; мишень из капельной цепи $(x_1, x_2, \dots, x_n)$$x_1 = 1$$i\ge 2$$x_i = x_j + x_k$$1\le j,k < i$$n$ .$x_n$

Что известно о сложности следующей задачи: Учитывая целое число , какова длина самой короткой цепочки сложения, целью которой является N ? Это NP-жесткий?$N$$N$

Википедия указывает на статью 1981 года, написанную Дауни, Леонгом и Сетхи, в которой доказывается, что следующая связанная проблема является NP-трудной: учитывая набор целых чисел, какова минимальная длина цепочки сложений, которая включает весь набор? Некоторые авторы, очевидно, утверждают, что эта статья доказывает, что задача с одной целью является NP-трудной, но это не так.

Проблема упоминается как открытая в докторской диссертации Эрика Лемана «Алгоритмы аппроксимации для сжатия данных на основе грамматики» в 2002 году. С стр. 35 диссертации:

«Тем не менее, точное решение проблемы цепочки сложения остается странно неуловимым. М-арный метод выполняется во времени polylog (n) и дает приближение 1 + o (1). Однако, даже если экспоненциально больше времени, поли ( n), точный алгоритм не известен ".

А в основной статье диссертации Лемана есть хороший обзор проблемы (раздел VB) со ссылками.

Я хотел бы задокументировать некоторый частичный прогресс - казалось бы, многообещающий - к алгоритму полиномиального времени. ОБНОВЛЕНИЕ : добавлены некоторые детали, чтобы учесть глюк, отмеченный @David (спасибо!).

Подход заключается в том, чтобы свести это к экземпляру CSP-серверов MIN-ONES EVEN-3 (MOEC), что является проблемой, решаемой за полиномиальное время. Доказательство сокращения немного нечетко, но я надеюсь, что оно существует!

Экземпляр MOEC - это семейство мерных подмножеств множества переменных и целое число k . Вопрос в том, существует ли удовлетворительное назначение веса не более k , где назначение - это функция от юниверса до { 0 , 1 } , вес назначения - это число переменных, которым оно присваивает одну, и назначение удовлетворяющий, если для каждого подмножества переменных { x , y , z } присваивание (скажем, f ) имеет свойство, которое:$3$$k$$k$$\{0,1\}$$\{x,y,z\}$$f$

.$f(x) + f(y) + f(z) = 0 (mod ~~2)$

Вы можете представить это как 3-SAT с другим понятием удовлетворенности - выберите ни одного или два. Я буду немного небрежен в отношении примера MOEC в том смысле, что я учту, кроме обычных подмножеств, последствия, дизъюнкции длины два и ограничение ( x = 1 ) . Я считаю, что эти простые дополнения сохранят проблему за полиномиальное время.$3$$(x = 1)$

Допустим, мы уменьшаем проблему цепочки сложений для числа . Переменная, установленная для этого сокращения, следующая:$n$

Для каждого переменная N i . Я переписать переменную N п , как N . Для каждой пары i , j такой, что 1 ≤ i , j ≤ k , введите переменные P i j и Q i j . $1 \leq i \leq n$$N_i$$N_n$$N$$i,j$$1 \leq i,j \leq k$$P_{ij}$$Q_{ij}$

Введем следующие подмножества для каждого такого что k = i + j :$i,j,k$$k = i+j$

$\{P_{ij}, Q_{ij}, N_k \}$

и следующие последствия:

и P i j ⇒ N $P_{ij} \Rightarrow N_i$$P_{ij} \Rightarrow N_j$

и следующие ограничения:

.$(N_1 = 1), (N = 1)$

$P$$N$$P_{ij}$$i + j$$N$

Итак, позвольте мне изложить общий способ сказать, учитывая набор переменных:

$(X, l_1, l_2, \ldots, l_t)$

$X$$l_i$

$(N_k, \{ P_{ij} ~|~ i + j = k \})$

$T_X$$t$$T_{di}$$1 \leq d \leq \log t$$1 \leq i \leq {\cal L}(d)$${\cal L}(d)$$T_X$$d$

$T_{di}$$p$$q$

$\{T_{di},p,q\}$

Это означает, что если переменная, соответствующая узлу, установлена ​​в значение true, то точно один из его дочерних элементов также должен быть установлен в значение true. Теперь добавьте значения:

$(X \Rightarrow T_{11})$$(d_{\log t,j}) \Rightarrow l_j$

Эта комбинация ограничений и последствий EVEN-3 эквивалентна ограничению, которое мы хотели закодировать.

$N_i$$N$$N$$P_{ij}$$N_i$$N_j$$P_{ij}$$(r,s)$$(r',s')$$P$$Q$$N_i$$P_{ij}$

$f$$f$$N_i$$N_i$$k$$N_k$$i_k,j_k$$i_k + j_k = j$$f$$P_{i_k j_k}$$Q_{i_k j_k}$$(i,j)$$i \neq i_k$$j \neq j_k$$i+j = k$$f$$Q_{ij}$$P_{ij}$$k$$i,j$$i+j = k$$Q_{ij}$$P_{ij}$$N_i$$(i,j)$

$t$$t$$Q$$x$$x$в любом случае происходит в более длинной цепочке, а остальные сравниваются благоприятно. Тем не менее, я должен тщательно это записать, и, возможно, я просто вижу вещи с синдромом после полуночи!