¿Hay alguna clase de problemas NP que tengan una solución única? Lo pregunto porque cuando estaba estudiando criptografía leí sobre la mochila y la idea me pareció muy
Quisiera su ayuda para probar que el lenguaje es decidible iff .L={⟨M⟩|L(M)∈NP∖P}L={⟨M⟩|L(M)∈NP∖P}L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}P=NPP=NP\mathrm{P}=\mathrm{NP} Si , entiendo que es el lenguaje de las máquinas de Turing vacías. Entonces es un...
Supongamos que ΠΠ\Pi es un problema de decisión decidible. ¿ Π∉NPΠ∉NP\Pi\not \in NP implica ΠΠ\Pi is NPNPNP -Hard? Editar: si suponemos que existe Π∈coNP∖NPΠ∈coNP∖NP\Pi\in coNP\setminus NP entonces hemos terminado. ¿Podemos refutar el reclamo sin suposiciones...