Questions marquées «np»

J'aimerais votre aide pour prouver que la langue est décidable ssi .L = { ⟨ M⟩ | L ( M) ∈ N P ∖ P }L={⟨M⟩|L(M)∈NP∖P}L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}P = N PP=NP\mathrm{P}=\mathrm{NP} Si , je comprends que c'est le langage des machines Turing vides....

Supposer ΠΠ\Pi est un problème de décision décidable. Est-ce que Π ∉ NPΠ∉NP\Pi\not \in NP impliquer ΠΠ\Pi est NPNPNP-Difficile? Edit: si l'on suppose qu'il existe Π ∈ c o NP∖ NPΠ∈coNP∖NP\Pi\in coNP\setminus NPalors nous avons terminé. Pouvons-nous réfuter la réclamation sans hypothèses...

Ma question est la suivante. Supposons que est un problème NP-difficile. Étant donné une instance arbitraire de et supposant qu'un adversaire sait que cette instance est facile à résoudre, est-il possible de trouver un algorithme déterministe en temps polynomial pour résoudre cette instance...