slovodefinícia
np-complete
(foldoc)		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/).

[Other examples?]

(1995-04-10)
podobné slovodefinícia
np-complete
(foldoc)		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/).

[Other examples?]

(1995-04-10)

Nenašli ste slovo čo ste hľadali ? Doplňte ho do slovníka.

na vytvorenie tejto webstránky bol pužitý dictd server s dátami z sk-spell.sk.cx a z iných voľne dostupných dictd databáz. Ak máte klienta na dictd protokol (napríklad kdict), použite zdroj slovnik.iz.sk a port 2628.

online slovník, sk-spell - slovníkové dáta, IZ Bratislava, Malé Karpaty - turistika, Michal Páleník, správy, údaje o okresoch V4