Closure Properties and Characterizations of TotP (original) (raw)

• Книги
• Статьи
• Главы в книгах
• Препринты
• Верификация публикаций
• Расширенный поиск
• Правила использования материалов
• Наука в ВШЭ

В книге

Vol. 16084. , Springer, 2026.

Springer, 2026.

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

, Сперанский С. О., 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 г.

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 г.

Сперанский С. О., 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 г.

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

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

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

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

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

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

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 г.