English Dictionary
◊ DID YOU MEAN COMPLETE?
complete
adj 1: having every necessary or normal part or component or step;
"a complete meal"; "a complete wardrobe"; "a complete
set pf the Britannica"; "a complete set of china"; "a
complete defeat"; "a complete accounting" [ant: {incomplete},
{incomplete}]
2: perfect and complete in every respect; having all necessary
qualities; "a complete gentleman"; "consummate happiness";
"a consummate performance" [syn: {consummate}]
3: (botany) having all four whorls or principal parts--sepals
and petals and stamens and carpels (or pistils); "complete
flowers" [ant: {incomplete}]
4: highly skilled; "an accomplished pianist"; "a complete
musician" [syn: {accomplished}]
5: without qualification; used informally as (often pejorative)
intensifiers; "an arrant fool"; "a complete coward"; "a
consummate fool"; "a double-dyed villain"; "gross
negligence"; "a perfect idiot"; "pure folly"; "what a
sodding mess"; "stark staring mad"; "a thoroughgoing
villain"; "utter nonsense" [syn: {arrant(a)}, {complete(a)},
{consummate(a)}, {double-dyed(a)}, {everlasting(a)}, {gross(a)},
{perfect(a)}, {pure(a)}, {sodding(a)}, {stark(a)}, {staring(a)},
{thoroughgoing(a)}, {utter(a)}]
6: having come or been brought to a conclusion; "the harvesting
was complete"; "the affair is over, ended, finished"; "the
abruptly terminated interview" [syn: {concluded}, {ended},
{over(p)}, {all over}, {terminated}]
v 1: come or bring to a finish or an end; "He finished the
dishes"; "She completed the requirements for her
Master's Degree"; "The fastest runner finished the race
in just over 2 hours; others finished in over 4 hours"
[syn: {finish}]
2: bring to a whole, with all the necessary parts or elements;
"A child would complete the family"
3: complete or carry out; "discharge one's duties" [syn: {dispatch},
{discharge}]
4: complete a pass, in football [syn: {nail}]
5: write all the required information onto a form; "fill out
this questionnaire, please!"; "make out a form" [syn: {fill
out}, {fill in}, {make out}]
English Computing Dictionary
◊ NP-COMPLETE
NP-complete
(NPC, Nondeterministic Polynomial time complete)
A set or property of computational {decision problem}s which
is a subset of {NP} (i.e. can be solved by a
{nondeterministic} {Turing Machine} in {polynomial} time),
with the additional property that it is also {NP-hard}. Thus
a solution for one NP-complete problem would solve all
problems in NP. Many (but not all) naturally arising problems
in class NP are in fact NP-complete.
There is always a {polynomial-time algorithm} for transforming
an instance of any NP-complete problem into an instance of any
other NP-complete problem. So if you could solve one you
could solve any other by transforming it to the solved one.
The first problem ever shown to be NP-complete was the
{satisfiability problem}. Another example is {Hamilton's
problem}.
See also {computational complexity}, {halting problem},
{Co-NP}, {NP-hard}.
{(http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/)}
[Other examples?]
(1995-04-10)
 np  np time  np-complete  np-hard  npc