арифметика - О вычислительной сложности выражения

Question

Пусть:

1) $%\mathbb{B}$% - множество булевых чисел, то есть $%\mathbb{B} = \{0, \ 1\}$%,

2) отображение $%\times : \mathbb{B}^2 \mapsto \mathbb{B}$% таково, что $%0 \times 0 = 0 \ \wedge \ 0 \times 1 = 0 \ \wedge \ 1 \times 0 = 0 \ \wedge \ 1 \times 1 = 1$%,

3) отображение $%\neg : \mathbb{B} \mapsto \mathbb{B}$% таково, что $%\neg 0 = 1 \ \wedge \ \neg 1 = 0$%,

4) $%\{x, y\} \subseteq \mathbb{B}$%.

Вопрос: Чему равна вычислительная сложность выражения $%\neg x \times y$%?

chameleon 4.2k●1●7●39 · Answer 1

Понятие "вычислительная сложность" неразрывно связано с вычислительной аппаратурой и без нее не существует. То есть вычислительная сложность выражения - это количество элементарных операций (обычно, примерно одинаковых по времени исполнения), необходимых для его вычисления на некоторой машине.
Аппаратура большинства компьютеров поддерживает операции побитового умножения и побитового отрицания, но не поддерживают их связку, приведенную в условиях. То есть, вычислительная сложность данного выражения равна 2. Но существуют и специальные компьютеры, процессоры и платы, поддерживающие вычисление данной операции сразу, - на них вычислительная сложность данного выражения равна 1.
Кроме того: если говорить о программировании, то с булевыми данными там отдельный разговор. Если надо просто вычислить значение выражения, то используются побитовые операции, но обычно логические данные нужны для того, чтоб перейти (или нет) по некоторой ветке алгоритма. Что-то вроде такого:

if ((not x) and y) then do_something;

Чтоб говорить о вычислительной сложности, надо изложить то же самое в элементарных операциях. Вот "наивный" вариант, сначала вычисляющий наше выражение, а потом проверяющий его истинность:

nx := not x;
z := nx and y;
ifnot (z) then goto NEXT
do_something;
NEXT:

Вычислительная сложность вычисления выражения вместе с проверкой в данном варианте равна 3: выполнить отрицание, выполнить умножение, проверить значение. Но любой современный компилятор сделает всё по другому:

if (x) then goto NEXT
ifnot (y) then goto NEXT
do_something;
NEXT:

То есть, компьютер редко производит логические операции непосредственно, а пользуется их свойствами (в данном случае - тем, что при $%x=1$% значение выражения уже известно). Вычислительная сложность - 2.

Галактион 629●3●34 · Answer 2

0

По моему мнению, подходящий ответ можно найти следующим образом.

Если операция $%\Diamond : \mathbb{B}^2 \mapsto \mathbb{B}$% такова, что $% 0 \Diamond 0 = 1 \ \wedge \ 0 \Diamond 1 = 0 \ \wedge \ 1 \Diamond 0 = 0 \ \wedge \ 1 \Diamond 1 = 0, $% тогда:

1) $%\forall x (x \in \mathbb{B} \rightarrow \neg x = x \Diamond x)$%,

2) $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \rightarrow x \times y = (x \Diamond x) \Diamond (y \Diamond y))$%,

3) $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \rightarrow \neg x \times y = ((x \Diamond x) \Diamond (x \Diamond x)) \Diamond (y \Diamond y))$%.

Руководствуясь изложенным, предполагаю, что вычислительная сложность выражения $%\neg x \times y$% не меньше, чем пять diamond'ов (диамантов).

P.S. Диамант - устаревшее название алмаза. Полагаю, что это название можно использовать в качестве названия бинарной битовой операции $%\Diamond$%.

Дополнение

$%1.$% Если выбрать отображение $%\times : \mathbb{B}^2 \mapsto \mathbb{B}$% и отображение $%\oplus: \mathbb{B}^2 \mapsto \mathbb{B}$% в качестве базисных операций, тогда вычислительная сложность выражения "$%\neg x \times y$% в базисе $%\{\times, \oplus \}$%" будет не меньше, чем две базисные операции, так как $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \ \rightarrow \ \neg x \times y = (1 \oplus x) \times y)$%.

$%2.$% Вычислительная сложность выражения "$%1$%" в базисе $%\{\Diamond, =, \downarrow \}$% равна 0 базисных операций, тогда как вычислительная сложность выражения "$%0$%" в указанном базисе равна 1 базисной операции (потому что $%0 = \neg 1 = 1 \Diamond 1$%).

ссылка

отвечен 11 Сен '13 17:11

Галактион
629●3●34

изменен 14 Сен '13 17:30

И что сподвигло Вас вычислять ВС выражения именно в "diamond'ах", а не чем-либо еще?

(11 Сен '13 17:17) chameleon

Стрелка Пирса.

(11 Сен '13 17:22) Галактион

@Галактион: в таком виде задача становится вполне понятной и содержательной, но это часть постановки вопроса, и тогда с самого начала уместно было так и написать. Типа, назовём "вычислительной сложностью" булевой функции (или задающей её формулы исчисления высказываний) то-то и то-то. Помимо стрелки Пирса, можно рассмотреть случай штриха Шеффера -- результат там будет в общем случае уже другой. Поправка: из Вашего примера следует, что сложность не больше 5.

(11 Сен '13 19:36) falcao

@Галактион: хочу добавить ещё такое соображение. В соответствии с "идеологией" построения схем из элементов, тождественную функцию строить не надо: она всегда как бы "дана". Грубо говоря, это "проводок", по которому течёт или не течёт ток, что управляется одним из переключателей. В этом случае достаточно двух "диамантов".

(11 Сен '13 19:49) falcao

Dear falcao.

Благодаря Вам, я стал лучше понимать, что такое вычислительная сложность выражения. Надеюсь, Вы продолжите высказывать Ваши наблюдения, замечания и соображения.

(11 Сен '13 19:54) Галактион

арифметика - О вычислительной сложности выражения

2 ответа

Здравствуйте

Связанные исследования

Связанные вопросы

Отслеживать вопрос