1

I was discussing P vs NP problem with somebody who works in computer science. I work in mathematics and know very little about computer science.

My opponent told me, if you solve P vs NP problem, keep the solution to yourself, so you can crack codes and stuff. I told him it does not matter because the theorem, if proven, is an existence statement and does not tell us how to implement the algorithms more efficiently. (Or even if it could, the constants can be so huge that it practically does not matter).

My feeling is that since in mathematical theorems are usually of existence-type, it means that if you can solve P vs NP, it would not mean you can suddenly go on cracking codes easily. Thus, our disagreement can be summarized as saying: I say the solution to P vs NP problem is a theoretical curiosity, while he thinks it has practical consequences to algorithms.

What are your thoughts?

daOnlyBG
  • 2,711
Durian
  • 11
  • 2
    Welcome to Math.SE. I don't really understand what your question is, although I think it is interesting, it is not a question. – Joao Oct 14 '14 at 06:41
  • 1
    It depends on your solution. – davidlowryduda Oct 14 '14 at 06:43
  • @mixedmath

    Is the official statement of the problem given by Clay Institute asking for existence only?

     – Durian Oct 14 '14 at 06:46
  • 1
    @Durian The Clay institutes simply asks for a resolution of whether or not P is NP. Any proof, constructive or not, will qualify. Of course, very few people believe P=NP, so most likely the answer is $P\ne NP$, in which case, I think, your (slightly vague) question dissolves. In the odd case where it will be shown, even constructively, that P=NP it may very well be the case that no efficient polynomial solutions exist to some (most?) NP (-hard) problems. In such an event, there will be little practical value to the resolution. In any case, the P=NP problem is one of theoretical value (probably – Ittay Weiss Oct 14 '14 at 07:04

1 Answers1

0

Well, I will try to answer the questions that I think you are asking. If the P=NP? question is solved positively, then the answer should be (quite possibly) in the form of an algorithm that solves an NP-hard problem in polynomial time. NP-hard problems are those problems that are at least as hard (computationally speaking) as any problem in the class NP, so that if you find an efficient (polynomial-time) algorithm to solve one of them, you are automatically finding an efficient algorithm for all problems in NP. Hence, in that case, the answer to the P=NP? question will have great practical value. However, as @Ittay Weiss points out, most people believe that P is a proper subset of NP. If that is the case, then you would not get any algorithm to crack codes, but on the other hand, you would get the one-million dollar prize offered by the Clay Institute :-). Moreover, a negative answer will justify all the work that is being done on heuristic algorithms. Finally, a third possibility is that the P vs. NP question lies beyond the axioms of complexity theory, so that either answer is unprovable with the current axioms.

Manolito Pérez
  • 1,241
  • A few comments. Firstly, heuristic algorithms are justified regardless of a positive or negative answer to $P=NP$. Heuristic algorithms are used also for problems with polynomial solutions which are still too computationally expensive. Even if $P=NP$ we will certainly still use heuristics to more efficiently solve problems. Secondly, I'm not entirely sure but I don't think that P vs. NP can be undecidable. What is certain is that P vs. NP can only be undecidable if $P\ne NP$. Of course, the answer may simply be beyond human capacity. E.g., if polynomial algos for NP-complete probs are too long – Ittay Weiss Oct 14 '14 at 08:56
  • Back in the 60's, Edmonds had already observed that most problems tend to fall into one of two categories: either they can be solved in polynomial time, with a low-degree polynomial, or they need exponential time. There are of course intermediate problems (e.g. problems with a high-degree polynomial, etc.). Nevertheless, those problems are rather scarce, and in any case, their execution time can be greatly improved by parallel algorithms and by the use of more powerful computers. Thus, the best justification for heuristic techniques is P$\neq$NP (not the only one, of course). – Manolito Pérez Oct 14 '14 at 10:02
  • I don't quite agree. There are plenty of important algorithms with polynomial time of degree 3 or 4. Such problems are hardly feasible for only moderately large inputs. Making computers faster usually does not improve things much since the size of problems tend to increase as well. Parallelism also doesn't help much since it does not reduce the degree of polynomials. The best justification for heuristic techniques is that they are effective for solving both polynomial time problems and other problems. – Ittay Weiss Oct 14 '14 at 10:07