Существует ли алгоритм, который доказуемо существует, хотя мы не знаем, что это такое?

21

В математике есть много доказательств существования, которые неконструктивны, поэтому мы знаем, что определенный объект существует, хотя мы не знаем, как его найти.

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

Эрель Сегал-Халеви
источник
5
Есть тривиальный ответ. Возьмите любой вопрос «да / нет», ответ на который неизвестен, например, «является случайным», тогда вопрос разрешим, только мы пока не знаем, какой из двух возможных алгоритмов является правильным. π
Хендрик Ян
1
@babou Действительно: вопрос с уникальным ответом разрешим. Здесь невежество - это точка, которая кажется, это случай «не знаю» из вопроса, хотя только «не знаю сейчас ». Как только мы выяснили, является ли случайным или нет, нам нужно искать другой пример. Ваш ответ ниже гораздо лучше, конечно! Это форма «не знаю», которая по своей сути «никогда не узнает». π
Хендрик Ян
1
@HendrikJan: И эту процедуру мы называем алгоритмом в CS. Но, взяв в качестве примера проблему остановки, мы даже не можем доказать, что алгоритм существует!
MSalters
1
Еще несколько интересных примеров можно найти здесь: cstheory.stackexchange.com/questions/4777/…
Segal-Halevi,

Ответы:

14

Самый простой случай, который я знаю об алгоритме, который существует, хотя неизвестно, какой алгоритм касается автоматов конечного состояния.

Фактор из языка L 1 с помощью языка L 2 определяется как L 1 / L 2 = { х | у L 2  таким образом, что  х у L 1 } .L1/L2L1L2L1/L2={xyL2 such that xyL1}

Нетрудно доказать, что регулярное множество замкнуто относительно факторного по произвольному множеству. Другими словами, если регулярно, а L 2 произвольно (не обязательно регулярно), то и L 1 / L 2 тоже регулярно.L1L2L1/L2

Доказательство довольно простое. Пусть - FSA, принимающая регулярное множество R , где Q и F - соответственно множество состояний и множество принимающих состояний, и пусть L - произвольный язык. Пусть F ' = { д Q | у LM=(Q,Σ,δ,q0,F)RQFL множество состоянийиз которых конечное состояние может быть достигнуто путем приема строки из L .F={qQyLδ(q,y)F}L

Автомат , которая отличается от М только в своем множестве F ' конечных состояний признает именно Р / л . (Или см. Hopcroft-Ullman 1979, стр. 62 для доказательства этого факта.)M=(Q,Σ,δ,q0,F)MFR/L

Однако, когда множество не разрешимо, может не быть алгоритма для определения того, какие состояния имеют свойство, которое определяет F ' . Итак, хотя мы знаем, что множество F является подмножеством Q , у нас нет алгоритма для определения того, какое подмножество. Следовательно, пока мы знаем, что R принимается одним из 2 | Q | возможно FSA, мы не знаем, что это такое. Хотя должен признаться, мы знаем в значительной степени, как это выглядит.LFFQR2|Q|

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

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

Babou
источник
1
@WW Я сказал, что регулярно, но L произвольно . Он не должен быть рекурсивно перечислимым или регулярным. Никакое свойство L не используется, кроме того факта, что это набор строк. Если вы мне не доверяете, проверьте Hopcroft-Ullman 1979, стр. 62.RLL
babou
Благодарю. Это мой любимый ответ, потому что разрешимый язык бесконечен.
Эрел Сегал-Халеви
@babou, моя ошибка, я неправильно прочитал то, что ты написал. Моя вина - извините за это. Я отредактировал твой пост, чтобы сделать ту часть, которую я неправильно понял, надеюсь, понятнее.
DW
@WW Меня удивляет, что у тебя была проблема, но она случается и со мной. Но, возможно, мне следовало быть более ясным. Это не было преднамеренным. Говоря это, потому что некоторые математики думают, что более элегантно быть загадочным. Спасибо за редактирование.
Бабу
12

Чтобы расширить исходный комментарий Хендрика, рассмотрим эту проблему

n0nπ

Эта проблема разрешима, так как один из двух случаев может получить:

  1. NπN
  2. nπn

В случае (1) алгоритм решения проблемы будет одним из

n>N

и в случае (2) алгоритм будет

Ответьте "да".

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

Рик Декер
источник
+1 Это простой пример, который я помню, как использовал мой профессор в области вычислимости и логики. Это мой пример, так как он не требует большого знания предметной области, поэтому его легко передать.
Джошуа Тейлор
1
Для альтернативных формулировок, см. Также здесь .
Рафаэль
2

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

SS

HH

Дэвид Ричерби
источник