Сокращения из книги.

22

Это похоже на « Алгоритмы из Книги ». Хотя сокращения также являются алгоритмами, я подумал, что сомнительно, что можно подумать о сокращении в ответ на вопрос об алгоритмах из книги. Отсюда отдельный запрос!

Сокращения всех видов приветствуются.

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

Те, кому не хватает контекста книги, могут захотеть взглянуть на вопрос об алгоритмах из книги .

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

Итак, позвольте мне описать то, что я имел в виду, и я думаю, что само собой разумеется - YMMV в этом отношении. Я намерен провести прямую аналогию с первоначальным намерением Доказательств из Книги. Я видел невероятно умные сокращения, и я не мог понять, как эта последовательность мыслей могла случиться с кем-либо. Хотя такие сокращения вызывают у меня определенное чувство благоговения, это не те примеры, которые я собираюсь собрать в этом контексте.

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

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

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

Neeldhara
источник
1
Сообщество вики.
Дэйв Кларк
@supercooldave: Спасибо. Полагаю, мне следовало сделать это во время публикации. Мой недосмотр!
Нилдхара
@Jukka: Спасибо! Я думал, что это то, что сделал редактирование supercooldave. Теперь я понимаю, что редактирование добавил тег. Теперь это CW :)
Нилдхара
8
Возможно, постер должен уточнить, что подразумевается под «из книги». Я бы подумал, что (по аналогии с доказательствами из книги) алгоритмы из книги все короткие, простые в изложении, изящные и работают почти волшебно. Тем не менее, другой поток имеет много сообщений с безумно сложными алгоритмами, которые не удовлетворяют ни одному из свойств, которые я упомянул.
Робин Котари
3
@ Робин: восприятие отличается. Я не нашел ни одного доказательства из «Доказательств из книги» простым (ну, почти, ни одного). И уже второе доказательство (постулат Бертрана) требует нескольких страниц, поэтому они тоже не короткие. - С другой стороны, я нахожу многие алгоритмы в связанном потоке довольно простыми (задним числом, очевидно), и нельзя отрицать, что они короткие.
Конрад Рудольф

Ответы:

9

Рабин показывает односторонность (x ^ 2 mod N = pq) без факторизации N путем сокращения, показывая, что если вы можете взять модуль квадратных корней N = pq, то вы можете множить N.

Ноам
источник
Объяснение этого сокращения (если я не ошибаюсь) можно найти на странице 7 «Обеспечиваемая безопасность криптосистем: обзор». Вот ссылка: cs.yale.edu/publications/techreports/tr288.pdf
Нилдхара,
9

В машинном обучении есть много интересных сокращений. Вот некоторые примеры:

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

Учебник Алина Бейгельзимер, Джон Лэнгфорд, и Бьянка Zadrozny охватывает некоторые другие.

Лев Рейзин
источник
2
Спасибо! Это кажется наиболее многообещающим, а также совершенно новым для меня. Я должен потратить некоторое время на этот учебник и другие ссылки тоже.
Нилдхара
8

Теорема Кука-Левина

Любая проблема в NP может быть уменьшена в политическом времени с помощью детерминированной машины Тьюринга до SAT. Для справки см. 1 .

Руи Феррейра
источник
8

Целочисленное умножение на быстрые преобразования Фурье!

Jeffε
источник
6
и следствие: строка, соответствующая БПФ!
Суреш Венкат
6

Теорема Райса

Один из любимых. Это уменьшает проблему остановки для любого набора индексов (или его дополнения). См., Например, Sipser, проблема 5.28.

Михаэль Кадилхак
источник
1
Обобщение Райс-Шапиро еще красивее. Смотрите экспозицию Катленда: books.google.com/… )
Диего де Эстрада
3

СБ на 3САТ

КК>3

Руи Феррейра
источник
3

3SAT до 3COL

Использование гаджетов, чтобы уменьшить 3SAT, чтобы решить, является ли граф окрашенным с 3 цветами. Для справки см. 1 .

Руи Феррейра
источник
1
Сокращение с использованием NAESAT вместо 3SAT (в книге Пападимитриу) является более прямым.
Диего де Эстрада
3

В смысле сказать - о, это было просто - в ретроспективе:

сведение сортировки к проблеме выпуклой оболочки.

user200
источник
2

ТОЧНАЯ ПОКРЫТИЕ 3-КОМПЛЕКТАМИ ПОД СУММУ

Uзнак равно{1,2,...,3м}S1,...,SNUмU

вес1,...,весNКК

Думайте о наборах как о векторах в { 0 , 1 } 3 м , и думайте об этих векторах как о целых числах в основании nSя{0,1}3мN+1Sявесязнак равноΣJSя(N+1)3м-JКзнак равноΣJзнак равно03м-1(N+1)J

(Моим источником была книга Пападимитриу.)

Диего де Эстрада
источник