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}$%,

5) $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \ \rightarrow \ (x < y \ \leftrightarrow \ \neg x \times y = 1))$%

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

задан 11 Сен '13 15:07

Полагаю, это вопрос сюда

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

Используя операцию "$%=$%" и операцию "$%\Diamond$%" в качестве базисных операций, находим

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

Исходя из изложенного, вычислительная сложность предложения "$%x \lt y$%" не меньше, чем шесть базисных операций, включая пять битовых операций "$%\Diamond$%" и одну операцию сравнения "$%=$%".

Далее:

  • если (x, y) = (1, 1), тогда выч. сложность "$%x \lt y$%" = 6 базисных операций,

  • если (x, y) = (1, 0), тогда выч. сложность "$%x \lt y$%" = 8 базисных операций,

  • если (x, y) = (0, 1), тогда выч. сложность "$%x \lt y$%" = 10 базисных операций,

  • если (x, y) = (0, 0), тогда выч. сложность "$%x \lt y$%" = 12 базисных операций.

Совокупная выч. сложность "$%x \lt y$%" = 6 + 8 + 10 + 12 = 36 базисных операций.

Средняя выч. сложность "$%x \lt y$%" = $%\frac{36}{4}$% = 9 базисных операций.

Дополнение

$%1. $%Вычислительная сложность предложения "$%x \in \{0, \ 1\}$%" в базисе $%\{\Diamond, =, \downarrow \}$% не меньше, чем 9 базисных операций, так как

$%x \in \{0, 1\} \ \Leftrightarrow \ x = 0 \vee x = 1 \ \Leftrightarrow \ (x = 0 \downarrow x = 1) \downarrow (x = 0 \downarrow x = 1)$%

$%\Leftrightarrow \ (x = \neg 1 \downarrow x = 1) \downarrow (x = \neg 1 \downarrow x = 1) \ \Leftrightarrow \ (x = 1 \Diamond 1 \downarrow x = 1) \downarrow (x = 1 \Diamond 1 \downarrow x = 1)$%

$%2.$% Вычислительная сложность предложения "$%x = x$%" в базисе $%\{\Diamond, =, \downarrow\}$% не меньше, чем одна базисная операция.

$%2.1$% Вычислительная сложность предложения "$%1 = 1$%" в базисе $%\{\Diamond, =, \downarrow\}$% равна одной базисной операции.

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

$%2.3$% Вычислительная сложность предложения "$%0 = 0$%" в базисе $%\{\Diamond, =, \downarrow\}$% равна трём базисным операциям, так как $%0 = 0 \ \Leftrightarrow \ \neg 1 = \neg 1 \ \Leftrightarrow \ 1 \Diamond 1 = 1 \Diamond 1$%.

ссылка

отвечен 11 Сен '13 20:29

изменен 14 Сен '13 21:28

Почему Вы говорите "не меньше" вместо "не больше"? Вот у Вас есть некий план, как вычислить что-то за 6 операций. Может так оказаться, что он оптимален, и тогда сложность равна 6. Но если вдруг кто-то предложит лучший вариант -- скажем, с 4 или 5 действиями, то сложность окажется меньше. Значит, она меньше либо равна 6, то есть не больше 6.

(13 Сен '13 13:14) falcao

Я говорю "не меньше", потому что мне очень хочется умножить 6 [операций] на 4 [ёмкость пространства $%\mathbb{B}^2$%, которому принадлежит пара (x, y)].

(13 Сен '13 14:07) Галактион
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×149
×80

задан
11 Сен '13 15:07

показан
597 раз

обновлен
14 Сен '13 21:28

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

по почте:

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

по RSS:

Ответы

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

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