|
Пусть: 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 
Галактион |
|
Предполагаю, что подходящий ответ на мой вопрос можно найти следующим образом. Используя битовую операцию диамант в качестве базисной операции, находим: 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 \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
Галактион Почему Вы говорите "не меньше" вместо "не больше"? Вот у Вас есть некий план, как вычислить что-то за 6 операций. Может так оказаться, что он оптимален, и тогда сложность равна 6. Но если вдруг кто-то предложит лучший вариант -- скажем, с 4 или 5 действиями, то сложность окажется меньше. Значит, она меньше либо равна 6, то есть не больше 6.
(13 Сен '13 13:14)
falcao
Я говорю "не меньше", потому что мне очень хочется умножить 6 [операций] на 4 [ёмкость пространства $%\mathbb{B}^2$%, которому принадлежит пара (x, y)].
(13 Сен '13 14:07)
Галактион
|
Полагаю, это вопрос сюда