  Answer set programming (ASP) is a well-established logic programming language
that offers an intuitive, declarative syntax for problem solving. In its
traditional application, a fixed ASP program for a given problem is designed
and the actual instance of the problem is fed into the program as a set of
facts. This approach typically results in programs with comparably short and
simple rules. However, as is known from complexity analysis, such an approach
limits the expressive power of ASP; in fact, an entire NP-check can be encoded
into a single large rule body of bounded arity that performs both a guess and a
check within the same rule.
  Here, we propose a novel paradigm for encoding hard problems in ASP by making
explicit use of large rules which depend on the actual instance of the problem.
We illustrate how this new encoding paradigm can be used, providing examples of
problems from the first, second, and even third level of the polynomial
hierarchy. As state-of-the-art solvers are tuned towards short rules, rule
decomposition is a key technique in the practical realization of our approach.
We also provide some preliminary benchmarks which indicate that giving up the
convenient way of specifying a fixed program can lead to a significant
speed-up.
  This paper is under consideration for acceptance into TPLP.
