Вычислительная сложность сумм и разностей

[zgemm]

Дано $a,b,c,d$, надо посчитать из них $x_1,x_2,x_3$ по формулам

$$x_1=a+b-c-d;$$

$$x_2=a-b-c+d;$$

$$x_3=a+b+c+d;$$

Я понимаю, как за семь операций их посчитать:

$$t_1=a-c;$$

$$t_2=b-d;$$

$$x_1=t_1+t_2;$$

$$x_2=t_1-t_2;$$

$$x_3=a+b+c+d;$$

Скажите, пожалуйста, можно ли доказать, что за шесть и меньше операций это уже нельзя сделать?

[dgwuqtj]

Если никто более умных мыслей не предложит, можно просто перебрать все способы что-то посчитать за $6$ операций с помощью сложения, вычитания и унарного вычитания. Каждый способ — это ориентированный ациклический граф, где вершины без исходящих рёбер — это исходные переменные и $0$, а из каждой другой вершины исходит 2 ребра. Причём такая вершина помечена "$+$" или "$-$", во втором случае ещё указан порядок на исходящих рёбрах. Самим вершинам соответствуют арифметические выражения. Для $6$ операций таких графов не больше $\prod_{k = 5}^{10} \bigl(k + 3 \binom k 2\bigr) \leq 2 \cdot 10^{11}$ (слагаемое $k$ — это когда складываем число с собой).

Можно попробовать считать унарное вычитание бесплатным, тогда вершина 0 не нужна и можно считать, что вершинам соответствуют выражения с точностью до знака. На исходящих рёбрах из вершин с "$-$" порядок тоже не нужен, всего графов не больше $\prod_{k = 4}^9 k^2 \leq 4 \cdot 10^9$. Это уже совсем за разумное время перебирается.

[wrest]

zgemm
Спросил у парочки ИИ, оба предлагают 7 операций. Один из них в качестве одной из 7 операций предлагает удвоение, что для целых чисел просто сдвиг на один бит.

[mihaild]

Можно не графы перебирать, а множества "что вообще можно посчитать за 6 действий", их чуть меньше.

[Sender]

wrest в сообщении #1671892 писал(а):

Спросил у парочки ИИ, оба предлагают 7 операций.

Нынешние ИИ довольно неважно проявляют себя в задачах подобного рода.

[dgwuqtj]

Я всё перебрал, за 6 сложений и вычитаний (и сколько угодно унарных вычитаний) действительно не получается. Программа работает несколько минут и выводит в консоль количество перебранных вариантов, когда оно делится на миллион.

Используется синтаксис C

#include <stdio.h>
#include <stdlib.h>
int coefficients[10][4]; // coefficients in the linear combinations of variables
long long count = 0; // current number of variants
FILE* output;

void try(int position) {
        if (position == 10) {
                count++;
                if (count % 1000000 == 0) {
                        printf("%d'000'000\n", (int)(count / 1000000));
                        fflush(stdout);
                }
                int done[3]; // flags if the required sums appeared
                done[0] = done[1] = done[2] = 0;
                for (int i = 4; i < position; i++) {
                        if ((long long)coefficients[i][0] * (long long)coefficients[i][1] * (long long)coefficients[i][2] * (long long)coefficients[i][3] == 1) {
                                if (coefficients[i][0] == coefficients[i][1]) {
                                        if (coefficients[i][0] == coefficients[i][2])
                                                done[2] = 1;
                                        else
                                                done[0] = 1;
                                } else {
                                        if (coefficients[i][0] != coefficients[i][2])
                                                done[1] = 1;
                                }
                        }
                        if (done[0] && done[1] && done[2]) {
                                for (int i = 4; i < position; i++) {
                                        for (int j = 0; j < 4; j++) {
                                                fprintf(output, "%d", coefficients[i][j]);
                                                if (j < 3)
                                                        fprintf(output, ", ");
                                        }
                                        if (i < position - 1)
                                                fprintf(output, "\n");
                                }
                                fclose(output);
                                exit(0);
                        }
                }
        } else {
                for (int i = 0; i < position; i++)
                        for (int j = 0; j < i; j++) {
                                for (int k = 0; k < 4; k++)
                                        coefficients[position][k] = coefficients[i][k] - coefficients[j][k];
                                try(position + 1);
                        }
                for (int i = 0; i < position; i++)
                        for (int j = 0; j <= i; j++) {
                                for (int k = 0; k < 4; k++)
                                        coefficients[position][k] = coefficients[i][k] + coefficients[j][k];
                                try(position + 1);
                        }
        }
}

int main() {
        output = fopen("output.txt", "w");
        for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++)
                        coefficients[i][j] = (i == j) ? 1 : 0;
        try(4);
        fclose(output);
}

 

[zgemm]

Спасибо большое dgwuqtj!!!

Я тоже начал писать аналогичную программу, но Вы опередили. Огромное спасибо!!!