RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Авторский договор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. МИАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. МИАН, 2003, том 242, страницы 23–43 (Mi tm403)  

Эта публикация цитируется в 18 научных статьях (всего в 18 статьях)

Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных

М. В. Алехновичa, А. А. Разборовb

a Московский государственный университет им. М. В. Ломоносова
b Математический институт им. В. А. Стеклова РАН

Аннотация: Обобщаются недавние линейные нижние оценки на степень вывода в полиномиальном исчислении, основанные на рассмотрении биномиальных идеалов. Мы предлагаем достаточно общий критерий трудности булевых функций (называемый нами иммунностью), которому, в частности, удовлетворяет случайная булева функция, и доказываем нижние оценки на степень вывода для широкого класса тавтологий, основанных на иммунных функциях. В качестве одного из приложений наших методов мы обобщаем цейтиновские тавтологии по модулю $p$ на случай булевых переменных (т.е. в присутствии аксиом $x_i^2=x_i$) и доказываем трудность их вывода в полиномиальном исчислении над любым полем характеристики, отличной от $p$. Затем по аналогии с цейтиновскими мы определяем “потоковые” тавтологии, основанные на функции голосования, и показываем их трудность над любым полем. Также мы доказываем нижнюю оценку $\Omega(n)$ на степень вывода случайных $k$-КНФ в полиномиальном исчислении над полями характеристики 2.

Полный текст: PDF файл (334 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics, 2003, 242, 18–35

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.6
Поступило в октябре 2002 г.

Образец цитирования: М. В. Алехнович, А. А. Разборов, “Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Тр. МИАН, 242, Наука, М., 2003, 23–43; Proc. Steklov Inst. Math., 242 (2003), 18–35

Цитирование в формате AMSBIB
\RBibitem{AleRaz03}
\by М.~В.~Алехнович, А.~А.~Разборов
\paper Нижние оценки для полиномиального исчисления в~случае идеалов,
отличных от биномиальных
\inbook Математическая логика и алгебра
\bookinfo Сборник статей. К~100-летию со дня рождения академика Петра Сергеевича Новикова
\serial Тр. МИАН
\yr 2003
\vol 242
\pages 23--43
\publ Наука
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm403}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2054483}
\zmath{https://zbmath.org/?q=an:1079.03047}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2003
\vol 242
\pages 18--35


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tm403
  • http://mi.mathnet.ru/rus/tm/v242/p23

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Alekhnovich M., Ben-Sasson E., Razborov A.A., Wigderson A., “Pseudorandom generators in propositional proof complexity”, SIAM J. Comput., 34:1 (2004), 67–88  crossref  mathscinet  zmath  isi
    2. Razborov A.A., “Feasible proofs and computations: Partnership and fusion”, Automata, languages and programming, 31st international colloquium, ICALP 2004 (Turku, Finland, July 12–16, 2004), Proceedings, Lecture Notes in Comput. Sci., 3142, 2004, 8–14  crossref  zmath  isi
    3. Razborov A.A., “Feasible proofs and computations: Partnership and fusion”, 19th Annual IEEE Symposium on Logic in Computer Science, Proceedings, Proceedings/Symposium on Logic in Computer Science, 2004, 134–138  isi
    4. Segerlind N., “The complexity of propositional proofs”, Bull. Symbolic Logic, 13:4 (2007), 417–481  crossref  mathscinet  zmath  isi  elib
    5. Raz R., “Elusive Functions and Lower Bounds for Arithmetic Circuits”, Stoc'08: Proceedings of the 2008 Acm International Symposium on Theory of Computing, 2008, 711–720  mathscinet  zmath  isi
    6. Ben-Sasson E., Impagliazzo R., “Random Cnf's are Hard for the Polynomial Calculus”, Comput Complexity, 19:4 (2010), 501–519  crossref  mathscinet  zmath  isi  elib
    7. Borodin A., Pitassi T., Razborov A., “Special Issue in Memory of Misha Alekhnovich. Foreword”, Comput Complexity, 20:4 (2011), 579–590  crossref  mathscinet  zmath  isi  elib
    8. Alekhnovich M., “Lower Bounds for K-DNF Resolution on Random 3-CNFS”, Comput Complexity, 20:4 (2011), 597–614  crossref  mathscinet  zmath  isi  elib
    9. Alekhnovich M., Razborov A., “Satisfiability, Branch-Width and Tseitin Tautologies”, Comput Complexity, 20:4 (2011), 649–678  crossref  mathscinet  zmath  isi  elib
    10. Buss S.R., “Towards NP-P via proof complexity and search”, Ann Pure Appl Logic, 163:7 (2012), 906–917  crossref  mathscinet  zmath  isi  elib
    11. Filmus Yu., Lauria M., Nordstroem J., Thapen N., Ron-Zewi N., “Space Complexity in Polynomial Calculus”, 2012 IEEE 27th Annual Conference on Computational Complexity (Ccc), Annual IEEE Conference on Computational Complexity, IEEE, 2012, 334–344  crossref  mathscinet  isi
    12. Nordstrom J., “Pebble Games, Proof Complexity, and Time-Spacetrade-Offs”, Log. Meth. Comput. Sci., 9:3 (2013), 15  crossref  mathscinet  zmath  isi  elib
    13. Atserias A., Lauria M., Nordstrom J., “Narrow Proofs May Be Maximally Long”, 2014 IEEE 29Th Conference on Computational Complexity (Ccc), IEEE Conference on Computational Complexity, IEEE, 2014, 286–297  crossref  mathscinet  isi
    14. Nordstrom J., “a (Biased) Proof Complexity Survey For Sat Practitioners”, Theory and Applications of Satisfiability Testing - Sat 2014, Lecture Notes in Computer Science, 8561, eds. Sinz C., Egly U., Springer-Verlag Berlin, 2014, 1–6  crossref  mathscinet  zmath  isi
    15. Miksa M., Nordstrom J., “Long Proofs of (Seemingly) Simple Formulas”, Theory and Applications of Satisfiability Testing - Sat 2014, Lecture Notes in Computer Science, 8561, eds. Sinz C., Egly U., Springer-Verlag Berlin, 2014, 121–137  crossref  mathscinet  zmath  isi
    16. Bonacina I., Galesi N., “a Framework For Space Complexity in Algebraic Proof Systems”, J. ACM, 62:3 (2015), 23  crossref  mathscinet  zmath  isi  elib
    17. Filmus Yu., Lauria M., Nordstrom J., Ron-Zewi N., Thapen N., “Space Complexity in Polynomial Calculus”, SIAM J. Comput., 44:4 (2015), 1119–1153  crossref  mathscinet  zmath  isi  elib
    18. Atserias A., Lauria M., Nordstrom J., “Narrow Proofs May Be Maximally Long”, ACM Trans. Comput. Log., 17:3 (2016), 19  crossref  mathscinet  isi  elib  scopus
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Просмотров:
    Эта страница:282
    Полный текст:66
    Литература:19

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017