Speciality:
01.01.09 (Discrete mathematics and mathematical cybernetics)
Birth date:
14.04.1945
Website: https://www.math.spbu.ru/user/kos/kos/html Keywords: computational complexity; lower bounds of complexity; program logic; discrete mathematics; heuristics in problem solving; nonclassical logic.
Subject:
A simple diophantine representation of solution sequence of Pell's equation was recieved (later a similar representation was recieved by M. Davis). A variant of foundation of constructive theory of probability was developed (as a base of Ph.D. thesis). For any natural k an example of NP-complete problem which cannot have a nondeterministic Turing Machine algorithm with polynomial of degree k upper time bound was proposed. The example consists in the problem of the existense of short (the length is not more than a polynomial of degree 2k+1) solutions of bit strings equations. Impossibility of a polynomial decision algorithm for solvability of boolean functional equations was prooved. A polynomial in time algorithm of solution search of a system of strict and nonstrict linear inequalities with integer coefficients was proposed. A number of papers (with A. V. Tishkov) were devoted to a sequent calculus for mixed many-valued Post and Lukacievich logic. It was proved that a problem of solvability of propositional fragment of this calculus belongs to EXP-LIN-TIME (as a proper subclass of EXP-TIME). The problem of satisfiability of a propositional formula of this calculus is NP-complete. Algorithmical undecidability of the universal theory of the ring of binary-rational numbers and decidability of the universal positive theory of nonstrict inequalities of both ring of rational numbers and ring of binary-rational numbers were proved. It was proved that the problem of solvability in real numbers of a strict polynomial inequality with integer coefficients belongs to NP. For every constant modulo the PSPACE-completeness of the problem of decidability of the elementary theory of comparisons this modulo was proved.
Main publications:
Kossovski N. Sequentcalculus for generalization of Getmanova's logic to the predicates. // The Bulletin of Symbolic Logic. V. 1, no. 2, June 1995. P. 245.
Beauquier D., Kossovski N., Smirnova E. An algorithm for solvsbility testing of elementary linear inequalities systems // Abstracts of the 6th IMACS International IMACS Conference on Applications of Computer Algebra. St. Petersburg, 2000. P. 59–61.
Kossovski N. The consistency checking of strict polynomial inequalities // Proc. Intern. Workshop on Logic and Complexity in Computer Science, University Paris 12, Creteil, France, 2001, p. 149–152.
