2 ms·

Here's something that I've always been confused about regarding P vs NP: It seems like what researchers are looking for is not necessarily an answer yes or no,

by bhousel 17y ago

Here's something that I've always been confused about regarding P vs NP: It seems like what researchers are looking for is not necessarily an answer yes or no, but really a transform that would convert NP problems into P ones. I have a background in electrical engineering, where it is common to use Laplace and Fourier transforms to convert differential equations in the time domain to polynomial equations in the frequency domain, so I see the P vs NP issue to be somewhat analogous to that. Am I understanding the issue, or completely off?

roundsquare 17y ago
Well, complexity theory does have this concept. I.e. you can convert one problem to another, they call it a reduction. I.e. you reduct problem A to problem B. So, in that sense, if you can somehow reduce an NP-Complete problem to a problem in P, then yes, you would prove that P=NP. However, this would not be the only way to prove this. If you could just find a polynomial time algorithm for any NP-Complete problem, then you've proved P=NP. Of course, most expert think P != NP, so if thats true then you'll fail in your attempts to do these...