Certain computations, although theoretically possible, have such high resource
requirements that in practice they must be rejected as unrealistic on existing
computers, as well as on supercomputers yet to be designed. Such problems are
sometimes called intractable to indicate that, while in principle computable,
there is no realistic hope of a practical algorithm. To understand this better,
computer scientists have attempted to put the idea of intractability on a formal
basis. One attempt to define the term intractable is made in what is generally
called the Cook-Karp thesis. In the Cook-Karp thesis, a problem that is in P is
called tractable, and one that is not is said to be intractable.
Is the Cook-Karp thesis a good way of separating problems we can solve
realistically from those we cannot? The answer is not clear-cut. Obviously, any
computation that is not in P has time-complexity that grows faster than any
polynomial, and its requirements will increase very quickly with the problem
size. Even for a function like 2 0.1n , this will be excessive for large n, say n ≥
1000, so we might feel justified in calling a problem with this complexity
intractable. But what about problems that are in DTIME (n 100 )? While the CookKarp thesis calls such a problem tractable, one surely cannot do much with it,
even for small n. The justification for the Cook-Karp thesis seems to lie in the
empirical observation that most practical problems in P are in DTIME (n),
DTIME (n 2 ), or DTIME (n 3 ), while those outside this class tend to have
exponential complexities. Among practical problems, a clear distinction exists
between problems in P and those not in P.
14.5 Some NP Problems
Computer scientists have studied many NP problems, that is, problems that can
be solved nondeterministically in polynomial time. Some of the arguments
involved in this are very technical, with a number of details that have to be
resolved.
Traditionally, complexity questions are studied as languages, in such a way
that the cases that satisfy the stated conditions are described by strings in some
language L, while those that do not are in . So, often the first thing that needs
to be done is to rephrase our intuitive understanding of the problem in terms of a
language.
Example 14.6
requirements that in practice they must be rejected as unrealistic on existing
computers, as well as on supercomputers yet to be designed. Such problems are
sometimes called intractable to indicate that, while in principle computable,
there is no realistic hope of a practical algorithm. To understand this better,
computer scientists have attempted to put the idea of intractability on a formal
basis. One attempt to define the term intractable is made in what is generally
called the Cook-Karp thesis. In the Cook-Karp thesis, a problem that is in P is
called tractable, and one that is not is said to be intractable.
Is the Cook-Karp thesis a good way of separating problems we can solve
realistically from those we cannot? The answer is not clear-cut. Obviously, any
computation that is not in P has time-complexity that grows faster than any
polynomial, and its requirements will increase very quickly with the problem
size. Even for a function like 2 0.1n , this will be excessive for large n, say n ≥
1000, so we might feel justified in calling a problem with this complexity
intractable. But what about problems that are in DTIME (n 100 )? While the CookKarp thesis calls such a problem tractable, one surely cannot do much with it,
even for small n. The justification for the Cook-Karp thesis seems to lie in the
empirical observation that most practical problems in P are in DTIME (n),
DTIME (n 2 ), or DTIME (n 3 ), while those outside this class tend to have
exponential complexities. Among practical problems, a clear distinction exists
between problems in P and those not in P.
14.5 Some NP Problems
Computer scientists have studied many NP problems, that is, problems that can
be solved nondeterministically in polynomial time. Some of the arguments
involved in this are very technical, with a number of details that have to be
resolved.
Traditionally, complexity questions are studied as languages, in such a way
that the cases that satisfy the stated conditions are described by strings in some
language L, while those that do not are in . So, often the first thing that needs
to be done is to rephrase our intuitive understanding of the problem in terms of a
language.
Example 14.6