4 papers · 1 filter
Logical characterizations of computational complexity classes
Vladimir Naidenko
Descriptive complexity theory is an important area in the study of computational complexity. In this direction, it is possible to describe combinatorial problems exclusively by log…
Logics for complexity classes
Vladimir Naidenko
A new syntactic characterization of problems complete via Turing reductions is presented. General canonical forms are developed in order to define such problems. One of these forms…
On some optimization problems for star-free graphs
V. G. Naidenko, Yu. L. Orlovich
It is shown that in star-free graphs the maximum independent set problem, the minimum dominating set problem and the minimum independent dominating set problem are approximable up…
Recursively Undecidable Properties of NP
V. G. Naidenko
We show that there cannot be any algorithm that for a given nondeterministic polynomial-time Turing machine determinates whether or not the language recognized by this machine belo…