NP=P? Algorithms for solving NP-problems by matrix method in Scilab program

Оглавление

Ludmila Naumova. NP=P? Algorithms for solving NP-problems by matrix method in Scilab program

Introduction

Chapter 1. The essence of the method; commands and typical algorithms in the program Scilab 6.0.1

– The essence of the method

– NP-problems and their models in small numbers, General algorithms

– Specify the source data

– Permutations

– Permutations followed by matrix replacement and finding solutions

– Placements

– Fulfillment of additional conditions in the task

– Complex placements

– Solving the problems of combinations and arrangements with the help of zeros in the rows of the original matrix

– Combinations

Chapter 2. Detailed solution of problems in the program Scilab 6.0.1

2.1. Model-problem №1

2.2. Task-model №1—1

2.3. Task-model №2

CONCLUSION

Отрывок из книги

From the course of school mathematics, we all know the problems of combinatorics, such as the problem of permutations, combinations, placement, represented by the corresponding formulas. But these formulas only give us the number of solutions, not the solutions themselves. There were no common standard algorithms for solving these types of problems. These types of problems with large numbers can be referred to NP problems. But with the help of Scilab program typical algorithms of such problems are revealed and solutions are given, and not only the number of solutions. The essence of the algorithms consists in operating with elements of natural series in rows and columns of the matrix, as well as in operating with rows and columns of the matrix using Scilab’s commands. NP-problems, in principle, represent all the same combinatorics problems, but in large numbers. So in one NP-problem can be present immediately as permutations and combinations and placement, can be these operations (combinations, placement, permutations) sequentially repeated, but with other, obtained in the course of solving the problem, data, can be set additional or any other conditions or calculations. The bottom line is that knowing the typical algorithms of permutations, placement, combinations, these algorithms can be used as much as necessary in a single problem and thus solve NP problems. Let us emphasize once again that the algorithms below give the solutions themselves, not just answers about the number of solutions, although they also give. In large numbers, the solution of these problems requires a large resolution power of the computer, but the algorithms remain the same. This book provides examples with small numbers, but the point remains the same. Thus, the author wants to show that often the solution of the problem lies on the surface, but sometimes we can not see the solution at this angle. The author is confident that more and more NP-problems will move into the category of P – problems. This process is inevitable with the development of programs and the growth of computer power.

Common algorithms for combinatorics problems, such as permutation, combination, placement problems, which are given below, are applicable for NP – problems. These types of problems (on permutations, combinations, placements) with large numbers can be attributed to NP – problems. NP-problems, in essence, represent all the same problems of combinatorics, but in a complicated version, in one problem can be present immediately as permutations and combinations and placement, these operations (combinations, placement, permutations) can be repeated sequentially, but with other data obtained in the course of solving the problem, additional conditions or calculations can be set. But with the help of Scilab program typical algorithms of such problems are revealed and solutions are given, not only the number of solutions. The bottom line is that knowing the typical algorithms of permutations, placement, combinations, they can be used as many as standard algorithms in one problem and thus solve NP – problems.

.....

– > ac= [1 3];

– > ad= [1 4];

.....