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

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

нашел на русском еще свежее:

http://www.isa.ru/proceedings/images/documents/2014-64-3/t-14-3_13-24.pdf
жалко доказательности в его статье мало по части асимптотики
но показывает он ту же "ленту решений" (стр 17, 18 нумерации) что и автор топика


Сочетания 3 по n давно известны, так что ничего удивительного. Но вот на 20 странице он своё решение "дорешивает". Так что видимо есть различия и существенные, в сам текст не вникал еще.
15 окт 21, 19:16    [22384342]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

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

автор
Предварительный этап решения заключается в унификации S1 и S2, так как унификация по
принципу действия сохраняет в структурахоперандах все существующие СВН и одновременно
минимизирует упомянутые структуры по числу элементов (строк).
очень тяжело его читать, лирика неуместная :-(

он кажется задачу к 2-КНФ сводит (там всё доказано и решено), а как - непонятно
15 окт 21, 19:18    [22384343]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

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

автор
Предварительный этап решения заключается в унификации S1 и S2, так как унификация по
принципу действия сохраняет в структурахоперандах все существующие СВН и одновременно
минимизирует упомянутые структуры по числу элементов (строк).
очень тяжело его читать, лирика неуместная :-(

он кажется задачу к 2-КНФ сводит (там всё доказано и решено), а как - непонятно


Надо почитать. Но вроде он параллельно показывает как 3сат и 2 сат его методом решать. Мой метод тоже умеет 2сат решать, но смысла в этом нет, 2 сат за линейное время решается.
15 окт 21, 19:25    [22384344]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

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

я и говорю что лирики много, а самого главного нема

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

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

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

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

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

я и говорю что лирики много, а самого главного нема

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


У меня смысл такой. Берешь ведро и синюю изоленту. Наматываешь изоленту на ведро, если буквы обоих концах изоленты сошлись, то красиво, если не сошлись - ведро выбрасывается ))))

Да, чуть не забыл. Без перехлёста не все варианты подойдут )))

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

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

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

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

а что, так можно? ))


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

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

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

а почему C(3, N) а не C(3, N) * 2^3 ?
20 окт 21, 17:58    [22385995]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

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

В первой версии один бит отвечал за одно состояние. Поэтому 2^3 это байт
20 окт 21, 18:47    [22386024]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

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

я в плане того спрашиваю, что троек то возможных не C(3,N), а в 8 раз больше (с учётом not-вариантов)
20 окт 21, 20:31    [22386063]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

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

я в плане того спрашиваю, что троек то возможных не C(3,N), а в 8 раз больше (с учётом not-вариантов)


не понял вопроса. Сочетаний 3 по n существует (n^3-3n^2+2n)/6. Число возможных размещений из {0,1} по 3 равно 2^3. Итого максимальное число размещений {0,1} в сочетаниях из n по 3 равно 8*(n^3-3n^2+2n)/6. Если каждое размещение 2 по 3 обозначить одним битом, то для хранение их всех потребуется(n^3-3n^2+2n)/6 байт. Или уточните о чем речь.

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

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

это я пытаюсь понять "Описание алгоритма решения задачи 3-КНФ", что откуда и зачем

из этого текста очень сложно понять, без гугления, что 8 состояний комбинаций для каждой тройки {vi, vj, vk}, это:
{vi | vj | vk}, {vi | vj | vk}, {vi | vj | vk}, ...


в этом блоке осталось осилить
автор
Векторы, соответствующие ограничениям 3-КНФ формулы помечаются как удаленные.
это какие? которые входят в формулу? зачем удалённые?
21 окт 21, 00:10    [22386166]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

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

если перефразировать блок "Описание алгоритма решения задачи 3-КНФ" человеческим языком, выходит следующее утверждение

Любую 3-КНФ формулу из n переменных можно представить в виде вектора состоящего из 8 * C(3, N) бит

теперь про то, что вы говорите далее, про операции с эти вектором

