A random pair of elements of $\mathop{SL}(n, \mathbb{Z})$ (where random is defined by taking a generating set, and picking two random long words) almost certainly (meaning, with probability approaching $1$ exponentially fast in the length of the words) generates a Zariski dense free subgroup (the "free" part is a result of Richard Aoun). The Zariski density part can be confirmed/denied in polynomial time. However, checking that the group is free is almost certainly (in some philosophical sense) undecidable for $n>2.$