Обучение NP-полноте - сокращения Тьюринга против сокращений Карпа

Меня интересует вопрос о том, как лучше всего преподавать NP-полноту специальностям информатики. В частности, должны ли мы учить этому, используя сокращения Карпа или сокращения Тьюринга?

Я чувствую, что концепции NP-полноты и сокращения - это то, что должен изучать каждый специалист по информатике. Однако, когда я учил NP-полноте, я заметил, что использование сокращений Карпа имеет некоторые недостатки.

Во-первых, для некоторых студентов сокращения Карпа кажутся излишне запутанными. Интуитивным понятием сокращения является «если у меня есть алгоритм для решения проблемы X, то я могу использовать его и для решения проблемы Y». Это очень интуитивно понятно, но гораздо лучше отображает сокращения Тьюринга, чем сокращения Карпа. В результате я вижу, что студенты, которые пытаются доказать NP-полноту, вводятся в заблуждение своей интуицией и создают неверное доказательство. Попытка преподавать оба вида сокращений и акцентирование этого аспекта сокращений Карпа иногда кажется чем-то вроде ненужного формализма и отнимает ненужное время урока и внимание студента к тому, что кажется несущественной технической деталью; не очевидно, почему мы используем это более ограниченное понятие сокращения.

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

Наконец, будучи студентом, я помню, как чувствовал себя озадаченным, когда столкнулся с такой проблемой, как «тавтология» - например, учитывая булеву формулу, проверьте, является ли она тавтологией. Что сбивало с толку, так это то, что эта проблема явно сложна: любой алгоритм за полиномиальное время подразумевал бы, что $P=NP$; и решить эту проблему, очевидно, так же сложно, как решить проблему тавтологии. Однако, несмотря на то, что тавтология интуитивно так же сложна, как и выполнимость, тавтология не является NP-сложной. Да, я понимаю сегодня, почему это так, но в то же время я помню, что был озадачен этим. (То, что пришло мне в голову, когда я наконец понял, было: почему мы проводим это различие между NP-hard и co-NP-hard, так или иначе? Это кажется искусственным и не очень мотивированным практикой. Почему мы фокусируемся скорее на NP чем co-NP? Они кажутся одинаково естественными. С практической точки зрения, co-NP-твердость, по-видимому, имеет практически те же практические последствия, что и NP-твердость, так почему же мы все одержимы этим различием? Да, я знаю, ответы, но, как студент, я помню, что это только заставило предмет чувствовать себя более загадочным и плохо мотивированным.)

Итак, мой вопрос заключается в следующем. Когда мы учим NP-полноту студентам, лучше ли учить, используя сокращения Карпа или сокращения Тьюринга? Кто-нибудь пробовал преподавать концепцию NP-полноты, используя сокращения Тьюринга? Если так, как все прошло? Были бы какие-то неочевидные подводные камни или недостатки, если бы мы учили концепции, используя сокращения Тьюринга, и пропускали концептуальные проблемы, связанные с сокращениями Карпа?

Связано: см. Здесь и здесь , где упоминается, что причина, по которой мы используем сокращения Карпа в литературе, заключается в том, что она позволяет нам различать NP-твердость и совместную NP-твердость. Тем не менее, это, похоже, не дает никакого ответа, который сосредоточен на педагогической перспективе того, является ли эта способность критической для целей обучения класса алгоритмов, который должен быть принят каждой специализацией CS. Смотрите также здесь на cstheory.SE , который имеет аналогичное обсуждение.

Я бы сказал, что очень определенно учить, используя сокращения Карпа (многие-один). Независимо от преимуществ использования многократных сокращений Тьюринга (Cook), сокращения Карпа являются стандартной моделью.

Все используют Karp, и главная проблема в обучении Кука состоит в том, что в конечном итоге вы получите целый класс студентов, которые будут патологически запутаны, когда будут читать учебник или пытаться обсудить этот предмет с кем-то, кого вы не учили.

$k$

Лучше учить обоих ! Специалист по информатике должен знать о них обоих.

Я не знаю никого, кто использует сокращения Кука для обучения NP-полноте, теоретики сложности, очевидно, этого не делают, теоретики несложности обычно следуют стандартному определению со времени работы Карпа и используются во всех учебниках (о которых я знаю). Это приведет к путанице для них позже, если вы не будете следовать стандартной терминологии.

Сокращение Кука по существу решает проблемы, используя подпрограммы черного ящика. Их легко объяснить и мотивировать, если у ваших студентов есть некоторый опыт программирования. Они важны, поскольку без сокращений Cook вы не сможете обсуждать сокращения между проблемами поиска, оптимизацией и т. Д.

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{coNP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}$

$x\in A$$f(x) \in B$

Интуитивным понятием сокращения является «если у меня есть алгоритм для решения проблемы X, то я могу использовать его и для решения проблемы Y».

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

Итак, теория подсказывает нам способ рассматривать вычисления в основном как процесс, который может вернуть ответ при некоторых обстоятельствах. в других обстоятельствах это не может быть. для полноты и разрешимости NP фундаментальный и наиболее общий вопрос состоит в том, «существует ли алгоритм, возвращающий Yвремя P». но это ничего не говорит об алгоритме, который возвращает Nв P времени. алгоритм может вернуть Yвремя P для одного экземпляра, но не вернуть ответ для других экземпляров. теория говорит нам, что здесь действительно есть четкое различие, на которое мы должны обратить пристальное внимание. если он не интуитивен, это означает, что наши фундаментальные интуиции должны быть скорректированы (как это часто бывает в теоретическом обучении).