basic query regarding NP Complete...

Hi,
I have am trying to understand the basics of NP and NP complete.
Can any one help me better my understanding.


Here is my query regarding the same

Do we call a set of problem in NP to be NP complete if each one of them
is reducible to an other ? ie.. if 3-CNF, Boolean satisfiability,
Vertex cover, Hamilton cycle.. problems form a set and each of them is
reducible to one of the other then do we call that set NP-Complete ?

Suppose I have a NDTM that solves the sorting problem by randomly
guessing the order and I have a verifier Algorithm (polynomial) that
outputs a YES if all elements are in order, This problem is in NP.
Supposing I have few other hypothetical problems that are reducible to
this problem will that set form a NP-COMPLETE set ? Since P is a subset
of NP do we have many partitions in class P that are reducible to each
other within that partition and hence NP complete ?

Please correct me if my understanding is wrong.

Thanking you,
Prakash S

.

Relevant Pages

  • Re: [opensuse] 10.3 upgrade
    ... It's above my understanding why Grub needs to be in two partitions, ... a DFSee 'part -b-' report would be useful. ...
    (SuSE)
  • Re: Maximum disk storage under 2000/2003 Server
    ... > Is there any overall limitation to the amount of storage that can ... > My understanding is that the only limit is 2 TB max partition size. ... The number of partitions, however, is still the old 4 max. Remember, ...
    (microsoft.public.windows.server.general)
  • Re: fostex pd6 - recording times?
    ... My understanding is that the PD-6 will close the newly created file as ... the disk partitions to the internal DVD-RAM! ...
    (rec.arts.movies.production.sound)
  • Re: [SLE] How to use Logical Volume Management
    ... I was of the understanding that LVM allowed for the ... >>resizing of partitions, without shutting down the computer etc. ...
    (SuSE)