O “Objeto alcançável” é realmente um problema completo do NP?

Eu estava lendo este artigo, onde os autores explicam o Teorema 1, que afirma que "Objeto alcançável" (conforme definido no artigo) é NP-completo. No entanto, eles provam a redução apenas em uma direção, ou seja, de 2P1N SAT para Objeto alcançável. Isso prova apenas que o problema é difícil de NP; não precisamos provar a direção reversa (2P1N para Objeto alcançável) para provar a completude de NP?

Um problema $P$ é NP-completo se:

1. $P$ é NP-difícil e
2. $P \in \textbf{NP}$.

Os autores fornecem uma prova do item 1. O item 2 provavelmente é aparente (e deve ser claro para o público do artigo). Para a comprovação do item número 1, você só precisa de uma redução (muitos) de um problema completo de NP (por exemplo, SAT) para$P$; não há necessidade de construir uma redução na direção oposta.

Os autores afirmam que é fácil mostrar que o problema está no NP. Para provar essa afirmação, faça uma sequência de trocas que levem a um estado como testemunha de que o estado é alcançável. Dada essa sequência de tamanho polinomial, podemos verificar em tempo polinomial que o estado é realmente alcançável executando os swaps.

O que resta a ser mostrado é que há uma sequência de trocas que possui tamanho polinomial. Observe que, como cada agente tem preferências rígidas e só trocará se puder fazer uma troca que ofereça um objeto melhor, cada agente poderá trocar no máximo$n$vezes. Como existem no máximo$n$ agentes, cada sequência de swaps tem no máximo $n^2$ swaps.

Penso que, se houvesse preferências não estritas, seria possível que alguns itens tivessem que passar por longos ciclos para alcançar determinados estados e que, em particular, existam estados em que todas as sequências de swaps tenham tamanho exponencial. No entanto, não consigo pensar em um exemplo imediato de tal problema. No mínimo, não é mais 'fácil' mostrar que o problema com preferências não estritas está no NP.