Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs

For any $\gamma >0$, Keevash, Knox and Mycroft constructed a polynomial-time algorithm to determine the existence of perfect matchings in any $n$-vertex $k$-uniform hypergraph whose minimum codegree is at least $n\mathrm{/}k+\gamma n$. We prove a structure theorem that enables us to determine the existence of a perfect matching for any $k$-uniform hypergraph with minimum codegree at least $n\mathrm{/}k$. This solves a problem of Karpi'nski, Ruci'nski and Szyma'nska completely. Our proof uses a lattice-based absorbing method.