0
$\begingroup$

I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)".

(latest version is sixth.)

There are some discriptions in this book that I don't understand

Not all binary strings are instances of Hamiltonian Circuit but only those representing an undirected graph. For most interesting decision problems the in- stances are a proper subset of the 0-1-strings. We require that we can decide in polynomial time whether an arbitrary string is an instance or not:

  • quote from p350

decision problem is pair P = (X,Y), where X is a language decidable in polynomial time.

  • quote p351

Why decision problem required that decide in polynomial time whether an arbitrary string is an instance or not?

I can't found any reasons of this restriction in the book.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Decision problems are not necessarily decided in polynomial time, I believe that the citations are lacking some context. $\endgroup$ – Yamar69 Dec 4 '19 at 9:35
  • $\begingroup$ This description is written in chap 15-3 P and NP(chap 15 is "NP-Completeness") . I think this restriction may be need to be NP class. $\endgroup$ – y y Dec 5 '19 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.