Problème de rechercheEn informatique théorique, et plus particulièrement en théorie de la complexité et en théorie de la calculabilité, un problème de recherche est un problème algorithmique associé à une relation binaire. Si R est une relation binaire telle que pour tout (R) ⊆ Γ+ et T une machine de Turing, alors T implante R si: Si x est tel qu'il existe un y vérifiant R(x, y) alors T accepte l'entrée x en produisant un résultat z tel que R(x, z) (s'il y a plusieurs y, T n'est astreint à n'en trouver qu'un seul) Si x est tel qu'il n'existe aucune y tel que R(x, y) alors T rejette l'entrée x De manière intuitive, un problème de recherche consiste à trouver, s'il existe, un objet "y" associé à un objet "x".
Schéma d'approximation en temps polynomialEn informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.
Constraint satisfactionIn artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.
