Um problema é NP se é possível verificar uma solução em tempo polinomial ou (esses conceitos são equivalentes) se ele é resolvido em tempo polinomial em uma máquina não determinística*.
A máquina não determinística percorre todos os caminhos para a solução paralelamente, por isso o tempo é polinomial pra esse tipo de problema.
Se um problema está em NP, o seu complemento está em Co-NP. Por exemplo: temos que SAT pertence a NP, e UNSAT pertence a CoNP. Sabemos que esses problemas têm a mesma complexidade, porém não podemos concluir que NP=CoNP porque a complexidade para resolver não é o motivo pelo qual um está em um conjunto e outro está no outro (e sim a complexidade para verificar uma solução).
Não deve ter ficado claro, mas eu escrevi antes de esquecer.
* NP: Não-determinístico Polinomial?