Intereting Posts

Singularities at infinity
How to proof the the derivative of $x^2$ is $2x$?
What is the practical difference between abstract index notation and “ordinary” index notation
What do we mean by an “Elegant Proof”?
Prove that $\phi(n) \geq \sqrt{n}/2$
The space of bounded continuous functions are not separable
Function Notation
What are the solutions to $z^4+1=0$?
Find all homomorphisms from a quotient polynomial ring $\mathbb{Z} /(15X^2+10X-2)$ to $\mathbb{Z}_7$
Why is Euler's Totient function always even?
Simplify $\int_{0}^{1}\ln(x-a)\ln x\,\mathrm{d}x$, for $a<0$
Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$
Group of order $3^a\cdot5\cdot11$ has a normal Sylow 3-group
An Inequality problem relating $\prod\limits^n(1+a_i^2)$ and $\sum\limits^n a_i$
Sum of polynomial

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it.

Suppose that we can prove all questions that can be verified in polynomial time have polynomial time solutions, it won’t help us in finding the actual solutions. Conversely, if we can prove that $$ P \ne NP,$$ then this doesn’t mean that our current NP-hard problems have no polynomial time solutions.

From practical point of view ( practical as in the sense that we can immediately use the solution to real world scenario), it shouldn’t bother me whether P vs NP is proved or disproved any more than whether my ** current problem** has a polynomial time solution.

- Ackermann Function primitive recursive
- Density of halting Turing machines
- Lower bound for finding second largest element
- Constructing a NFA for the following language
- Reed Solomon Polynomial Generator
- How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Am I right?

- Are sets and symbols the building blocks of mathematics?
- How to maximize the number of operations in process
- Recognizing and Using Chaitin's Constant
- What is the algorithm hiding beneath the complexity in this paper?
- Is $L_1$ context free language?
- Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?
- Try not to get the last piece, but with a twist!
- Matrix Chain Multiplication?
- Reed Solomon Polynomial Generator
- Is there a polynomial-time algorithm to find a prime larger than $n$?

Many of the problems we know to be in NP or NP-complete are problems that we actually want to solve, problems that arise, say, in circuit design or in other industrial design applications. Furthermore, since the diverse NP-complete problems are all polynomial time related to one another, if we should ever learn a feasible means of solving any of them, we would have feasible means for all of them. The result of this would be extraordinary, something like a second industrial revolution. It would be as though we suddenly had a huge permanent increase in computational power, allowing us to solve an enormous array of practical problems heretofore out of our computational reach. The P vs. NP question is important in part because of this tantalizing possibility.

If it were proved that P = NP and the proof provided a specific polynomial time algorithm for an NP-complete problem, then because of the existing reduction proofs, we could immediately produce polynomial time algorithms for all our other favorite NP problems. Of course, a proof may be indirect, and not provide a specific polynomial time algorithm, but you can be sure that if we have a proof of P=NP, then enormous resources will be put into extracting from the proof a speciffic algorithm.

Conversely, if someone were to prove $P \neq NP$, then it would mean that there could be no polynomial time solution for any NP complete problem. (In particular, the last sentence of your second paragraph is not correct.)

If $P = NP$, computational revolution (once a specific algorithm is identified for an NP-hard problem, with explicit asymptotic runtime bounds).

If $P < NP$ *and one can prove it*, secure (classical) cryptography provably exists, and a huge missing piece in our understanding of computation is filled in. The first already has significant implications for daily life, and developing the second would have much larger implications.

You should also understand that after 40 years of research, today P=NP carries a host of related ideas like: easy-to-hard phase transition in combinatorial problems; quantifiable boundaries between easy and hard approximate versions of specific NP-complete problems (so getting within 7/8 of the optimal solution is easy but anything closer is NP-complete); counting and randomly sampling combinatorial objects are the same problem; zero-knowledge proofs “that reveal nothing but their own validity” (unforgeable ID cards). It’s a very rich universe of ideas and it doesn’t run out of questions once you know the answer to P=NP.

Actually $P \ne NP$ *does* mean that our current NP-hard problems have no polynomials time solutions. NP-complete problems are the hardest problems in NP and NP-hard problems are at least as hard as this. So if $P \ne NP$, then all these NP-hard problems must be harder than P.

Whether the proof helps us find solutions will of course depend on the proof. If $P \ne NP$, then we know not to waste time looking for polynomial solutions.

If $P=NP$, then the real practical benefits would of course come from the solution, rather than the proof. That is fine – there is no reason why all theoretical computer science needs to be *directly* practical.

Not directly related to the question, but definitely relevant.

Three days ago proof for P != NP is published. Community thinks it looks serious.

Currently, if a manager asks their software engineering team to look at implementing some utility, and the team says that requirements are NP hard, that’s a reason that the project requirements need to be changed before work on implementation can begin. That’s because no-one knows how to give feasible solutions to such problems.

The plurality of complexity theorists furthermore believe P =/= NP, so that means that there’s a widespread belief among experts that feasible solutions to these problems will never be found.

If someone shows P=NP, then if the team says the requirements are NP-complete, then the manager and the team will start to move from talk of theory to possible realisations and their efficiency.

There is an interesting heuristic to suggest that P is actually not NP. It is that, roughly, the task of finding out a proof of a statement is an NP task, but that of verifying it is a P task. From our actual experience that verifying a proof is far easier than finding one, we can intuitively expect P != NP to hold true.

The practical application is that a result which would agree with our intuition would be a great thing, and psychologically satisfying moreover.

- Old AMM problem
- How to evaluate $\int_{0}^1 {\cos(tx)\over \sqrt{1+x^2}}dx$?
- Submodularity of the product of two non-negative, monotone increasing submodular functions
- A disease spreading through a triangular population
- New, extremely simple golden ratio construction with two identical circles and line. Is there any prior art?
- There is no “operad of fields”
- What are the left and right ideals of matrix ring? How about the two sided ideals?
- Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−2}$
- Given $f\notin L^p$ find $g\in L^q$ s.t. $fg\notin L^1$
- What do people mean by “finite”?
- Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines.
- Suppose $A$ is nilpotent, and $B = c_0I_n + c_1A + \cdots + c_{m-1}A^{m-1}$, show $\det(B) = 0$ iff $c_0 = 0$
- Prove that the Pontryagin dual of $\mathbb{R}$ is $\mathbb{R}$.
- Is it true that $\mathbb{C}(x) \equiv \mathbb{C}(x, y)$?
- third-order nonlinear differential equation