  In automated complexity analysis, noninterference-based type systems
statically guarantee, via soundness, the property that well-typed programs
compute functions of a given complexity class, e.g., the class FP of functions
computable in polynomial time. These characterizations are also extensionally
complete -- they capture all functions -- but are not intensionally complete as
some polytime algorithms are rejected. This impact on expressive power is an
unavoidable cost of achieving a tractable characterization. To overcome this
issue, an avenue arising from security applications is to find a relaxation of
noninterference based on a declassification mechanism that allows critical data
to be released in a safe and controlled manner. Following this path, we present
a new and intuitive declassification policy preserving FP-soundness and
capturing strictly more programs than existing noninterference-based systems.
We show the versatility of the approach: it also provides a new
characterization of the class BFF of second-order polynomial time computable
functions in a second-order imperative language, with first-order procedure
calls. Type inference is tractable: it can be done in polynomial time.
