Closure Properties and Characterizations of TotP

Y. Ivanashev

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

АБВ
АБВ
АБВ

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

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

по году

Тематика

Новости

5 июня 2026 г.

Аспирантка НИУ ВШЭ открыла «невидимую» планировку античного Париона

Исследовательница из НИУ ВШЭ Идиль Малгиль изучила с помощью дрона с лазерным сканером сверхвысокого разрешения древнеримский город Парион, расположенный на территории современной Турции. Благодаря высокой плотности сканирования удалось зафиксировать крошечные неровности рельефа, скрытые под землей и растительностью. Обнаружены следы целых кварталов, террасных систем и стен, которые невозможно было различить ни при обычных раскопках, ни с помощью аэрофотосъемки. Результаты исследованияо публикованы в международном научном журнале Ancient Civilizations from Scythia to Siberia.

2 июня 2026 г.

От Волги до Янцзы: математики из Нижнего Новгорода и Шанхая изучают устойчивость систем

Математики НИУ ВШЭ в Нижнем Новгороде совместно с коллегами из шанхайского Университета Тунцзи исследуют фундаментальные причины структурной устойчивости систем и механизмы их нарушения. О развитии проекта Qualitative Theory of Systems of Ordinary and Partial Differential Equations в рамках программы НИУ ВШЭ «Международное академическое сотрудничество» «Вышке.Главное» рассказала его руководитель, профессор Ольга Починка, заведующая Международной лабораторией динамических систем и приложений НИУ ВШЭ в Нижнем Новгороде.

4 июня 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.

Universal Comparison Methodology for Hough Transform Approaches

Kazimirov D., Vitalii Gulevskii, Kroshnin A. и др., Mathematics 2026 Article 1136

Добавлено: 28 мая 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 г.