НП (класа комплексности) — разлика између измена

Садржај обрисан Садржај додат
Autobot (разговор | доприноси)
м knjige+sfn; козметичке измене
Autobot (разговор | доприноси)
м референце
Ред 20:
 
Међу додатним примерима проблема из класе '''НП''' су:
 
* [[Проблем изоморфизма графова]], одређивање да ли се од једног графа може направити други простим преименовавањем чворова
* [[Проблем трговачког путника]], где покушавамо да утврдимо да ли постоји пут одређене дужине који пролази кроз све чворове неког графа
Линија 34 ⟶ 33:
== Пример ==
[[Проблем трговачког путника]] у верзији проблема одлучивања је у класи '''НП'''. Ако је дата матрица у којој су наведене раздаљине између -{N}- проблем се састоји у утврђивању да ли постоји путања која повезује све градове, укупне дужине мање од ''-{k}-''. Недетерминистичка Тјурингова машина може да пронађе такву путању на следећи начин:
 
* У сваком граду она ''погађа'' који следећи град да посети, док не посети сваки град. Ако се заглави, одмах стаје.
* На крају проверава да ли је дужина путање мања од ''-{k}-'' за време -{[[Нотација великог O|O]](''n'')}-.
Линија 44 ⟶ 42:
== Литература ==
* -{ Complexity Zoo: [http://qwiki.caltech.edu/wiki/Complexity_Zoo#np NP]}-
* -{ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp. 979-983.}-
* -{ {{cite book|author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Sections 7.3-7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp. 241-271.}-
* -{David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.}-