Is there a certain time frame for which the computer must complete the verification and solving?
I'm wondering if it is possible to extend the time (or increase the complexity) of verifying a problem, so that the verification takes just as long as solving. If "quick" means relatively fast, then both would be answered quickly with a fast computer.
I'm assuming this isn't so, but I wanted to hear more about why or why not this would fit the criteria of the problem.
I'm wondering if it is possible to extend the time (or increase the complexity) of verifying a problem, so that the verification takes just as long as solving. If "quick" means relatively fast, then both would be answered quickly with a fast computer.
I'm assuming this isn't so, but I wanted to hear more about why or why not this would fit the criteria of the problem.
-
Quick means that it solves it in polynomial time. Its referring to the running time being bounded in relation to the size of the input being used in the algorithm. So yes a faster computer will solve something faster, but if the relationship is still larger (say exponential) then it still fails to be P no matter how quickly the computer runs