3 ms·
> A really interesting aspect of NP-complete problems is that the can be solved in P, but require NP to check for correctness. Sorry, maybe I'm confused by wha
by roundsquare 17y ago
> A really interesting aspect of NP-complete problems is that the can be solved in P, but require NP to check for correctness.
Sorry, maybe I'm confused by what your saying, but thats not quite right.
NP Complete problems cannot be solved in polynomial time unless P = NP. But, given a potential solution, it can be verified in poly time.
I'll try to translate that to the world of proteins... but I don't know much biology.
Given a protein sequence, finding a folding that minimizes the energy (formally, finding a folding where the energy is less than some value K) cannot, in general, be done in polynomial unless P = NP. However, given a potential folding, we can verify if its the minimum (formally, we can verify if the energy is less than K).
Am I right with this? Can someone verify? I would hate to spread disinformation.
- ars 17y agoYou are both saying the same thing. But giving the same words different meanings. Let me try: A possible solution can be found in P time. But checking if it's THE solution (i.e. the best solution) requires NP time. Does solve mean: solve a solution? or solve for the final (best) solution? Does verify mean: verify that the solution works? or that you verified that it's the best answer?
- roundsquare 17y agoUrg... I think I know why I'm confused. P, NP, etc... are sets of yes/no or boolean problems. That is to say, the answer to these questions are always "Yes" or "No". Lets take the traveling saleperson problem. You have a bunch of cities, and the distances between them. Also, your given a threshold, K. Your goal is to tell me if there is a path through the cities that has a distances less than K. All you output is "Yes" or "No" This can be converted to an algorithm for finding the shortest path in polynomial time, which is the optimization version of the problem. But this problem is not in NP, its not even a candidate to be in NP. However, I'm having trouble relating to what your saying. > A possible solution can be found in P time. But checking if it's THE solution (i.e. the best solution) requires NP time. In terms of traveling salesperson, what is "a possible solution" and what is "the solution"? I'm guessing "the solution" is the shortest path, but if "a possible solution" means some path through all the cities... then that doesn't help much. Even for problems that are harder than NP, I can come up with a possible solution in polynomial time as long as the size of the solution is polynomial (I'm having difficulty thinking up an example at the moment). Tell me if I'm being hard-headed or overly semantic...
- jballanc 17y agoI think you're neither. My understanding is based on practical applications. That is, as far as I understand it, you're right about P and NP. From a practical point of view, the optimization of the problem depends on knowing what the smallest K is that has a "Yes" answer. So, yes, checking the solution is P. Finding the solution is NP. Optimizing for K is, therefore, intractable. Does that sound (at least somewhat) right?
- roundsquare 17y agoYep, we agree! One small thing though, its only intractable if P != NP.
- jballanc 17y agoYes, I think this pretty much sums up the confusion I've been having. Lack of understanding of jargon on my part...