P = NP? Introduction

zhaozj2021-02-16 66

Future mathematician challenge computation problem

Yang Zhaun; Yang Zhongjun

First, foreword two, calculate three, P, Fourth, Gark Law and NP-Completeness 5. NP-Complete Problem Bear Sixth, NP-Hardness and Go

Seven, conclusions

I. Introduction

There are mathematicians that "a good question is better than ten good answers." Because of the answer, this problem is already the end, and it does not constitute a challenge for people who constantly innovate. The new problem is the source of live water and can open new realm. Most people don't want to be intoxicated in a good solution, and hope to find new problems, constantly think, explore. Everyone has seen a lot of good problems in "Digital", especially Professor Kangmingchang talked about the Taxi, geometric three puzzles, are very interesting issues. Some have an answered answer, and some are still resolved. In addition to the topic above, like a four-color problem (ie, as long as one of the maps can separate the national boundary), five times the above-mentioned formula solution, and the number of rigidity distribution in the number, all in the occupation and amateur mathematicians The mind has a considerable status. What is going to introduce this article is a big problem for many mathematicians and electronic computerists in the 1970s. The meaning representative of NP, you will naturally understand after reading this article, now you may wish to remember "NP-HARD" this great word. In the future, if you say that your question is "NP-HARD", he may think about you, NP-Hard not only represents Hard (difficult), but it is NP! One of the representative issues of NP issues is the Traveling Salesman Problem. There is a salesman to drive to N designated cities to sell goods, and he must pass all N city. Now he has a map between this N-city and the road between the city. How should he take the shortest trip from home to home?

Figure 1 Map of Salesperson, A, B, C, ... Famous City name, digital table between two cities. As shown in Figure 1, A, B, C, ..., G represent seven cities, and the salesperson should return to A city from A City and visit B, C, ..., G, all the city, a viable method is

The problem is: Is this the shortest way? Maybe

What is it closer? The result of the result of the first path is 235, and the second path is 230, so the second path is short, but does there be a shorter path? The current approach is close to a one-piece trial, and has not found a way to find the shortest path. For seven cities, there are 6! = 720 rows, it is not difficult, but if there is 20 towns, there is 19! because

In the arrangement combination, it is easy to write, but 1.21 x 1017 is a big number, if the row is once every second, you have to row 3.84 x 109 (about 3.15 x 107 seconds a year), even if you use a computer One million times per second (not easy to do) also have to pay for 3,000 years to find the answer. "There is also a good life, knowing the endless", I can't think of 20 centuries in the district, I have to find the answer in my thirty century. Due to the development of the electronic computer, there are many calculations that are previously considered to be spending, the value of the line, the anti-matrix, and the high-order square solution can be solved in a very short period of time. But there have been some new problems, and even large computers are also surprised. As a salesperson problem, because it is better to find a lot than the hard row, the mathematician begins to prove that there is a lot of practices that are better than the hard row. This proof has not been found so far. Just like the previous three-class score, since I found a method of couldn't find a rounded one-level one-level, maybe we can prove that it is absolutely impossible to use a square horizontal. Now we have to prove that it is impossible to write a computer program greatly simplified salesman. Unlike the three-class part of the problem, the former is a mathematically curious, and today's problems are closely related to the actual use. Here we have always emphasized a lot of ways. The reason is the problem of such problems, if you can calculate a fast or ten times, thousands, often can't get a big role, it seems that the twenty city travel problem just happens, even if it is fast, it still takes three years to calculate Time, and then plus three cities immediately offset the effect of this calculation method, so we have to make a reduction in the basic level of calculation, which is what we have to discuss in the next section. Search keywords:. NP problem. Salesman travel problem

Future mathematician challenge computational quantity problem (page 2)

Yang Zhaun; Yang Zhongjun

Home | Search

. Originally published in the Ten Volume II of Mathematics Communication. The author teaches the statistical system of Flori University in the United States; US Navy Research Experiments ‧ Note ‧ External search keyword

Second, the amount of calculation

