?
Complexity and expressivity of Branching- and Alternating-time temporal logics with finitely many variables
P. 396-414.
Rybakov M., Shkatov D.
We show that Branching-time temporal logics CTL and CTL*, as well as Alternating-time temporal logics ATL and ATL*, are as semantically expressive in the language with a single propositional variable as they are in the full language, i.e., with an unlimited supply of propositional variables. It follows that satisfiability for CTL, as well as for ATL, with a single variable is EXPTIME-complete, while satisfiability for CTL*, as well as for ATL*, with a single variable is 2EXPTIME-complete,—i.e., for these logics, the satisfiability for formulas with only one variable is as hard as satisfiability for arbitrary formulas.
Rybakov M., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45-60
We prove that branching-time temporal logics CTL and CTL* are polynomial-time embeddable into their single-variable fragments. It follows that satisfiability for CTL and CTL*, and therefore also for alternating-time temporal logics ATL and ATL*, in languages with one propositional variable is as algorithmically hard as satisfiability for the full logic: EXPTIME-complete for CTL and ATL, and 2EXPTIME-complete for CTL* and ATL*. We discuss applicability of the technique used in the proofs to other ...
Added: May 12, 2022
Rybakov M., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426-443
It is shown that products and expanding relativized products of propositional modal logics where one component is the minimal monomodal logic K are polynomial-time reducible to their single-variable fragments. Therefore, the nown lower bound complexity and undecidability results for such logics are extended to their single-variable fragments. Similar results are obtained for products where one component is a polymodal logic with a K-style ...
Added: September 24, 2020
Rybakov M., University of the Witwatersrand, Johannesburg, 2019
Modal logics, both propositional and predicate, have been used in computer science since the late 1970s. One of the most important properties of modal logics of relevance to their applications in computer science is the complexity of their satisfiability problem. The complexity of satisfiability for modal logics is rather high: it ranges from NP-complete to ...
Added: October 5, 2019
Rybakov M., Shkatov D., , in : Proceedings of the Annual Conference of the South African Institute of Computer Scientists and Information Technologists. : NY : ACM, 2018. P. 313-316.
It is known that both satisfiability and model-checking problems for propositional Linear-time Temporal Logic, LTL, with only a single propositional variable in the language are PSPACE-complete, which coincides with the complexity of these problems for LTL with an arbitrary number of propositional variables. In the present paper, we show that the same result can be ...
Added: October 6, 2019
Yaroslav Shitov, Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500-2502
We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...
Added: August 11, 2013
Malyshev D., Pardalos P. M., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called ...
Added: December 18, 2015
Andrey E. Krouk, Sergei Valentinovich Fedorenko, , in : 2019 XVI International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY). : IEEE, 2019. P. 115-116.
This article is dedicated to an alternative method of solving of the Chinese Remainder Theorem for polynomials. To construct the solution, a system of linear equations is constructed (using the method of undetermined coefficients) and then solved. The complexity of the proposed method is also calculated. ...
Added: October 27, 2019
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...
Added: June 23, 2013
Berlin : Springer, 2012
This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns ...
Added: October 30, 2013
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2012 Vol. 6 No. 1 P. 97-99
Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other ...
Added: December 7, 2012
Aleskerov F. T., Meshcheryakova N., Shvydun S. et al., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.
The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these ...
Added: June 8, 2016
Rubtsov A. A., Vyalyi M., , in : Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018. P. 295-307.
We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this ...
Added: June 21, 2018
Korpelainen N., Lozin V. V., Malyshev D. et al., Theoretical Computer Science 2011 No. 412 P. 3545-3554
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...
Added: September 11, 2012
Shitov Y., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Added: February 23, 2016
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791-801
For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain ...
Added: February 16, 2024
Mokeev D. B., Malyshev D., Optimization Letters 2020 Vol. 14 No. 6 P. 1317-1322
For a graph G and a positive integer k, a subset C of vertices of G is called a k-path vertex cover if C intersects all paths of k vertices in G. The cardinality of a minimum k-path vertex cover is denoted by β_{P_k}(G). For a graph G and a positive integer k, a subset ...
Added: March 12, 2020
Malyshev D., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...
Added: April 7, 2014
Malyshev D., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except ...
Added: October 3, 2013
Sirotkin D., Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 4 P. 759-769
The 3-coloring problem for a given graph consists in verifying whether it is possible
to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete
complexity classification is known for this problem for the hereditary classes defined by triples of
forbidden induced subgraphs, each on at most 5 vertices. In this article, ...
Added: November 20, 2018
Malyshev D., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for ...
Added: November 25, 2012
Alekseev V., Lozin V. V., Malyshev D. et al., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative ...
Added: November 7, 2012
Sirotkin D., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, ...
Added: July 2, 2018
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566-1595
We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...
Added: January 6, 2023
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...
Added: January 30, 2021