Есть ли какие-то противоречивые результаты в теоретической информатике?

Возможно, некоторые математические и логические парадоксы могут быть автоматически применены к компьютерам, но есть ли какие-либо парадоксы, которые были обнаружены в самой компьютерной науке?

Под парадоксами я подразумеваю противоречащие друг другу интуитивные результаты.

Я нахожу факт, что сетевой поток полиномиального счетчика времени интуитивно понятен. На первый взгляд это кажется намного сложнее, чем многие проблемы NP-Hard. Иными словами, в CS есть много результатов, где время их решения намного лучше, чем вы ожидаете.

Семейство противоречивых результатов - это целое семейство результатов «докажи верхнюю границу, чтобы доказать нижнюю границу». Meyer результат , что означает E X P ⊈ P / р о л у является одним из примеров этого, и это пришло мне в голову от GCT работы как Кетан Малмули, а также недавний результат Райана Уильямса , который снова используется верхний граница для ЦЕПИ-САТ , чтобы доказать нижнюю границу для N E X P в терминах A C C .$\mathsf{P} = \mathsf{NP}$$\mathsf{EXP} \not\subseteq \mathsf{P}/poly$$\mathsf{NEXP}$$\mathsf{ACC}$

SAT имеет алгоритм полиномиального времени, только если P = NP. Мы не знаем, P = NP. Тем не менее, я могу записать алгоритм для SAT, который имеет полиномиальное время, если P = NP истинно. Я не знаю правильную ссылку для этого, но страница в Википедии дает такой алгоритм и кредиты Левин.

Вычислительность, безусловно, винит большинство студентов Прекрасный пример с высокой частотой путаницы:

$f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{cases}$

Является ли вычислимой?$f$

Ответ - да; смотрите обсуждение здесь . Большинство людей сразу пытаются построить с нынешними знаниями. Это не может работать и приводит к воспринимаемому парадоксу, который на самом деле просто тонкость.$f$

Один удивительный и противоречивый результат состоит в том, что , доказанное с помощью арифметизации примерно в 1990 году.$IP = PSPACE$

Как выразились Арора и Барак (стр. 157): «Мы знаем, что одно только взаимодействие не дает нам никаких языков за пределами NP. Мы также подозреваем, что одна только рандомизация не добавляет значительных возможностей к вычислениям. взаимодействие обеспечивают?

Видимо совсем немного!

Как сказал Филипп, теорема Райса является хорошим примером: перед изучением вычислимости интуиция заключается в том, что в вычислениях обязательно должно быть что- то, что мы можем вычислить. Оказывается, мы можем вычислить что-то только для некоторых вычислений.

Как насчет публикаций Мартина Эскардо, показывающих, что существуют бесконечные множества, которые можно исчерпывающе обыскать за конечное время? См. Гостевой блог Эскардо в блоге Андрея Бауэра, например, на тему «На первый взгляд невозможные функциональные программы» .

Теорема о рекурсии, безусловно, кажется нелогичной, когда вы впервые ее видите. По сути, это говорит о том, что когда вы описываете машину Тьюринга, вы можете предположить, что она имеет доступ к своему собственному описанию. Другими словами, я могу создавать машины Тьюринга, например:

TM M принимает n, если n кратно числу раз, которое "1" появляется в строковом представлении M.

TM N принимает число n и выдает n копий самого себя.

Обратите внимание, что здесь «строковое представление» относится не к неформальному текстовому описанию, а к кодированию.

Доказательство теоретико-информационных результатов, основанных на теоретико-сложных предположениях, является еще одним нелогичным результатом. Например, Bellare et al. в своей работе (Истинная) сложность статистического нулевого знания конструктивно доказала, что при допущении о сертифицированном дискретном журнале любой язык, который допускает статистическое нулевое знание с достоверным проверяющим, также допускает статистическое нулевое знание.

Результат оказался настолько странным, что удивил авторов. Они указывали на этот факт несколько раз; например, во введении:

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

PS: более сильный результат был позже безоговорочно доказан Окамото ( О взаимосвязях между статистическими доказательствами нулевого знания ).

Описание некоторых терминов

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

1. $p$$p-1$
2. Нулевое знание : протокол, который не дает знания ограниченным полиномиальным временем сторонам.
3. Знание статистического нуля: протокол, который не дает никакой информации, даже неограниченным в вычислительном отношении сторонам, за исключением случаев, когда вероятность ничтожна.
4. Честный-проверяющий с нулевым знанием: протокол, который не дает никаких знаний сторонам, ограниченным полиномиальным временем, если они действуют так, как указано в протоколе.

Как насчет того факта, что вычислительный перманент является # P-Complete, но является компьютерным детерминантом - так случается, что более странная операция происходит в классе NC?

Это кажется довольно странным - так быть не должно (или, может быть, так и было ;-))

Задача линейного программирования разрешима за (слабо) полиномиальное время. Это кажется очень удивительным: почему мы можем найти одну среди экспоненциального числа вершин многомерного многогранника? Почему мы смогли бы решить проблему, которая настолько смехотворно выразительна?

Не говоря уже о всех линейных программах экспоненциального размера, которые мы можем решить, используя метод эллипсоидов и разделительные оракулы, а также другие методы (добавление переменных и т. Д.). Например, удивительно, что LP с экспоненциальным числом переменных, таких как релаксация Кармакара-Карпа бин-упаковки, может быть эффективно аппроксимирована.

Всякий раз, когда я преподаю автоматы, я всегда спрашиваю своих учеников, не находят ли они удивительными, что недетерминизм не добавляет силы автоматам с конечным состоянием (то есть, что для каждого NFA существует эквивалент - возможно, намного больший - DFA). Около половины школьных отчетов удивлены, так что поехали. [Я сам потерял «чувство» к тому, что удивительно на начальном уровне.]

$R\neq RE$

Я нашел простую криптосистему с открытым ключом с механизмом дешифрования с двойным люком и ее применения парадоксальной, потому что это адаптивно выбранная безопасная схема шифрованного текста, которая гомоморфна.