Программисты, что за класс задач "another solution problem"?

Slava33

Всё что мне известно, так их называют японцы. и не могу найти аналог в русской литературе. Вроде бы впервые это понятие ввели в 1996г. Uedo и Nagao.
Буду благодарен за ссылку на какой-нибудь русскоязычный источник или просто объяснение в посте Выбирать не приходится

zorin29

Ничего про это не знаю, чисто наугад предположу: поиск второго решения? (т.е. следующего по оптимальности)

Slava33

поиск второго решения?

Это ты у меня спрашиваешь? А для чего тогда я, по-твоему, тему завел?

nikita270601

The Another Solution Problem (ASP) of a problem Π is the following problem: for a given instance x of П and a solution s to it, find a solution to x other than s.

То есть, для данного экземляра x задачи П и его решения s, найти решение x, отличное от s.
Только я не уверен, что использовал общепринятую русскоязычную терминологию. Возможно, лучше было бы сказать "для данного конкретного случая x абстрактной задачи П" или что-то вроде того.

Slava33

Это определение, которое даже я смог бы перевести) А как этот класс задач на русском называется?

Slava33

Еще актуально

slonishka

"another solution problem"

это такой эвфемизм для слова совесть.

UAV27

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

Slava33

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

Спасибо

UAV27

Это отсебятина, я точно не знаю
Если угадал, скажи потом

Bibi

вообще, если я не ошибаюсь, то, что ты написал, называется NP. просто NP, без NP-полноты

UAV27

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

Bibi

что-то ты невнимателен

nikita270601

Это необязательно NP, потому что из его определения неочевидно, есть ли полиномиальный проверочный алгоритм. С другой стороны, насколько я понимаю, к another solution problem его определение тоже не имеет ни малейшего отношения.

Bibi

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

nikita270601

Выделил то слово, которое ты пропустил в моем предыдущем посте, пожирнее.

Bibi

! точно. спасибо

freestyle

Пока точного определения не было, так как не был описан класс задач, модель вычислений и т.д. Очень часто ASP — это задача проверки, единственное ли решение у головоломки (игры типа японских кроссвордов). Обычно в таком случае очевидна полиномиальная проверка данного решения.

freestyle

update: ASP лежит в классе FNP, который в свою очередь лежит в NP.
Определения можно смотреть тут, в разделе 2: http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf
Таким образом, проверочный алгоритм всегда есть по определению .

nikita270601

Тогда беру свои слова обратно!

apl13

Ты ваще жжошь.