Пусть мы умеем находить ответ на вопрос: "существует ли в произвольном графе Гамильтонов цикл" за полиномиальное время. Другими словами пусть NP=P.

Пусть дан граф G(n) с действительными, положительными весами и действительное число $%\alpha%$%.

a) Докажите что тогда задача существования в G(n) Гамильтонова цикла длины меньшей $%\alpha%$% принадлежит классу P.

б) Сводится ли задача поиска наименьшего Гамильтонова цикла к задаче пункта (а) за полиномиальное время?

задан 27 Ноя '17 3:58

Вопросы а и б независимы. И интереснее ответ сразу на вопрос (б).

(27 Ноя '17 4:03) abc

@abc: алгоритмы не умеют работать с произвольными действительными числами. Поэтому их обычно считают целыми (на худой конец, рациональными).

Если в графе есть цикл с весом меньше a, то недетерминистский алгоритм его находит за полиномиальное время. В предположении, что P=NP, должен быть и детерминистский.

Что касается пункта б), то можно положить a равным сумме всех весов, а потом делить пополам, и спрашивать алгоритм о существовании цикла. Тогда мы найдём наименьший по весу цикл.

(27 Ноя '17 5:30) falcao
  1. Вроде никто не мешает нам определить машину Тьюринга с вшитой вещественной арифметикой. И в отношении таких алгоритмов ставить вопрос.

  2. "Если в графе есть цикл с весом меньше a, то недетерминистский алгоритм его находит за полиномиальное время." не понял как находит? наш алгоритм должен использовать полиномиальную процедуру отвечающую да/нет на вопрос существует ли в графе гамильтонов цикл. Как он это использует?

  3. Если мы делим $%\alpha$% пополам, то сложность алгоритма становится зависимой от $%\alpha$%. Это я запрещаю. Разрешаю только вшитую вещественную арифметику (+,-,<,>,=,итд).

(27 Ноя '17 9:16) abc

@abc: по идее, можно рассмотреть какую-то систему, которая работает с вещественными числами как с чем-то уже "готовым", только это будут уже не машины Тьюринга и не алгоритмы. Тогда всю концепцию придётся пересматривать, и понятия сложности вычислений тоже как-то придётся переопределять. Главное, непонятно, зачем это нужно. Ведь мы всё равно работаем с вещественными числами, принадлежащими конечно-порождённой подгруппе в (R,+), а она устроена проще.

ND-алгоритм, как всегда, угадывает цикл, а потом проверяет за линейное время, что его вес не больше a. Значит, задача принадлежит NP=P.

(27 Ноя '17 9:42) falcao

@falcao Я немного подумал и решил что действительные веса для меня не принципиальны. Пусть все веса ребер у нас натуральные числа. Главный вопрос такой - как угадать этот злоcчастный цикл за полиномиальное время? Делить веса пополам мы не имеем права, потому что тогда сложность алгоритма начинает зависеть от значений весов, а по моим условиям она должна зависеть только от n и ничего другого.

(27 Ноя '17 12:21) abc

@abc: сложность не может зависеть только от n. Для того, чтобы просто ознакомиться с весом ребра, его надо прочитать. Это занимает log w единиц времени, где w -- вес. Если мы делим пополам, то времени уходит примерно столько же.

(27 Ноя '17 15:18) falcao

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

(27 Ноя '17 20:03) abc

@abc: иногда абстрагируются, иногда нет, но если это делать, пренебрегая разрядностью, то проблема сама собой снимается. Числа (веса) считаются принадлежащими фиксированному диапазону. Для практических соображений этого больше чем достаточно. Например, если мы считаем расходы на поездку коммивояжёра, то триллиона всяко хватит, а тогда деление пополам осуществляется в константное число шагов.

(27 Ноя '17 20:34) falcao

Понятно, просто я в другую сторону абстрагировался, в сторону неограниченных чисел, но видимо так не делают.

Тогда еще вопрос (а) остается. Пусть мы умеем отвечать на вопрос есть ли в графе гамильтонов цикл или нет. Как тогда ответить на вопрос, есть ли в графе гамильтонов цикл меньше a?

(27 Ноя '17 20:39) abc

@abc: в этой теории такого явления нет. Это наподобие того, как границы массивов в языках типа Pascal являются константами. Мне когда-то это ограничение казалось неудобством, но потом я осознал, что только в математике бывают "абстрактные" числа, а в программировании их нет. То есть не только действительных чисел там нет, но нет ничего "неограниченного большого".

(27 Ноя '17 20:47) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×129
×41

задан
27 Ноя '17 3:58

показан
159 раз

обновлен
27 Ноя '17 20:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru