P=NP How important is Speed?

[pauldodd123]

Hi there,

I have watched a few YouTube videos on P vs NP.   I'm not sure if this is the right place to ask, but I have a quick question.  I was wondering whether to prove P=NP then does the program have to be the exactly the same speed to find a solution to an NPC as to check a solution to an NPC, or can it be slower, still done in polynomial time, but a lot slower.   For example if it takes a few nested loops vs 1 nested loop, but the number of nested loops is not related to the problem size, just to the method of solving the problem?  

Thanks!

Paul

[wtf]

What's NPC? If you don't mind my saying, if you're an expert feel free to tell me to take a hike. But if you "watched a few YouTube videos" I suggest you'd greatly benefit from defining all your terms, summarizing exactly what it is you understand, and exactly what question you're asking. You'll probably answer your own question and/or uncover some uncertainties and gaps in your own understanding.

The way you're talking about a few versus 1 nested loop shows you might be missing the essence of all this. A linear scaling factor doesn't make any difference to anything in the complexity business. X and a million times X are the exact same thing in this subject.

Edited September 29, 2018 by wtf

[taeto]

18 hours ago, pauldodd123 said:

I have watched a few YouTube videos on P vs NP.   I'm not sure if this is the right place to ask, but I have a quick question.  I was wondering whether to prove P=NP then does the program have to be the exactly the same speed to find a solution to an NPC as to check a solution to an NPC, or can it be slower, still done in polynomial time, but a lot slower.   For example if it takes a few nested loops vs 1 nested loop, but the number of nested loops is not related to the problem size, just to the method of solving the problem?  

You assume that to prove P=NP you do it by demonstrating a polytime algorithm to an NP-complete (NPC) problem. And yes, that is the obvious way. And no, there is no restriction whatsoever on the degree of the polynomial which bounds the time demand of your solution algorithm, nor on the size of the constants involved in that polynomial. They could be hugely larger than in a polynomial which bounds the time demand of verifying a proposed certificate of a solution. So long as you get some polynomial bound on execution time, you are good. 

Edited September 29, 2018 by taeto