Are there slight modifications to NP-complete problems which reduce them to P?

Question

Recently I revisited the infinite harmonic series and its barely diverging sum, and how removing all the composite numbers from the sum still produces a divergent series (even more barely). In contrast, the infinite Kempner series shows interesting examples of how exclusion of terms from the harmonic series renders the sum finite. This made me curious about the "boundary" between convergent and divergent series. Several good answers here on Math.SE showed me that there is actually no such thing; one can always find a series which diverges more slowly or which grows higher before converging.

Today I began wondering about something similar regarding problems and whether they are P or NP-complete. Are there problems which are known to be hard, but for which a slight alteration to the common statement of the problem renders it easily solvable? For example, having a small amount of information about the solution, or by slightly weakening the requirements of the problem? How small can the difference be and still bring the problem down from NP-complete to P? If P = NP then this question has a trivial positive answer (in fact, no modification to the original problem is necessary!), but I think this question is still valid for P ≠ NP.

If examples are known, do they have any impact on how P versus NP is tackled?

I apologize if my question is not clear, as my formal education in mathematics stopped shortly after calculus. I can try to clarify it if necessary. Contributions at any level are appreciated.

Answer 1

Every planar map can be colored with $4$ colors. Moreover, a planar map with $n$ countries can be colored with $4$ colors in time $O(n^2)$. So $4$-coloring a planar map is a problem in $P$.

On the other hands, not every planar map need 4 colors; some need only $3$ colors. But it is $NP$-complete to decide whether a planar map can be colored with $3$ colors.

[source: wikipedia]

Answer 2

I have since learned of a very interesting example where a slightly modified problem has a wildly different computational complexity.

The familiar matrix determinant is defined by: $$Det(A)=\sum_{σ∈S_n}(−1)^{sgn(σ)}\prod_{i=1}^{n}a_{i,σ(i)}$$

Naively, computing the determinant of a $n\times n$ matrix can be performed by Laplace expansion, with asymptotic $\mathcal{O} (n!)$ runtime. However multiple techniques provide polynomal-time algorithms, such as LU decomposition in $\mathcal{O} (n^3)$ time. The current asymptotically fastest algorithm using fast matrix multiplication is $\mathcal{O} (n^{2.373})$, and has been conjectured to be as low as $\mathcal{O} (n^{2})$. Regardless, computing the matrix determinant is well within P.

Consider now the matrix permanent, with a very similar, even simpler definition:

$$Per(A)=\sum_{σ∈S_n}\prod_{i=1}^{n}a_{i,σ(i)}$$

It turns out that exactly computing the permanent of a matrix is #P-complete, a class believed to be even harder than NP-complete problems. The current best known algorithm has $\mathcal{O} (n2^n)$ asymptotic runtime.