Closure Properties and Characterizations of TotP

Y. Ivanashev

doi:10.1007/978-981-95-4839-2_2

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

Новости

25 мая 2026 г.

Биологи ВШЭ получили «молекулярный отпечаток» преэклампсии

Исследователи НИУ ВШЭ использовали новый способ моделирования состояния гипоксии в клетках плаценты при беременности, осложненной преэклампсией, и обнаружили молекулярные маркеры кислородного голодания тканей. Гипоксия — один из ключевых механизмов преэклампсии, полученные результаты важны для более точной и своевременной диагностики заболевания, а также для разработки эффективных методов лечения. Работа опубликована в журнале Placenta.

22 мая 2026 г.

Лаборатория живых смыслов: как проект НИУ ВШЭ и СахГУ переосмысляет труд

Проект «Зеркальные лаборатории» НИУ ВШЭ — Пермь и Сахалинского государственного университета (СахГУ) изучает, как культура, среда и технологии формируют и меняют трудовые смыслы. Исследование объединяет индивидуальный опыт, профессиональные нормы, городские проблемы, творческие практики и цифровые условия труда. Руководитель Лаборатории междисциплинарных исследований по антропологии труда НИУ ВШЭ в Перми Лилия Пантелеева рассказала о работе проекта.

21 мая 2026 г.

«Пик глупости» и «долина отчаяния»: экономисты НИУ ВШЭ предложили объяснение эффекта Даннинга - Крюгера

Эффект Даннинга — Крюгера, который описывает резкий всплеск уверенности в своих силах у новичков и такое же стремительное ее падение при наборе опыта, объясняется особенностями процесса обучения и набора новых знаний. К такому выводу пришли сотрудник факультета экономических наук НИУ ВШЭ Андрей Ворчик вместе с независимым исследователем Муратом Мамышевым. Они разработали математическую модель процесса обучения и показали, как формируется и изменяется субъективная уверенность по мере накопления знаний и как преподаватель может уменьшить «долину отчаяния» для ученика.

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации

?

Closure Properties and Characterizations of TotP

P. 15–24.

Иванашев Я. М.

Язык: английский

DOI

Текст на другом сайте

Ключевые слова: computational complexity counting problems closure properties #P

В книге

19th Annual Conference, TAMC 2025, Jinan, China, September 19–21, 2025, Proceedings. Theory and Applications of Models of Computation. Lecture Notes in Computer Science (LNCS, volume 16084)

Vol. 16084. , Springer, 2026.

19th Annual Conference, TAMC 2025, Jinan, China, September 19–21, 2025, Proceedings. Theory and Applications of Models of Computation. Lecture Notes in Computer Science (LNCS, volume 16084)

Springer, 2026.

Добавлено: 20 января 2026 г.

On algorithmic properties of propositional inconsistency-adaptive logics

Odintsov S., Сперанский С. О., Logic and Logical Philosophy 2012 Vol. 21 No. 3 P. 209–228

The present paper is devoted to computational aspects of propositional inconsistency-adaptive logics. In particular, we prove (relativized versions of) some principal results on computational complexity of derivability in such logics, namely in cases of CLuN-r and CLuN-m , i.e., CLuN supplied with the reliability strategy and the minimal abnormality strategy, respectively. ...

Добавлено: 27 декабря 2025 г.

Computability issues for adaptive logics in multi-consequence standard format

Сперанский С. О., Studia Logica 2013 Vol. 101 No. 6 P. 1237–1262

In a rather general setting, we prove a number of basic theorems concerning computational complexity of derivability in adaptive logics. For that setting, the so-called standard format of adaptive logics is suitably adopted, and the corresponding completeness results are established in a very uniform way. ...

Добавлено: 27 декабря 2025 г.

A note on definability in fragments of arithmetic with free unary predicates

Сперанский С. О., Archive for Mathematical Logic 2013 Vol. 52 No. 5–6 P. 507–516

We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates — which are strongly related to definability in ...

Добавлено: 27 декабря 2025 г.

NP-полнота игры “Ханаби” при минимальных параметрах

Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216

Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...

Добавлено: 23 ноября 2025 г.

Overview of methods to improve execution time in image steganography and watermarking

Мельман А. С., Джанашиа К. М., Евсютин О. О., Computer Standards and Interfaces 2026 Vol. 96 Article 104066

Добавлено: 3 сентября 2025 г.

Low Sets and Closure Properties of Counting Function Classes

Иванашев Я. М., / Series Computer Science "arxiv.org". 2025.

Добавлено: 29 июля 2025 г.

Partitioning vertices of graphs into paths of the same length

Duginov O., Dmitriy Malyshev, Dmitriy Mokeev, Discrete Applied Mathematics 2025 Т. 373 С. 179–195

Given a graph, the (induced) P_k-partition problem is to decide whether its vertex set can be partitioned into subsets, each of which induces (the k-path) a k-vertex subgraph with a Hamiltonian path. We show that these problems are NP-complete for planar subcubic bipartite (H_1,H_2,...,H_ℓ)-free graphs of girth g, for any k,g≥3,l≥1, where Hi is obtained ...

Добавлено: 3 мая 2025 г.