Abstract: We prove that for an exponentially generic (in the sense of Gromov or Ol'shanskii) class of one-relator groups the isomorphism problem is solvable in at most exponential time as is the problem of deciding if a give one-relator group belongs to this class. The key ingredient of the proof is a more general result that a "random" m-generated n-related group G has only one Nielsen equivalence class of m-tuples generating non-free subgroups. This implies, for example, that G is co-Hopfian. These conclusions are obtained by elementary methods, without using the techniques of R-trees or JSJ-decomposition and without appealing to the results of Zlil Sela. Combined with a probabilistic analysis of the Whitehead algorithm in free groups, our results imply that generic one-relator groups are complete (that is, they have trivial outer automorphism group and trivial center).