The amount of calculation, as the name, refers to the time to solve the calculation of a problem, but because the calculations for each complex problem often have to pass many different computments, except for the addition and decrease, and the comparison, data, save data Wait, if you carefully calculate, it is very difficult. Generally, only one or two main quantities are placed, and the statistics are statistically, and the sales issuer of the above-mentioned salesman is the case. The main job is to add a total path to each. Long, because of the N-city, there is (N-1)! The rule of the rule is O (N!), That is, within the N!, The source of ORDER 即). For two examples, if we require N number and or average, its calculation amount is O (n). However, if we want to arrange n numbers in turn, its computation amount will be quite different due to the differences, and a direct approach is to find the largest (ratio (n-1), then Never the biggest intermediate (ratio (N-2) times), then ask the third largest (ratio (N-3)), ... so a total ratio

You can do this. Therefore, we will form the calculation amount of this method with o (N2), ie at the N2 level. Another fast-sliding method, first divide N number into several small pieces, then together, it can prove that this method is 1, due to the number of ranks, the phone number, this The drain is very practical, such as one million in a big city, n2 = 1012, and only 2 x 107, the difference is three months and one minute. Generally, the amount of calculated amount is more than the following table, in the above table, k is a positive integer greater than 2, and there is a gap between them, there is a basic layer, in theoretical, if someone can find one New ways, reduce a level of computation, then his new method is eligible to be a breakthrough, you can immortal. Table 1 There is a comparison of each item in the previous item, which is based on a computer per second (106) as a principle.

NNN2N32N3NN! 1010-610-510-510-410-310-30.0590.452010-30-510.452010-610-510-510-410-21 (second) 58 (divided) 1 year 5010-510-410-40.00250.1 2536 2 x 1010 1057 1000-510-310-3116 Hours 10333 pole Terminal 10610 - 5161, 105, extremely big big top 10910-516 hours 6 days 3 years 3 x 109 pole great big big table 1: Taking a computer to do one million times per second When completing the time required to calculate each level (if uniform, all in seconds)

In this table, specifically pay special attention to the difference in N3 and 2N, generally referred to as the calculation amount rises, while N3 or NK calculates a party rising 2, for the current and future computers, one is present The amount of calculation of both the rising should be copened, but the amount of computation that is rising index is quite large when n is quite large. Therefore, the direction of computer scholars focus on how to increase a computational amount of an index, simplifies a calculated amount of calculation. We define that the most important parameter n in a question can be completed in the amount of calculation that can be found in moderation. We call this problem (p is the first letter of English in English). The set containing all such problems is represented by P.

Future mathematician challenge computation problem (page 3)

Yang Zhaun; Yang Zhongjun

Home | Search

What is the three, P?

This section is a bit unusual, our purpose is to remind the reader's English-writer in English, the general written in English is a collection of problems that can be solved with O (NK). In addition to P, a question mark system refers to so far, we don't know if P is an empty collection. So far, in addition to the salesman travel issues, there have been hundreds of interesting or useful issues, which cannot be solved with O (NK), and we list several examples here.

Question 1: Sales officer travel problem (A)

That is, the problem described in the first section is no longer repetitive, but it is assumed that all distances are positive and integers.

Question 2: Salespeople Travel Problem (B)

The same as the first question, but now there is a given positive integer

B, the problem is whether there is a path that has a total distance of no more than

B. (Problem 1 is similar to question 2, but there is a big difference in the next theory)

Question 3: Back bag problem (A)

Object

N, heavy

W1, W2, ...,

Wn, this is to divide them into two bags, and ask how to make two bags close to the weight. (May wish to assume

Wi is a positive integer, which has not lost a generality. )

Question 4: Back bag problem (B)

As the topic, and give a positive integer

B, ask if you can choose a number

Wi, make it and

Question 5: Packaging problem

Have

N of the items that are less than 1 kg and enough to install 1 kg of things, this item is installed in the box, and multiple items can be installed in a box, but no box is not more than 1 kg, try Minimum number of boxes.

Question 6: Dance partnership

Now

N boys and

N girls participated in the ball, and each boy and girl were handed over to a list of hosted a list, and he wrote a dance partner in him (she) (at least one person, but more than one person). I can be divided into being divided by the host after receiving the list.

N pairs, allowing each person to get the dance partners you like.

Question 7: Inventory problem

A warehouse has

D storage, arranged, today

n Batch goods, each can have one or more deposits, and have known the deposits of each batch of items and the date of proposed. If you do not have difficulties in depositing in the library, the storage warehouse must be adjacent to the same batch of goods.

Question 8:

A known

n triangular integer, ask if there is a smaller than

N-bit positive integers

Question 9:

(A) given one

N-bit integer

a, ask if it is a lot?

(B) given one

N-bit integer

a, ask if it exists

m, n> 1

A = mn?

Question 10: Tissue

Known space

N points, and assume that the distance between the points is positive and the integer is given.

K and

B, ask if you can

N points are divided into less than

K non-coincidentic subset makes any two points in the same subset of no more than

It can now be seen that the general structure of this type of question is now. Obviously, some are very useful issues, and some can be converted into useful issues. For example, the dance partner, if the boy is replaced with the girl with workers and fores, or the doctor has a lot to use. These issues have not currently proven to be P, everyone guess they may be outside P, that is, their calculation is increased. In the 1960s, some people have returned some problems into a class, ie a few problems are alive. If one of them belongs to P, other several also belong to P, which is mostly proved to prove two mutual There is a bridge that only needs to be done with an O (NK) time in the middle of the problem. Until 1971 An. Cook published The external approval of the P is homed into three major categories, namely NP, NP-Complete and NP-HARD 4, now talk now law.

1│2│3│4│5│6│7

Future mathematician challenge computation problem (page 4)

Yang Zhaun; Yang Zhongjun

Home | Search

Fourth, Gark Law and NP-Completeness

The proof of the law of Gark is difficult, that is, it is not easy to understand it. We will see this problem from a few angles, try to understand it. Its main result is that most of the problems of the previous festival are at a relatively proven collection, called NP, and find a batch of interpretation in NP, called NP-Complete class and get the following results. 1. If there is an NP-COMPLETE problem, you can use

O (NK) calculation amount is solved, then all NP issues can be used

O (nk) calculation is solved, ie

1 '

NP-COMPLETE

,then

P = NP.

In other words, NP-COMPLETE is a problem in NP, and NP-Complete has solved 5, and NP is solved. However, if there is a problem that belongs to NP and does not belong to NP-Complete, other NP issues are not necessarily resolved. What is NP? NP is an abbreviation of English Nonderministic PolyNomial, meaningless of a non-deterministic polynomial time. To understand this word. Let's take a look at the role of normal computers. Now use a computer, to solve the salesman's travel problem is very difficult, but if we have many computers, can I solve the original problem in o (nk) time? "Many", not one, two, more than one or two are not supplemented, more than one thousand people are still a drop in the bucket, because there is a thousand machines to do separate, and can only It's almost a thousand times, I have said in the first quarter, help it. Therefore, computer scholars will look around, and simply allow you to add machines. Now that we have to pay attention is that all issues with unlimited machines can be solved immediately. If there is any problem, there is a preface, such as when it is calculated

[(A1 A2) A3 A4] A5 A6

Unless otherwise on the form, it is necessary to step by step, the machine does not speed up the speed of calculation, and the machine is more, the contact between the rooms, one machine should pay a thousand tens of millions of machines. The signal is also exhausted. Therefore, we only assume that all machines are only in the open, single-wire jobs, do not do any horizontal contact 6, that is, machine 1 can pass its results to it below, like A1, A2, ..., AN A machine can also pass their results to their own, but do not contact each other between A1, A2, ..., AN. Take the salesman's travel problem as an example. If there is 20 cities, the first machine starts, the next 19 machines take a different city and calculation and a distance, and this 19 machines will find it The distance is handed over to the 18 sub-machines to take a distance from the city, such as the distance, so, in the tenth time, the tenth stage, the machine has taken it 9 cities and total distance tells the next Machine, told them to take one with different cities that have taken the city, so that they have been done 19th, all the distances of all routes have, in time, all the distances are O (n) (n) But with 19! Computer), the august definition can solve the problem with unlimited multi-computer in O (NK) time as an NP issue. Now I have to remember because there is no translative contact, after all paths have, I don't solve the salesman problem (A), because I don't know who is the shortest (if you want the shortest distance, you will want o (n! Comparison), so we can't say that the salesperson travel problem (A) is an NP issue. But the last question 2, the salesperson travel problem B, any single line can know if its total distance is not more than B, so there is a "YES" or "No" answer per single line. As long as there is a "YES" answer, we know that this issue has been resolved, so the problem is a NP issue. In single-wire work, each machine can make three things. The current answer is not clear, everyone's work. A certain line has found the answer, immediately stopped, everyone stopped the job, and the question was completed. This road is not available, the network is no longer homework, but it is not called, and the line is still working. From the active role, it is easy to see that the calculation time to find the answer is time to stop, and that is, the sum of the quantities in the "Yes" answer line, that is to find the answer "shortcut" time. It is easy to say that under a non-deterministic computer system, its subsector appears to "guess" to shortcut function. If in any calculation step, someone guess an answer, and the computer can answer "Yes" or "No" within the o (nk) time, this question is an NP issue. Take the salesperson travel (A) and Figure 1 as an example, if you guess a path

We can't know if this road is shorter, but in the (b) question, a result of "Yes" or "No" will answer if 7 plus method can answer. So according to the new definition, problem 2 is an NP issue. From these two definitions, readers are not difficult to see problems 2, 4, 6, 7, 8, 9 (B) and 10 are NP issues, especially the problem 9 (A), (B), is actually the same problem But if you guess two M, N, immediately know whether A is MN. The key to the gurke-proof is demonstrating that if a SatisFactability Problem is a P, all NP issues belong to P (that is, this problem belongs to NP-COMPLETE), order, , - (,, or, but) Table three basic logical operations (ie, for 0 and 1 logic symbol, except for 1 1 = 1, , with the general algebra.). Let F is a function containing N logical variables (U1, U2, ..., UN). If we can find a set of U1, U2, ..., UN, make f (u1, u2, ..., un) = 1, then F (U1, U2, ..., UN) is called satisfaction. For example, to meet the function, take U1 = U2 = U3 = 1, but

Yometry 0, so this is not satisfied. Initially, this problem has no shortcut to check 2n in one by 0, 1 generation, and the auspine in 1971 is proved to be all NP issues.

Gark Theorem:

The problem is NP-COMPLETE.

It is now possible to prove that problems in the previous festival, except for problems 1, 3, 5, and 9, all NP-Complete issues.

Future mathematician challenge computation problem (page 5)

Yang Zhaun; Yang Zhongjun

Home | Search

V. NP-Complete Problem

NP-Complete Problems Can't find a feasible solution, and large parts of NP-Complete issues are used in computer language, programs, circuit design, statistics, and program operations, so I have to pay a follow-up to find a feasible Approximate solution. It is a pity that all NP-Complete issues are connected at the hierarchy of NP. In approximate solutions, different solutions are often different, and these solutions have been in an intuitive, we will mention two examples.

example 1

In the third question 5, in the packaging problem, if the "can assemble the installation" method, if the existing box can be installed, the number of boxes required for this method is required.

K1 and the most likely number of boxes

K0 satisfied

prove

This order

N items

W1, W2, ...,

Wn kg, because each box can only be loaded 1 kg, so

On the other hand, "can install it" method is not possible to have more than two boxes at the same time less.

Kg, so

This example is certified.

The result of this question is to say that we can use the "Canada to install" method to do half. After more complicated proof, Johnson was certified in 1974, when N is large,

(i)

And there is a situation that can be produced.

(ii)

That is, it is not more than 70% of the "can assemble" method, but it can be used to use a 70% box. An intuitive way to visit the problem of the salesman is to visit the recent city that has not yet visited. It is called "the first visit to the city" law. Take Figure 1 as an example, and its method is Rosenkrantz, etc. In 1977, this is not a very The ideal way to walk, they have identified that the distance between the city meets the triangular inequality 7, the "First Visit the Near City" law is the relationship between D1 and the shortest path D0.

And when N is large, there is a situation so that

[X] in the above formula indicates a minimum integer greater than X, for example [5] = 5, [2.5] = 3. Because the N is very large, D1 can be different from D0, but in the same paper, Rosenkrantz, etc., proves that another complicated "intuitive" way can achieve. In the above theorem, the conditions of triangle inequality are important. If the distance of the city is not here, Sahni and Gonzalez have been certified in 1976: if NP, there is no possibility of limited M, and one O (NK) The calculated amount of way of walking can make its full-deputy D1 to satisfy when any N

That is, M is not equivalent to unlimited in the upper form, that is, all O (NK) is not very good.

Future mathematician challenge computation problem (page 6)

Yang Zhaun; Yang Zhongjun

Home | Search

Sixth, NP-Hardness and Go

Not all the problems can be summed up to NP issues, like the absolute play of a one-hand play now is currently more difficult to calculate than all NP issues, namely NP-HARD issues, NP-HARD issues are as follows:

Definition:

X is an NP-HARD problem, if np

,then

That is, even if p = np, x is not necessarily P, but NP, X is never easier than NP. The problems in the third quarter 1, 3 are not necessarily NP issues, but if they can solve them with O (NK), it is relatively easy to problem 2 and 4 can also solve o (nk), so if the problem 1 , 3 questions 2, 4, and because 2, 4 is NP-Complete, the NP = P is introduced. This is associated with the definition of NP-HARD, so problems 1,3 are NP-HARD issues. Similar problems 5 also belong to NP-HARD, but these NP-HARD seem to be much less than NP, but the problem may be much more rare than NP, Go problem can be made.

Question 11. (Go problem)

Rules in the usual Go, in one

N x N's chessboard, given a resilience (two children can be considered), first, if you can determine that the black child is under the best under the method, will you win?

This problem cannot be used to prove that it is NP with a general method. Because there is currently no one can guess the winning method and in o (np), it proves that it is right, because it is related to the other party, and the enemy's cis is related to the premise of you later. So going down, the first thing that happens is that the memory is bright, that is, the memory required may have the progress of the above. Because each memory is at least (calculated) once, this memory is not as good as, so the memory of a problem is rising index, the amount of calculation is not index, but if a problem is only required The remembering of the second, that is, it does not guarantee that it only needs to increase the amount of calculation. Therefore, computer scholars define three new collections: pspace = {

x only needs to rise to the memory}

