documentclass[10pt]{article}
usepackage{parskip,multicol,amsmath,amsfonts}

newcommand{defPP}[4]
{
    fbox
    {
        begin{minipage}{textwidth}

            #1

            begin{tabular}{r l}


                textit{Instance:}& #2\
                textit{Parameter:}& #3\
                textit{Problem:}& #4
            end{tabular}

        end{minipage}
    }

}

begin{document}
    defPP{emph{p}-textsc{Bounded-NTM-Halt}}{A deterministic TM $mathbb{M}$, $n in mathbb{N}$ in unary, $k in mathbb{N}$}{$k$}{Decide whether $mathbb{M}$ accepts the empty string at most in $n$ steps and using at most $k$ nondeterministic steps.}

    To show that $p$-textsc{Bounded-NTM-Halt} $in text{W[P]}$, [...]
end{document}