  In this paper we propose a generalization of the extension complexity of a
polyhedron $Q$. On the one hand it is general enough so that all problems in
$P$ can be formulated as linear programs with polynomial size extension
complexity. On the other hand it still allows non-polynomial lower bounds to be
proved for $NP$-hard problems independently of whether or not $P=NP$. The
generalization, called $H$-free extension complexity, allows for a set of valid
inequalities $H$ to be excluded in computing the extension complexity of $Q$.
We give results on the $H$-free extension complexity of hard matching problems
(when $H$ are the odd set inequalities) and the traveling salesman problem
(when $H$ are the subtour elimination constraints).