Note:

X is a problem.

PSPACE-COMPLETE:

PSPACE,

also

PSPACE-COMPLETE,

And

then

P = pspace.

PSPACE-HARD:

PSPACE-HARD,

And

then

P = pspace.

Note that PSPACE-Complete Pspace in the above formula, PSPACE-COMPLETE is a problem in PSPACE, but PSPACE-HARD does not necessarily belong to PSPACE. Stockmeyer and Meyer proved a similar theorem with anacker in 1937. If the order indicates that there is one X, the table has one of the X, Q tables, and X is the Both Rank variable 0 and 1, then we call F (Q1 X1, Q2 X2, ..., Qn XN) is a quantification of Brown. formula. If f is possible to be 1, then f is called satisfaction, such as rewriting (1) in the fourth section into

The above formula is impossible to satisfy, because the pair (U3 is 0 or 1), F is not all 1. Theorem of Stockmeyer and Meyer is:

theorem:

A quantifier formula is a PSPACE-Complete problem that can be satisfied.

When we play chess, our request is

Whether there is a win chess for me to deal with

Any enemy to pay chess

Since then, if there is a win chess, you can deal with

Any enemy to pay chess

......

Do I have a win chess to deal with

Any chess

I won

So this is complete ,,, ... The relationship between the Stockmeyer and the Meyer theorem is close, Robertson and Munro have a PSPACE-HARD problem in 1918, and there is currently to calculate the memory of Go 8 The amount of calculation is more than 10,600, regardless of one atom, regardless of the human brain or computer, and the number of universe atoms knows only 1075. The way of chess, big! To be a robot to be a win-win-winning robot?

