The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.
It was introduced in 1971 by Stephen Cook in his paper "The complexity of theorem proving procedures and is considered by many to be the most important problem in the field.
In essence, the question P = NP? asks
Suppose that solutions to a problem can be verified quickly. Then, can the solutions themselves also be computed quickly?
: The theoretical notion of quick used here is an algorithm that runs in polynomial time.
P- "The general class of questions for which some algorithm can provide an answer in polynomial time."
NP-"Class of questions for which an answer can be verified in polynomial time. For these questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it may be possible to verify the answer quickly."
NP-complete problems are the "toughest" problems in NP in the sense that they are the ones most likely not to be in P.NP-complete problems are a set of problems that any other NP-problem can be reduced to in polynomial time, but retain the ability to have their solution verified in polynomial time.
In comparison, NP-hard problems are those at least as hard as NP-complete problems, meaning all NP-problems can be reduced to them, but not all NP-hard problems are in NP, meaning not all of them have solutions verifiable in polynomial time.The decision version of traveling salesman problem is one of many such NP-complete problems, so any instance of any problem in NP can be transformed mechanically into an instance of the traveling salesman problem, in polynomial time.
Based on the definition alone it's not obvious that NP-complete problems exist. A trivial and contrived NP-complete problem can be formulated as, "given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept? It is in NP because (given an input) it is simple to check whether or not M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.
It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete.Such problems are called NP-intermediate problems.They are some of the very few problems believed to be NP-intermediate. For example,The integer factorization problem, it is the computational problem of determining the prime factorization of a given integer. In the form of a decision problem it is the problem of deciding whether the input has a factor less than k.
No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes expected time O(e(64/9)1/3(n.log 2)1/3(log (n.log 2))2/3) to factor an n-bit integer. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.
General notion about P versus NP Problem in Scientific Community:
According to Poll Many computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems. Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.
Some researchers believe that there is overconfidence in believing P ≠ NP and that researchers should explore proofs of P = NP as well.
The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. [. . .] The resolution of Fermat's Last Theorem also shows that very simple questions may be settled only by very deep theories.
—Moshe Y. Vardi, Rice University
Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.
—Anil Nerode, Cornell University
It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience.
If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...
— Scott Aaronson, MIT
One of the reasons the problem attracts so much attention is the consequences of the answer. A proof that P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP. It is also possible that a proof would not lead directly to efficient methods.
Results About Difficulty to Proof :
Although the P = NP? problem itself remains open, despite a million-dollar prize and a huge amount of dedicated research, efforts to solve the problem have led to several new techniques. In particular, some of the most fruitful research related to the P = NP? problem has been in showing that existing proof techniques are not powerful enough to answer the question, thus suggesting that novel technical approaches are required.
All these led some computer scientists to suggest that the P versus NP problem may be independent of standard axiom systems, cannot be proved or disproved within them like ZFC. The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it's impossible to prove in ZFC that such algorithms are correct. However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the Peano axioms (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP. Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.Logical Characterizations:
The P = NP problem can be restated in terms of expressible certain classes of logical statements, as a result of work in descriptive complexity. All languages (of finite structures with a fixed signature including a linear order relation) in P can be expressed in first-order logic with the addition of a suitable least fixed point operator (effectively, this, in combination with the order, allows the definition of recursive functions); indeed, (as long as the signature contains at least one predicate or function in addition to the distinguished order relation [so that the amount of space taken to store such finite structures is actually polynomial in the number of elements in the structure]), this precisely characterizes P. Similarly, NP is the set of languages expressible in existential second-order logic—that is, second-order logic restricted to exclude universal quantification over relations, functions, and subsets. The languages in the polynomial hierarchy, PH, correspond to all of second-order logic. Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?". The word "existential" can even be dropped from the previous characterization, since P = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).
Now Its time to answer all the questions marked as Red with the help of a new concept:
At first we should consider the major part, the relation between P and NP, before that there is a one thing to be noted, in the case of NP problems, as Complexity increases Relativity also increases. It can be visualized easily with the help of Rubik Cube's moves. Consider a 2*2*2 Rubik Cube, if we move one block(let consider it as an oracle, just for remembering), the other oracle adjacent to also moved with respect to the movement of the original one. This number will be two in the case of 3*3*3 Rubik cube, three in case of 4*4*4 Rubik Cube and so on.....
So here we can see that relativity is also increasing as Computation complexity is increasing.
And this is the common characteristic of all the problems of NP.
It can be easily seen here that the relativity is increasing in the same ratio in which Computational Complexity does.
If we make the puzzle more complex with increasing one oracle each side the relativity is increased automatically in the same amount.
So,now we can say that, "Relativity is directly proportional to Computational Complexity here". This thing will be explained in detail further.
If somehow one can control the relativity the Computational Complexity will also be controlled.
So P = NP(If relativity controlled)
and P != NP(If there relativity is not controlled)
For having a brief idea of the concept of relativity in Computational Complexity lets try to find out the answer of the following question-
Is there an upper bound for Rubik cube?
(Maximum number of steps in which a particular Rubik cube of N*N*N dimension can be solved.)
1) An oracle of the Rubik cube can be moved only in three ways that is along x-axis, y-axis and z-axis.
2) In each way above stated only two directions are possible; a) clockwise and b) anticlockwise, as after one complete rotation we get the original arrangement, so clockwise and anticlockwise do not make much sense.
3) Each oracle can move independently along a particular axis with respect to a particular arrangement which gets changed after the movement.
4) Total number of movements for each arrangement is the sum of oracles along the three axes that is 3*(N).
5) But there should be a particular oracle with respect to which we can see the movements of other oracles as along one axis of 3*3*3 dimension Rubik cube if two oracles moved the third one is automatically moved as it is relative and vice versa.
6) So along each axis we can restrict the movement of a particular oracle so that with respect to which we can see the movements of others.
7) Now let for a particular arrangement of Rubik cube lets restrict the movement of an oracles of each axis with a common point so that we can move the oracles in a most free manner. This point may be anywhere at the Rubik cube, at the centre, at the edge or at the corner. Let take it at one of the corner or rather chose a corner as a frame of reference which is not going to change irrespective of any movement along any axis.This is our fixed point.
8) For N*N*N the total number of movements now are 3(N-1) with a particular corner never moved in any case.
9) That particular corner is also relative as in this three dimensional arrangement every corner is moving with respect to remaining corners and same for the other points as well in each step. But choosing a particular corner will reduce the number of steps. It should be noted that instead of corner we can chose any point on the Rubik cube for example a middle point or an edge point, all these make the same sense.
10) After each movement the cube is changed with respect to the particular corner we have chosen avoiding 4n movements for each oracle where n stands for the set of the natural numbers.
11) But the corner we have chosen will always remain the same as its configuration will never going to change as it is fixed one.
12)Now let’s see from the fixed point: In 3(N-1) steps in which we are taking movement of each oracle which do not contains the fixed corner, we can get all the possible arrangements of the Rubik cube with respect to that corner (it should be noted that it may be an edge block or a block anywhere in between) as in these number of moves we can displace each box on the Rubik cube at least ones with respect to that.
13)If from a particular symmetric arrangement we can get all the possible arrangement then it reverse should also be true, from any arrangement of N*N*N dimensional Rubik cube we can get a symmetrical arrangement in at most 3(N-1) steps (with respect to that fixed point).
It should be noted that in exact there are not 3(n-1) moves. All the moves are relative and we cannot predict how many exact moves we have done in those 3(n-1) steps. For example if we move an oracle of 3*3*3 Rubik cube the other two moves automatically but in what extent they move will depend upon their further movements and movements we have done before and so on....So the relativity also depends upon the movements before and after that particular movement.
Now lets consider Travelling salesman problem. As we increase number of cities the number of relative movements as well as relativity per movement increase as like complexity (same as above case where number of steps increase as well as relativity in those steps increase).
All the problems which posses the above property of relativity are the most likely not in P, So they must be NP-complete.
Now lets come to the concept of NP-intermediate Problems.
It was shown by Ladner that if P ≠ NP (Figure 01)then there exist problems in NP that are neither in P nor NP-complete.Such problems are called NP-intermediate problems. For example the integer factorization problem.
The integer factorization problem is the computational problem of determining the prime factorization of a given integer. If we see it clearly we will find it posses the same property of relativity with fixed known number of total possible steps which is obvious.It is fixed for every NP-complete problem. The thing is this number is hard to find due to relativity but it doesn't makes any sense whether this is known or unknown as while controlling the relativity we do not consider the total possible number of steps and once we get the solution it is of no use at all as now the problem is in P with the smallest possible number of steps.
So this is a NP-Complete problem. It means NP contains only two types of problems P and NP-Complete. The problems which are in NP and not in P must be NP-Complete.
"And Relativity is the only thing with the help of which we can identify between these two classes."
As the problem is NP-complete, the polynomial time hierarchy collapse to its first level (i.e., NP will equal co-NP).
Now lets consider the P= PH relation.
All languages (of finite structures with a fixed signature including a linear order relation) in P can be expressed in first-order logic with the addition of a suitable least fixed point operator (effectively, this, in combination with the order, allows the definition of recursive functions); indeed, (as long as the signature contains at least one predicate or function in addition to the distinguished order relation [so that the amount of space taken to store such finite structures is actually polynomial in the number of elements in the structure]), this precisely characterizes P.
Similarly, NP is the set of languages expressible in existential second-order logic.
Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?"
The languages in the polynomial hierarchy, PH, correspond to all of second-order logic.
As once relativity is controlled, there will be no discrimination between first order and second order logics because it is the relativity which differs this two classes by making the second order logics much more complex.
So again the same thing will happen:
P = PH(if relativity controlled)
P!= PH(if relativity not controlled)
As the former we have established that NP = co-NP, which in turn implies that NP = PH.
So, while considering the above result now lets consider the case of controlled relativity:
1) P = PH; which implies
2) P= NP
And in the case of uncontrolled relativity:
1) P!= HP; which implies
2) P!= NP
Now lets have an idea about what is controlled relativity in exact and how it can be done?
For the sake of simplicity lets again take the example of Rubik cube:
Now, how to find the particular 3(N-1) steps as described previously?
Take two Rubik cube the first one to which we want to arrange let R and the second one is that according to which we want to arrange the first one let R’.
1) Move all the oracles of the R (four times so that after movement each one acquire its original position) along their axes and note the number of boxes matches of each oracle of R to respective oracle of the R’ in each rotation of the movement of the particular oracle. So in exact there are 4*3*(N) steps.
2) Identify the maximum number of matches; this is our last step of those 3(N-1) steps or less than 3(N-1) steps.
3) Move that particular oracle according to that step and then again repeat the above method to find the preceding step due to which we get R from R’.
4) Again find out the step with maximum number of matches and make the movement according to that.
5) In this way find all the 3(N-1) steps for a given N*N*N dimensional Rubik cube.
6) Perform the movements accordingly and in this way we will get the R’ arrangement from R in 3(N-1) steps.
7) In these 3(N-1) steps one particular point will never move and this is our fixed point
So in this way we have controlled relativity of a Rubik Cube. We have indirectly performed many steps instead of these 3(N-1) steps. In fact the number of steps we have done here is the sum of all the possible steps.
It is same as solving a NP problem on a non-deterministic Turing machine in polynomial time. This is the benefit of the Relativity..........!
To explain the statement of Scott Aaronson about equality of P and NP classes lets go to the concept of ZERO(0), its definition and origin:
It is well known that it is discovered in India. But what is the basic idea behind it or exactly what is the definition of ZERO(0)?
There are many disputes about this. Such like why 0+0=0 or why 0-0=0, is 0 means nothing? But there are many points where this definition comes out to be wrong.
And if it is not nothing then why the above quality exist?
Then how to prov the these two most basic results in mathematics?
One thing is clear that whatever knowledge we are having today about this number(for example multiplying or dividing a number by 0) is only because of the above two results or by contradiction.....!
But from where these two most basic equations comes from and what is the exact definition of ZERO(0)?
For this we should go into the origin of this amazing concept. The first shloka of Isavasya Upanishad
"Om Purnamadah purnamidam
"That is completeness, this is completeness.From completeness, completeness comes forth.
Completeness from completeness taken away
Completeness to completeness added
Completeness alone remains.
Here in this definition the complete thing is known as 0(Bramha). It means 0(Bramha) is complete and the other o(Bramha)'s comes from it are also complete same as the ancestor. It means 0-0 =0 always no matters how many times we perform this operation. Same in the case of addition the complete is added to the complete and what we get is again the same thing, complete. It means 0+0 =0 always no matters how many times we perform the same operation.
Basically the meaning of Purna is not exactly fullness or complete, rather it is the nearest meaning on English Language for this word ,'Purnatva' goes far beyond these meanings.
'Fullness' can indicate a state of satiation and the word 'Completeness' can denote a state arrived through the 'Sum of the parts'. But 'Purnatva' is far from these two conditional states. 'Purnatva' is a state of profound realization, when the sense of limitation, as "Individuality" drops off, as a redundant vestige from one's consciousness. Any extent of acquisition OR renunciation cannot hasten the arrival of 'Purnatva'! When the microcosm totally dissolves into the state of Macrocosm, as a sugar doll dissolves into water, 'Purnatva' is THAT non-verbalized state. Following peace invocation 'Shloka' in the 'Isavasya Upanishad' most brilliantly conveys the total import of 'Purnatva'.
In this Shloka, the word 'That' indicates the totality of Macrocosm. The word 'this' indicates the infinitely teeming microcosm. Thus, if one substitutes accordingly, the whole stunning import of WHOLENESS is revealed! 'Poornatva' is such all devouring FULLNESS!