= Strong NP-completeness
{wiki}
= Strongly NP-complete
{synonym}
An <NP> <decision problem> is strongly <NP-complete> when its <NP-hardness> persists with numerical parameters written in the <unary numeral system>. An important proof method bounds every relevant numerical value by a <polynomial> in the remaining explicit <input> size. For the <clique decision problem>, values $k>|V(G)|$ can be mapped to one fixed no-instance; otherwise writing $1^k$ takes only <polynomial time>. The distinction is representation-sensitive, so an explicit <graph> encoding must be specified.
Back to article page
