  The trust region subproblem with a fixed number m additional linear
inequality constraints, denoted by (Tm), have drawn much attention recently.
The question as to whether Problem (Tm) is in Class P or Class NP remains open.
So far, the only affirmative general result is that (T1) has an exact SOCP/SDP
reformulation and thus is polynomially solvable. By adopting an early result of
Martinez on local non-global minimum of the trust region subproblem, we can
inductively reduce any instance in (Tm) to a sequence of trust region
subproblems (T0). Although the total number of (T0) to be solved takes an
exponential order of m, the reduction scheme still provides an argument that
the class (Tm) has polynomial complexity for each fixed m. In contrast, we show
by a simple example that, solving the class of extended trust region
subproblems which contains more linear inequality constraints than the problem
dimension; or the class of instances consisting of an arbitrarily number of
linear constraints is NP-hard. When m is small such as m = 1,2, our inductive
algorithm should be more efficient than the SOCP/SDP reformulation since at
most 2 or 5 subproblems of (T0), respectively, are to be handled. In the end of
the paper, we improve a very recent dimension condition by Jeyakumar and Li
under which (Tm) admits an exact SDP relaxation. Examples show that such an
improvement can be strict indeed.
