Wie heißt es, wenn zwei Probleme ähnlich sind?

Angenommen, es gibt zwei Probleme $P$ und $Q$.

Wie kann ich das sagen "lösen $P$ ist das gleiche mit dem Lösen $Q$"?

Zum Beispiel, wenn $P$ ist NP-Hard, dann können wir sagen "$P$ kann in Polynomzeit gelöst werden, wenn ein Algorithmus existiert $A$ das löst $Q$ in Polynomzeit ".

Es sollte eine kürzere Frist dafür geben, und ich bin sicher, dass das nicht ähnlich ist .

Ist Äquivalent das richtige Wort?

In der Komplexitätstheorie bevorzugen wir, wenn möglich, formale Definitionen. Zwei Probleme$P,Q$sind polynomial äquivalent, wenn es Polytime-Funktionen gibt$f,g$ so dass $x \in P$ iff $f(x) \in Q$ und $y \in Q$ iff $g(x) \in P$. Dies ist der übliche Begriff der Äquivalenz in der Komplexitätstheorie.

Manchmal bevorzugen wir einen gröberen Begriff der Äquivalenz, der es erlaubt, ein Problem als Orakel zu verwenden. Zwei Probleme$Q,R$sind in Bezug auf Orakelreduktionen polynomiell äquivalent, wenn$Q \in \mathsf{P}^R$ und $R \in \mathsf{P}^Q$oder mit anderen Worten, $Q$ kann in Polynomzeit mit Orakelzugriff auf gelöst werden $R$, und $R$ kann in Polynomzeit mit Orakelzugriff auf gelöst werden $Q$. Nach diesem Begriff sind 3SAT und Co-3SAT (sein Komplement) gleichwertig.

Sofern ich keinen Fehler gemacht habe, sind beide Begriffe Äquivalenzbeziehungen. In beiden Fällen kann das andere Problem in Polynomzeit gelöst werden, das andere auch. Da die zweite allgemeiner ist, scheint sie besser zu Ihrer Beschreibung zu passen, obwohl wir in der Komplexitätstheorie normalerweise den feineren ersten Begriff oder sogar feinere Begriffe wie Lograumreduzierbarkeit und AC ⁰ -Reduzierbarkeit bevorzugen .