Возможно ли, подставив значение N-й переменной, получить однозначное 3-КНФ уравнение из (N-1) переменных ?
и если возможно, то как это сделать
21 окт 21, 09:10    [22386214]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

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

если перефразировать блок "Описание алгоритма решения задачи 3-КНФ" человеческим языком, выходит следующее утверждение

Любую 3-КНФ формулу из n переменных можно представить в виде вектора состоящего из 8 * C(3, N) бит

теперь про то, что вы говорите далее, про операции с эти вектором

Возможно ли, подставив значение N-й переменной, получить однозначное 3-КНФ уравнение из (N-1) переменных ?
и если возможно, то как это сделать


Можно на n получить просто удалив все векторы, соответствующие ограничению. В исходниках смотрите, там есть функция addconstraint(x). N-1 получить можно, это надо весь набор пересобирать, такого функционала у меня нет.

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

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

вот в чём и фигня

(v1, v2, vn) & (v7, v16, vn)

vn = 1

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

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

вот в чём и фигня

(v1, v2, vn) & (v7, v16, vn)

vn = 1

левый можно удалить, куда девать правый?


Ахаха. Да, логично. Правый никуда не девать. 2SAT выражение получается. Если vn это отрицание, то он равен 0. И из v7 v16 получаем 2SAT

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

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

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

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

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


здорово. осталось выяснить способ чего.

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

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

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

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

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


Хороший ход. Но ты не сможешь утоптать 2^n возможных решений в n-1 переменных. Вместо сочетаний n по 3 придётся использовать сочетания n по 4, что увеличит размер хранения полученной формулы.
21 окт 21, 22:55    [22386704]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
kealon(Ruslan)
Member

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

ничего особо не увеличит (кардинально во всяком случае), вместо 8*C(3,n) бит потребуется 8*C(3,n + 3)

например добавим 3 переменные (t0 = 0, t1 = 0, t2 =0) - это 7 известных соотношений.

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

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

фактически можно хранить в развёрнутом виде только разницу 8* [C(3,n + 3) - C(3,n)] бит, так как исходные блоки не меняются
22 окт 21, 00:01    [22386718]     Ответить | Цитировать Сообщить модератору
 Re: Решение NP-сложных задач за полиномиальное время  [new]
Верблюд
Member

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

фактически можно хранить в развёрнутом виде только разницу 8* [C(3,n + 3) - C(3,n)] бит, так как исходные блоки не меняются


Немного не понял, для чего вообще хранить t0 t1 t2, если они в задачу не входят? Сохранить не проблема, достаточно в начале сказать что в задаче на 3 переменных больше. Что с ними делать дальше?

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

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

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

Собственно невозможность подставки 1 натолкнула на мысль, что можно подставить не конкретно 1 или 0, а переменную.

Потом пришла мысль, что может получиться ситуация (vi, vi, vj) - что недопустимо, и я подумал, а почему бы не добавить соотношение которое однозначно задаёт переменные, количество решений это не увеличивает.
Т.е. это позволяет решить конкретную проблему: понижение уровня уравнения

Пойдём дальше:
из операции видно, что при подстановке всегда будет меняться только часть с включением этих добавленных переменных (помним, что для добавки достаточно 8* [C(3,n + 3) - C(3,n)] бит. ), что очень хорошо. Можно не хранить исходную функцию в развёрнутом виде, а просто помечать те переменные, которые уже найдены\предположены - и это можно сделать гораздо эффективнее (нужно лишь определиться с базовыми операциями).

Теперь вернёмся к тому, что говорит Aleksandr Sharahov
при подстановке у нас получается дробление на 2 ветки, Aleksandr Sharahov утверждает, что возможно задать такое уравнение
что при любой подстановке у вас не обнаружится коллизий и придётся опять дробить на 2. Логично, что в худшем случае вам придётся раздробиться на 2^N решений, что как бы уже относится к NP.

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

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

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