Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6]      все
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
kealon(Ruslan)

И я как бы не вижу у вас описание решения вопроса, который поднял Aleksandr Sharahov


Не понял про дробление. Что дробить? Заглянул в результат, который возвращает алгоритм. Список фиктивных переменных из него достаётся на раз. За исключением переменных входящих в логические взаимоблокировки назначений.
22 окт 21, 12:18    [22386817]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
Верблюд,


Вот смотрите, актуализация одной из переменных в 1 или 0 даёт две функции, каждую из которых надо решать.
Если допустить, что функция решаема, тут два решения: либо сразу выяснится, что 1 из них несовместима, либо в обоих случаях конфликта не будет
Допустим, вы прошлись по всем переменным и попробовали произвести такую замену
и оказывается, что конфликтов нет

ваши действия?
22 окт 21, 12:55    [22386833]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
Верблюд,

я вам простой пример приведу
допустим есть число
n = P1 * P2 - произведение двух простых

если я запишу в 3-кнф функцию описывающую уравнение
n mod a = 0

оно естественно будет иметь два решения 1 и P2 (я ограничу количество бит корнем из n)

соответственно лишь часть P2 будет иметь нулевые биты (а может и вообще не иметь)
для остальных переменных будет 1
и как вы не задавайте у вас для любой разбивки будут оба решения
22 окт 21, 13:20    [22386841]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
Короткое видео о том откуда появился алгоритм.

22 окт 21, 14:25    [22386870]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
Aleksandr Sharahov
Верблюд
пропущено...


У нас состояния в точке стыковки двух веток согласованы в обе стороны. По крайней мере до следующего уровня ветвления дерева. Если в процессе прохода от одного уровня ветвления до следующего маска поменялась, то следующее состояние будет полностью согласовано с обеими частями ветки выше очередной точки ветвления


Речь не о том, что согласовано или нет, а о том, как долго придется ходить и согласовывать.

Если грубо.
У нас матрешка, а у нее в самом конце может оказаться баба-яга.
На вопрос, что в конце не ответишь, пока всю матрешку не разберешь.
Но у нас в каждой матрешке не одна матрешка предыдущего уровня, а 100. И так на каждом уровне.
Переходя на предыдущий уровень по одной ветке, мы не особенно понижаем сложность задачи.
И чтобы ответить на вопрос, есть ли там хоть одна баба-яга, может потребоваться очень много проб.


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

Сообщение было отредактировано: 25 окт 21, 08:48
25 окт 21, 08:50    [22387539]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
Верблюд,

вот кстати
задавать значение переменным сложнее, чем выставлять равенство\неравенство переменных

т.е., если функция содержит два включения
(vi, vj, p1) и (vi, vj, p2)
и если при задании p1=p2 или p1 = not p2 выявится конфликт, то мы выразим одну переменную через другую

так же по аналогии с алгоритмом Карацубы
для (vi, pa, pb) и (vi, pc, pd) разрешение конфликтов подобным образом может дать 3 ветвления за 2 замены, а не 4


В литературе ещё есть разбиения функции на две независимых функции, у вас этот вопрос как-то вообще упущен.
25 окт 21, 14:40    [22387738]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
Верблюд,

ещё такая мысль: если алгоритм будет доказанно "стопориться" только при наличии нетривиальных решений, то такой алгоритм уже приобретёт ценность
25 окт 21, 14:51    [22387756]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
kealon(Ruslan)
Верблюд,

ещё такая мысль: если алгоритм будет доказанно "стопориться" только при наличии нетривиальных решений, то такой алгоритм уже приобретёт ценность


Я вроде нашел способ определить фиктивность всех переменных в результатах работы алгоритма за n^2 времени. Используя тот факт, что не бывает ложноотрицательных ответов. Вроде должен работать. Сижу думаю как это в программу воплотить, придётся isdeleted переделывать на метку времени.
25 окт 21, 19:18    [22387991]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
Верблюд
kealon(Ruslan)
Верблюд,

ещё такая мысль: если алгоритм будет доказанно "стопориться" только при наличии нетривиальных решений, то такой алгоритм уже приобретёт ценность


Я вроде нашел способ определить фиктивность всех переменных в результатах работы алгоритма за n^2 времени. Используя тот факт, что не бывает ложноотрицательных ответов. Вроде должен работать. Сижу думаю как это в программу воплотить, придётся isdeleted переделывать на метку времени.


Решение найдено. Описание тут:
27 окт 21, 22:09    [22389138]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
Верблюд,

опять в том же ракурсе, сложно понять это, и доказательности мало, речь вообще очень тяжело воспринимается

хотя какая-то аналогия идёт с заменой переменных для перевода в 2-КНФ
3 ноя 21, 09:20    [22391504]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
+
Верблюд
Короткое видео о том откуда появился алгоритм.


Ну что ж, попытаемся перевести на человеческий язык
есть такое понятие СКНФ, чем элементы 3-КНФ у нас и являются
автор
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. Отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля. В дизъюнкцию (это собственно то, что мы и имеем в виде 3-КНФ) записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.

Логически верен и обратный процесс, мы просто вычёркиваем в полной таблице истинности выражения которые есть в 3-КНФ. Н-р, если (abc) - вычёркиваем (000), если (abc) - вычёркиваем (010).
Для выражения из видео (abc)(abd)(acd)(bcd) изначально мы получим 4 такие таблички:
abc a bd ac d bcd
000 000 000 000
001 001 001 001
010 010 010 010
011 011 011 011
100 100 100 100
101 101 101 101
110 110 110 110
111 111 111 111


теперь бы ещё понять что автор подразумевает под словом "придём"
судя по словам "туда-обратно", напоминает какой-то алгоритм отжига, типа алгоритма Бржозовского

Сообщение было отредактировано: 9 ноя 21, 10:07
9 ноя 21, 10:05    [22393471]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6]      все
Все форумы / Программирование Ответить