Na teoria da complexidade, problemas computacionais co-NP-completos são os mais difíceis problemas em co-NP, no sentido de que são os mais propensos a não serem P. Se existisse uma forma de resolver um problema co-NP-completo rapidamente, então esse algoritmo poderia ser usado para resolver todos os problemas co-NP rapidamente. Wikipedia