Word:

NP-complete

(complexity)NP-complete - (NPC, Nondeterministic Polynomial time complete) A set or property of computational decision problems 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/.

Translate NP-complete to German
Browse
noxiously
noxiousness
noxiptiline
Noy
Noyade
Noyance
Noyau
Noyer
Noyes
Noyful
Noyls
Noyous
Nozle
Nozzle
Np
NP time
-- NP-complete --
NP-hard
NPA
NPAC
NPC
NPD
NPDA
NPH
NPH insulin
NPI
NPL
NPM
NPMS
NPPL
NPSI
NPSS
NPTN
Definitions Index: # A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

About this site and copyright information - Online Dictionary Home - Privacy Policy