This is a partial answer, which addresses the practicalities of and workarounds for solving convex optimization problems not satisfying Slater's condition. It does not address the existence of a polynomial time algorithm when Slater's condition is not satisfied.
Most primal-dual interior point solvers are predicated on Slater's condition being satisfied. To the extent that it isn't, or is just barely satisfied numerically, the solver might have difficulty converging, or reliably determining when convergence has occurred. That reflects algorithm design, and is not a claim that Slater's condition is necessary for existence of a polynomial time algorithm.
Nevertheless, reformulating a problem which violates (or almost violates) Slaters' condition to a lower dimensional space in which it is satisfied, can prove quite helpful to algorithm performance and reliability.
Dimensionality reduction can apply, for instance, to Linear SDP (Semidefinite Programming) problems. If Slater's condition is not satisfied in the original formulation, meaning, there is no non-empty interior relative to the nonlinear (e.g., semidefinite) constraints, that might be resolvable by reformulating in a lower dimensional space.
For example, assume $A$ is an n by n symmetric positive semidefinite (PSD) input matrix, B is an n by n matrix variable constrained to be PSD, and there is a constraint trace(A*B) = 0. This formulation violates Slater's condition if $A$ is not of full rank, in which case the solver might have difficulty on some problem instances. But this problem can be reformulated because trace(A*B) = 0 with A and B PSD, implies $B$ is in the nullspace of $A$. So instead of using $B$ as the optimization variable, let $Z$ be the n by d basis for the nullspace of $A$, and let $C$ be a d by d PSD matrix variable. Then use $ZCZ^T$ in place of $B$, and omit the constraint trace(A*B) = 0, because it is satisfied by construction in this reformulation. The reformulated problem now satisfies Slater's condition, and should be well-behaved numerically. It also has the advantage of being a smaller problem. In this example, there is a polynomial-time algorithm for solving the problem which violated Slaters's condition; it is achieved by utilizing the reformulation.
