Answers.com > Wiki Answers > Categories > Technology > Computers > Computer Terminology > Difference between np and np complete?

Difference between np and np complete?

In: Computer Terminology, Computer Science [Edit categories]

Answer:

A problem is 'in NP' if there exists a polynomial time complexity algorithm which runs on a Non-Deterministic Turing Machine that solves it.

A problem is 'NP Hard' if all problems in NP can be reduced to it in polynomial time, or equivalently if there is a polynomial-time reduction of any other NP Hard problem to it.

A problem is NP Complete if it is both in NP and NP hard.

First answer by Tobyodavies. Last edit by Tobyodavies. Contributor trust: 0 [recommend contributor ]. Question popularity: 3 [recommend question].

[report abuse]

Can you answer these Computer Terminology questions?

	What is the size of a typical function field and Estimate the number of functions available in the processor's instruction set?	Answer it!
	What is random bus arbitration?	Answer it!
	What are the system requirements for GIMP?	Answer it!
	How do you rotate a NEC projector image?	Answer it!
	How are reports classified in management information system?	Answer it!

Relevant answers:

What is the difference between NP and NP Complete problems?
- a problem in NP means that it can be solved in polynomial time with a non-deterministic turing machine - a problem that is NP-hard means that all problems in NP are "easier" than this problem - a...
What is the difference between Complete and Finish?
The words complete and finish have very similar meanings, but there is a slight difference of nuance. When something is completed, we expect that it is complete, and it has everything that it is...
How do you explain what P NP and NP complete complexity classes are in a simple way?
P is the class of problems that can be solved in polynomial time. That is, the size of the input affects the length of the computation multiplicatively.NP is the class of problems in which the effect...
What is the difference between complete tetany and tetanus?
compelete is applying stimuli at a rate that the cell can not relax between subsequent contractios. The max force will allow the cell to freeze, incompete is when the cell can not be compelety...
What is the difference between complete and incomplete metamorphosis?
Incomlete Metamorphosis is only 3 stages, egg, nymph then adult. Complete Metamorphosis is eggs, then larva, than caterpillar, pupa, and then the adult. A nymph is the young of an insect.