1
1

Пусть:

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$%?

задан 11 Сен '13 11:26

А каково используемое Вами определение "вычислительной сложности"?

(11 Сен '13 13:08) falcao

Отвечая на мой вопрос, воспользуйтесь тем определением "вычислительной сложности", которое Вам нравится.

P.S. Мной не обнаружено определение "вычислительной сложности" в статье "Вычислительная сложность" в Википедии.

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

Если определение можно выбирать произвольно, то самое первое, что приходит в голову -- это считать её равной количеству логических связок в формуле. Тогда для $%\neg{x}\& y$% она равна двум, и это как бы не слишком интересно. Могут, правда, быть и другие толкования -- с "дробным" ответом, но для этого надо рассмотреть более сложный пример, когда ответ (для конкретных значений переменных) получается "досрочно", без "просчёта" всей формулы.

(11 Сен '13 15:18) falcao
  1. Большое спасибо.

  2. Приглашаю Вас продолжить обсуждение понятия "вычислительная сложность выражения".

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

А какие приоритеты у операций? То есть, $%\neg x \times y = \neg (x \times y)$% или $%\neg x \times y = (\neg x) \times y$%?

(11 Сен '13 17:19) chameleon
10|600 символов нужно символов осталось
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.

ссылка

отвечен 11 Сен '13 15:45

  1. Спасибо.

  2. Поскольку в физике некоторые "эталоны" могут быть "аппаратными" (например, таким был эталон длины и таким является эталон веса), постольку я допускаю, что в математике некоторые "эталоны" для измерения "вычислительной сложности" могут быть "аппаратными".

  3. Предполагаю, что никакое выражение не имеет ни "истинности", ни "ложности".

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

$%2$%. "Вычислительная сложность" - это понятие в принципе не математическое.
$%3$%. Выражение - не может. Значение выражения - может. 0 - "ложь", 1 - "истина". Если я где-то случайно написал "выражение" вместо "значение выражения", то Вы уж простите меня за это.

(11 Сен '13 17:09) chameleon
10|600 символов нужно символов осталось
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

изменен 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) Галактион
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×163
×86

задан
11 Сен '13 11:26

показан
853 раза

обновлен
14 Сен '13 17:30

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

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru