What does "quick" mean in the P=NP Millennium Prize Problem
Favorites|Homepage
Subscriptions | sitemap
HOME > Mathematics > What does "quick" mean in the P=NP Millennium Prize Problem

What does "quick" mean in the P=NP Millennium Prize Problem

[From: ] [author: ] [Date: 11-05-11] [Hit: ]
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,......
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.

-
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
1
keywords: quot,Millennium,Problem,NP,Prize,in,quick,the,mean,does,What,What does "quick" mean in the P=NP Millennium Prize Problem
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .