Discussion Board
There are no previous messagesGo to the following message
Current Forum: 15-211 Main Forum
Date: Mon Dec 17 2001 3:37 pm
Author: White, David <white3@andrew.cmu.edu>
Subject: NP problems....
So I still have questions about what it means for a problem
to be NP. I think what it means is that the problem will
have a solution that can be verified in poly-nomial time.

Does this mean that all simple problems like, unionFind, shortest-path, sorting, are NP problems?

A NP complete problem means then that one of the already NP complete problems can be reduced to this problem. Right?

Thanks
Post response
There are no previous messagesGo to the following message
Current Thread Detail:
NP problems....      White, David      Mon Dec 17 2001 3:37 pm       
Re: NP problems....      Scherlis, William L.      Mon Dec 17 2001 4:12 pm       
Re: NP problems....      Shi, Ying      Mon Dec 17 2001 4:26 pm       
Re: NP problems....      Lee, Charles C.      Mon Dec 17 2001 7:44 pm       
Re: NP problems....      Maxim, Michael G.      Mon Dec 17 2001 8:00 pm       
Re: NP problems....      White, David      Mon Dec 17 2001 8:42 pm       
Re: NP problems....      Maxim, Michael G.      Tue Dec 18 2001 1:38 pm       
Re: NP problems....      White, David      Tue Dec 18 2001 3:34 pm       
Re: NP problems....      Maxim, Michael G.      Tue Dec 18 2001 7:09 pm       
Back to previous screen