Вопросы с тегом «permanent»

24
Существует ли прямое / естественное сокращение для подсчета двойных совершенных совпадений с использованием перманента?

Подсчет количества совершенных совпадений в двудольном графе сразу сводится к вычислению перманента. Поскольку поиск идеального соответствия в двудольном графе есть в NP, существует некоторое сокращение от двудольных графов к перманенту, но это может привести к неприятному полиномиальному взрыву,...

22
Нижняя граница для определителя и постоянного

В свете недавней пропасти на глубине 3 результата (который, среди прочего, дает глубины 3 арифметическая схема дляп×попределителя надС), у меня следующие вопросы: Григорьев и Карпиньскидоказалв2Ом(п)нижняя граница для любой глубины-3 арифметической схемы вычислительной Определительп×пматрицы над...

20
Легкие проблемы с жесткими подсчетами версий

В Википедии приводятся примеры проблем, где версия для подсчета трудна, а версия для принятия решения проста. Некоторые из них подсчитывают идеальные соответствия, подсчитывают количество решений для SAT и количество топологических сортировок.222 Существуют ли другие важные классы (например,...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

16
Можем ли мы решить, есть ли у перманента уникальный термин?

Предположим, нам дана матрица n по n, M, с целочисленными элементами. Можем ли мы решить в P, существует ли перестановка такая, что для всех перестановок мы имеем ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Мя σ( я )≠ П Мя π( я )ΠMяσ(я)≠ΠMяπ(я)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Замечания. Конечно, можно...

15
Релятивизируют ли доказательства того, что перманент не является равномерным

Это продолжение этого вопроса и связано с этим вопросом Шивы Кинали. Кажется, что доказательства в этих работах ( Аллендер , Кауссин-Маккензи-Териен-Фольмер , Койран-Перифель ) используют теоремы иерархии. Я хочу знать, являются ли доказательства « чистыми » теоремами диагонализации или они...

14
Вопрос к # P-полному доказательству перманента от Ben-Dor / Halevi

В статье Бен-Дор / Галеви [1] приводится еще одно доказательство того, что перманент является -завершенным. В более поздней части статьи они показывают цепочку сокращений то время как постоянное значение сохраняется вдоль цепи. Так как число постоянных назначений формулы 3SAT может быть получено из...

12
Выражение определителя как постоянного

Одной из основных проблем в TCS является проблема выражения перманента в качестве детерминанта. Я читал статью Агравала « Детерминант против перманента», и в одном абзаце он утверждает, что обратная проблема проста. Легко видеть , что определитель матрицы может быть выражен как перманент...

11
Решает ли изменение одной записи уменьшение перманента матрицы в полиномиальной иерархии?

Рассмотрим следующую задачу: для заданной матрицы , индексов i , j ∈ { 1 , … , n } и целого числа a . Заменить M [ я , J ] по и вызвать новую матрицу M . Является ли p e r ( M ) > pM∈{−m,…,0,…,m}n×nM∈{−m,…,0,…,m}n×nM\in\{-m,\dots,0,\dots,m\}^{n\times...

9
Перманент матрицы и из определителей

Пусть будет матрица или с элементами . Может ли кто-нибудь предоставить мне матрицу чтобы ? Что такое наименьший явный B, который известен таким образом, что \ operatorname {per} (A) = \ det (B) ? Любые ссылки на это с явными примерами?AAA3 × 33×33 \times 34 × 44×44 \times 4aя жaija_{ij}ВBBв( A ) =...

9
Отмена и определитель

Алгоритм Берковица обеспечивает схему полиномиального размера с логарифмической глубиной для определителя квадратной матрицы с использованием степеней матрицы. Алгоритм неявно использует отмену. Является ли аннулирование необходимым для получения схемы полиномиального размера с логарифмической или...