Future mathematician challenge computation problem (page 7)

Yang Zhaun; Yang Zhongjun

Home | Search

Seven, conclusions

Now you understand the big problem of the twentieth century, p = np? In a simple language, is it possible to find a way to solve travel, packaging, dance, and other issues. Ordinary questions, I look forward to your extraordinary answer.

1. Gorey, M.R. And Johnson, D.S. "Computers and intractability-a guide to theory of np-intr g", 1979, FreeMan and Company.

2. Pearl, J. "Hearistics-Intelligent Search Strategies for Computer Problem Solving", 1984, Addsion-Wesley.3. Cook, SA , Proc. 3rd Ann. ACM Symp. On Theory of Computing, 1971, 151-158.

4. Jonhson, D.s. et. Al. , Siam J. Comp., 1974, 299-325.

5. Rosenkrantz, D.j. et. TL. , Siam J. Comp., 1977, 563-581.

6. Sahin, s. And Gonzalez, , J. ACM, 1976, 555-565.

7. Stockmeyer, L.J. And Meyer, P.r. , Proc. 5th. Ann. ACM Symp. On Theory of Computing, 1973, 1-9.

8. Robertson, E. And Munro, I. Utilifas Math., 1978, 99-116.

转载请注明原文地址:https://www.9cbs.com/read-22309.html

9cbs

New Post(0)