А вы используете алгоритм в какой то практической задаче, или просто ради научного интереса??
Нет, я не использую этот алгоритм на практике, но уверен, что он имеет множество практических и теоретических применений.
Что нибудь можете сказать по поводу habrahabr.ru/post/225831/?
Полиномиальное решение задачи о покрытии множества влекло бы равенство P и NP. К сожалению, утверждение теоремы 2 не верно в общем случае. В теореме один Вы описываете некоторые из минимальных покрывающих множеств, но не все. В теореме два Вы говорите, что если выбрать наименьшее из описанных Вами минимальных множеств, то Вы получите наименьшее покрывающее множество. Это было бы верно, если бы Вы рассматривали множество всех минимальных покрытий, однако Вы рассматриваете лишь его подмножество.
То есть, в теореме 1 каждое Ваше решение соответствует минимального множеству, но обратное утверждение не верно. В теореме 2 Вы как раз пользуетесь обратным утверждением: Вы подразумеваете, что каждое минимальное покрытие описывается в теореме 1.
Вот по этой ссылке перечислены некоторые криптографические примитивы, которые существуют без каких-либо предположений (существование односторонней ф-ции, P!=NP и.т.д.) cstheory.stackexchange.com/a/20085
Нет, дополнительных трудностей нет. После поступления можно подавать на визы F1 и J1. В 90% случаев студенты подают на визу F1. Получив визу одного типа Вы можете позже поменять ее на визу другого типа (это не очень просто, как я понимаю).
Право на работу.
F1. Вы не имеете права работать, но имеете право подрабатывать в своем университете, проходить интернатуры и, на самом деле, делать все, что Вы можете успевать, являясь студентом)
J1-студенты имеют право работать, только если их учебная программа обязывает их работать (что, как я понимаю, большая редкость).
Супруги.
Супруги F1-студентов получают визу F2 и не имеют права работать.
Супруги J1-студентов получают, соответственно, визу J2 и имеют право работать.
Правило двух лет.
F1 — нет такого правила.
J1 — есть такое правило. Это правило означает, что по окончании обучения Вы должны приехать на Родину и пробыть там два года до Вашей следующей поездки в США. Я не встречал людей, которые бы понимали, когда это правило применяется, а когда не применяется)
Ходят слухи, что получение J1 может занять чуть больше времени.
скрывает полиномиальные множители от длины входа, т.е. . Этим мы просто хотим сказать, что нам не очень интересно оценивать какой именно полином стоит перед .
Да, конечно. Если Вам хочется почитать именно алгоритм динамиеского программирования, то его можно найти здесь: Bellman (1962) и здесь Held, Karp (1971). Алгоритм из статьи можно почитать здесь.
Это, вроде, не всегда сработает. Если информация о ключах не попала в удаленный процент, то, возможно, Вы сможете расшифровать почти все.
Такие системы можно организовать используя, например, All or Nothing Hash Functions. Грубо говоря, каждый байт выхода зависит от каждого байта входа и наоборот. Удалив 0.1% выхода, Вы теряете информацию о всем входе. Проблема такого рода систем в том, что они статичны. То есть, если Вы захотите к закодированному тексту добавить пару байт, то придется кодировать все заново.
Я имею в виду, почему Вы не считаете битовую сложность? Если Вы говорите о числах длины k, то нужно операции над числами длины k считать не константными.
Спасибо за статью.
Видимо я что-то не понял в подсчёте сложности. Поясните, пожалуйста. Вопрос по простому алгоритму. Что мы считаем элементарной операцией? Считаете ли вы любую функции high и low требующими одну операцию? Обращение по индексу длины k/2 является одной операцией?
существования односторонних функций, которые в свою очередь существуют, если P != NP.
Это пока доказано только в обратную сторону. То есть если P!=NP, то не факт, что существуют односторонние функции. Однако, если существуют односторонние функции, то, очевидно, P!=NP.
То есть, существование односторонних функций доказать сложнее, чем P!=NP.
Да, но я имел в виду то, что
>>Построение универсального синтаксического анализатора с приемлемой вычислительной сложностью
вполне возможно для КС-грамматик, если говорить о классе P.
Да, это известный метод анализа КС-грамматик. Если я правильно понял псевдокод, то это очень похоже на анализатор методом рекурсивного спуска (нисходящий). Но если Вы это придумали сами — то, по-моему, это замечательно!
2SabMaks: в статье говорится про синтаксический анализ именно для КС-языков. Грамматики типа 0 и типа 1 задают более широкий класс языков. Построение универсального анализатора для КС-языков — вещь и теоретически и практически осуществимая. Возьмите, например, алгоритм Кока-Янгера-Касами.
2gribozavr: всё-таки, скорее всего приемлемой сложностью здесь разумно считать линейное время.
Так как
1)за полином (от размера грамматики) можно привести любую КС-грамматику к форме Хомского,
2)а за куб времени и квадрат памяти можно запустить Кока-Янгера-Касами для любой КС-грамматики в форме Хомского,
то эта задача лежит в P. Однако, интересны как раз те случаи, когда работают линейные по времени анализаторы (LL, SLR, LR, операторные и.т.д).
Любая оптимизационная задача из NP сводится не к некоторому языку из NP.
Тут, видимо, я не очень понятно объяснил именно формальное отличие. То есть, P и NP — это классы (множества) языков. Язык — это просто набор слов (строк, чисел, графов, пар...). Так вот язык, который состоит из графов, имеющих вершинное покрытие не больше k — NP-полный язык. А задача определения вот такого вот k по графу — это не язык. Это задача, которая также трудна, как и все языки из NP. Поэтому задача и называется NP-трудной.
Возможно, я не очень подробно это описал. Но на каждой итерации алгоритма мы удаляем все ребра, инцидентные выбранным вершинам. Это значит, что мы никогда больше не сможем выбрать ребро, инцидентное вершинам из S.
Нет, я не использую этот алгоритм на практике, но уверен, что он имеет множество практических и теоретических применений.
Полиномиальное решение задачи о покрытии множества влекло бы равенство P и NP. К сожалению, утверждение теоремы 2 не верно в общем случае. В теореме один Вы описываете некоторые из минимальных покрывающих множеств, но не все. В теореме два Вы говорите, что если выбрать наименьшее из описанных Вами минимальных множеств, то Вы получите наименьшее покрывающее множество. Это было бы верно, если бы Вы рассматривали множество всех минимальных покрытий, однако Вы рассматриваете лишь его подмножество.
То есть, в теореме 1 каждое Ваше решение соответствует минимального множеству, но обратное утверждение не верно. В теореме 2 Вы как раз пользуетесь обратным утверждением: Вы подразумеваете, что каждое минимальное покрытие описывается в теореме 1.
cstheory.stackexchange.com/a/20085
Право на работу.
F1. Вы не имеете права работать, но имеете право подрабатывать в своем университете, проходить интернатуры и, на самом деле, делать все, что Вы можете успевать, являясь студентом)
J1-студенты имеют право работать, только если их учебная программа обязывает их работать (что, как я понимаю, большая редкость).
Супруги.
Супруги F1-студентов получают визу F2 и не имеют права работать.
Супруги J1-студентов получают, соответственно, визу J2 и имеют право работать.
Правило двух лет.
F1 — нет такого правила.
J1 — есть такое правило. Это правило означает, что по окончании обучения Вы должны приехать на Родину и пробыть там два года до Вашей следующей поездки в США. Я не встречал людей, которые бы понимали, когда это правило применяется, а когда не применяется)
Ходят слухи, что получение J1 может занять чуть больше времени.
Такие системы можно организовать используя, например, All or Nothing Hash Functions. Грубо говоря, каждый байт выхода зависит от каждого байта входа и наоборот. Удалив 0.1% выхода, Вы теряете информацию о всем входе. Проблема такого рода систем в том, что они статичны. То есть, если Вы захотите к закодированному тексту добавить пару байт, то придется кодировать все заново.
Видимо я что-то не понял в подсчёте сложности. Поясните, пожалуйста. Вопрос по простому алгоритму. Что мы считаем элементарной операцией? Считаете ли вы любую функции high и low требующими одну операцию? Обращение по индексу длины k/2 является одной операцией?
Это пока доказано только в обратную сторону. То есть если P!=NP, то не факт, что существуют односторонние функции. Однако, если существуют односторонние функции, то, очевидно, P!=NP.
То есть, существование односторонних функций доказать сложнее, чем P!=NP.
Ноябрь 2010 «Microsoft launches the Windows Phone 7» в рамке неправильного цвета.
>>Построение универсального синтаксического анализатора с приемлемой вычислительной сложностью
вполне возможно для КС-грамматик, если говорить о классе P.
2SabMaks: в статье говорится про синтаксический анализ именно для КС-языков. Грамматики типа 0 и типа 1 задают более широкий класс языков. Построение универсального анализатора для КС-языков — вещь и теоретически и практически осуществимая. Возьмите, например, алгоритм Кока-Янгера-Касами.
2gribozavr: всё-таки, скорее всего приемлемой сложностью здесь разумно считать линейное время.
Так как
1)за полином (от размера грамматики) можно привести любую КС-грамматику к форме Хомского,
2)а за куб времени и квадрат памяти можно запустить Кока-Янгера-Касами для любой КС-грамматики в форме Хомского,
то эта задача лежит в P. Однако, интересны как раз те случаи, когда работают линейные по времени анализаторы (LL, SLR, LR, операторные и.т.д).
Тут, видимо, я не очень понятно объяснил именно формальное отличие. То есть, P и NP — это классы (множества) языков. Язык — это просто набор слов (строк, чисел, графов, пар...). Так вот язык, который состоит из графов, имеющих вершинное покрытие не больше k — NP-полный язык. А задача определения вот такого вот k по графу — это не язык. Это задача, которая также трудна, как и все языки из NP. Поэтому задача и называется NP-трудной.