En teoría de la complejidad computacional, el complemento de un problema de decisión es el problema de decisión que resulta de invertir las respuestas sí y no.[1]​ De manera equivalente, si se definen los problemas de decisión como conjuntos de cadenas finitas, entonces el complemento de este conjunto sobre algún dominio fijo es su problema de complemento.[2]​