Изменения
Новая страница: «# Докажите, что объединение и пересечение языков из $P$ является языком из $P$ # Докажите, чт…»
# Докажите, что объединение и пересечение языков из $P$ является языком из $P$
# Докажите, что дополнение языка из $P$ является языком из $P$
# Докажите, что конкатенация и замыкание Клини языков $P$ является языком из $P$
# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
# Почему рассуждение из задания 2 не применимо к языкам из $NP$?
# Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
# В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $FAC.UNARY = \{\langle 1^n, 1^q \rangle |$ у $n$ существует делитель $t$, такой что $2 \le t \le q < n\}$ лежит в $P$. Что можно сказать про аналогичную задачу, где ввод задается в двоичной системе счисления?
# Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
# Докажите, что дополнение языка из $P$ является языком из $P$
# Докажите, что конкатенация и замыкание Клини языков $P$ является языком из $P$
# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
# Почему рассуждение из задания 2 не применимо к языкам из $NP$?
# Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
# В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $FAC.UNARY = \{\langle 1^n, 1^q \rangle |$ у $n$ существует делитель $t$, такой что $2 \le t \le q < n\}$ лежит в $P$. Что можно сказать про аналогичную задачу, где ввод задается в двоичной системе счисления?
# Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
