2 citations · 4 across the 12 of their papers we have counts for
12 papers
Searching isomorphic graphs
Anatoly D. Plotnikov
To determine that two given undirected graphs are isomorphic, we construct for them auxiliary graphs, using the breadth-first search. This makes capability to position vertices in…
Polynomial-time algorithm for determining the graph isomorphism (v.2)
Anatoly D. Plotnikov
We develop the methodology of positioning graph vertices relative to each other to solve the problem of determining isomorphism of two undirected graphs. Based on the position of t…
On non-canonical solving the Satisfiability problem
Anatoly D. Plotnikov
We study the non-canonical method for solving the Satisfiability problem which given by a formula in the form of the conjunctive normal form. The essence of this method consists in…
On a logical model of combinatorial problems
Anatoly D. Plotnikov
The paper proposes a logical model of combinatorial problems, also it gives an example of a problem of the class NP that can not be solved in polynomial time on the dimension of th…
On the structure of the class NP
Anatoly D. Plotnikov
A new class UF of problems is introduced, strictly included in the class NP, which arises in the analysis of the time verifying the intermediate results of computations. The implic…
About set-theoretic properties of one-way functions
Anatoly D. Plotnikov
We investigate the problem of cryptanalysis as a problem belonging to the class NP. A class of problems UF is defined for which the time constructing any feasible solution is polyn…
On the relationship between classes P and NP
Anatoly D. Plotnikov
In this paper we discusses the relationship between the known classes P and NP. We show that the difficulties in solving problem "P versus NP" have methodological in nature. An alg…
Encipher of information on the basis of geometrical presentations
A. S. Petrov, A. D. Plotnikov
In this paper, we examine a ciphertext on the basis of using geometrical objects. Each symbol normative alphabet is determined as a point on the plane. We consider possible ways fo…
Experimental Algorithm for the Maximum Independent Set Problem
Anatoly D. Plotnikov
We develop an experimental algorithm for the exact solving of the maximum independent set problem. The algorithm consecutively finds the maximal independent sets of vertices in an…
Formalization of the class of problems solvable by a nondeterministic Turing machine
Anatoly D. Plotnikov
The objective of this article is to formalize the definition of NP problems. We construct a mathematical model of discrete problems as independence systems with weighted elements.…
A class of problems of NP to be worth to search an efficient solving algorithm
Anatoly D. Plotnikov
We examine possibility to design an efficient solving algorithm for problems of the class \np. It is introduced a classification of \np problems by the property that a partial solu…
Designing SAT for HCP
Anatoly D. Plotnikov
For arbitrary undirected graph , we are designing SATISFIABILITY problem (SAT) for HCP, using tools of Boolean algebra only. The obtained SAT be the logic formulation of conditi…