  Given $1\le \ell <k$ and $\delta\ge0$, let $\textbf{PM}(k,\ell,\delta)$ be
the decision problem for the existence of perfect matchings in $n$-vertex
$k$-uniform hypergraphs with minimum $\ell$-degree at least
$\delta\binom{n-\ell}{k-\ell}$. For $k\ge 3$, the decision problem in general
$k$-uniform hypergraphs, equivalently $\textbf{PM}(k,\ell,0)$, is one of Karp's
21 NP-complete problems. Moreover, for $k\ge 3$, a reduction of Szyma\'{n}ska
showed that $\textbf{PM}(k, \ell, \delta)$ is NP-complete for $\delta <
1-(1-1/k)^{k-\ell}$. A breakthrough by Keevash, Knox and Mycroft resolved this
problem for $\ell=k-1$ by showing that $\textbf{PM}(k, k-1, \delta)$ is in P
for $\delta > 1/k$. Based on their result for $\ell=k-1$, Keevash, Knox and
Mycroft conjectured that $\textbf{PM}(k, \ell, \delta)$ is in P for every
$\delta > 1-(1-1/k)^{k-\ell}$.
  In this paper it is shown that this decision problem for perfect matchings
can be reduced to the study of the minimum $\ell$-degree condition forcing the
existence of fractional perfect matchings. That is, we hopefully resolve the
"computational complexity" aspect of the problem by reducing it to a well-known
extremal problem in hypergraph theory. In particular, together with existing
results on fractional perfect matchings, this solves the conjecture of Keevash,
Knox and Mycroft for $\ell\ge 0.4k$. Moreover, we also supply an algorithm that
outputs a perfect matching, provided that one exists.
