La génération automatique de tests structurels à l'aide de la programmation par contraintes se répand de plus en plus dans l'industrie du logiciel. Parmi les critères de couverture les plus stricts, le critère tous-les-chemins exige la génération d'un ensemble de cas de tests tel que tout chemin d'exécution faisable du programme sous test soit exécuté par un des cas de test. Cet article étudie des aspects de calculabilité et de complexité de la génération de tests tous-les-chemins et le rapport entre la complexité et la forme des contraintes issues du programme sous test. Nous définissons deux classes de programmes importantes pour la pratique. Nous montrons d'abord que pour une classe contenant des programmes simples avec de fortes restrictions, la génération de tests est possible en temps polynomial. Pour une classe de programmes plus large où les entrées peuvent être utilisées comme des indices de tableaux (ou décalages de pointeurs), la génération de tests tous-les-chemins s'avère NP-difficile. Quelques expérimentations montrent le temps de génération pour des exemples de programmes des deux classes.