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.