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.

Graduated from Faculty of Mathematics and Mechanics of Leningrad State University (LSU, now SPbSU) in 1966 (speciality of mathematical logic). Ph.D. thesis was defended in 1970. D.Sci. thesis was defended in 1988 at M.V.Lomonosov Moscow State University (MSU). A list of my works contains more than 150 titles. In 1994 I was Adviser of Sy.Petersburg team in the Eastern European Regional Contest of 19th Annual International Collegiate Programming Contest of ACM (Romania).

In 1963 I was a winner of mathematical student tournament between Leningrad and Moscow state universities. In 1985 -- recieved a gratitude of the rector of Leningrad state university for education of Universities' prpfessors in computer science. In 1988 -- awarded by honorable credentials of Ministry of University Education of Russia for the book "Base of elementary algorithm theory",Leningrad, LSU, 1987. 152p. In 1999 -- awarded by honorable credentials of rector of St.Petersburg State University for scientific and educational activity. In 2001 -- awarded by sign of honorable educationalist for educational activities by Ministry of Russia education.

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

• St. Petersburg State University, Mathematics and Mechanics Faculty
• St. Petersburg Mathematical Society