In der rechenbetonten Kompliziertheitstheorie die Kompliziertheitsklasse ist NP-equivalent der Satz von Funktionsproblemen, die sowohl NP-easy als auch NP-hard sind. NP-equivalent ist die Entsprechung von NP-complete für Funktionsprobleme.

Zum Beispiel FINDET das Problem, "dass TEILMENGE-SUMME" in NP-equivalent ist. In Anbetracht einer Reihe von ganzen Zahlen, "FINDEN, dass TEILMENGE-SUMME" das Problem ist, eine nichtleere Teilmenge der ganzen Zahlen zu finden, die sich auf Null beläuft (oder das Zurückbringen des leeren Satzes, wenn es keine solche Teilmenge gibt). Dieses Optimierungsproblem ist der Entscheidungsproblem-TEILMENGE-SUMME ähnlich. In Anbetracht einer Reihe von ganzen Zahlen ist TEILMENGE-SUMME das Problem der Entdeckung, ob dort eine Teilmenge besteht, die zur Null resümiert. TEILMENGE-SUMME ist NP-complete.

Um zu zeigen, dass "FINDEN, ist TEILMENGE-SUMME" NP-equivalent, wir müssen zeigen, dass es sowohl NP-hard als auch NP-easy ist.

Klar ist es NP-hard. Wenn wir einen schwarzen Kasten hatten, der gelöst hat, "FINDEN TEILMENGE-SUMME" in der Einheitszeit, dann würde es leicht sein, TEILMENGE-SUMME zu lösen. Bitten Sie einfach den schwarzen Kasten, die Teilmenge zu finden, die zur Null resümiert, dann überprüfen Sie, ob es einen nichtleeren Satz zurückgegeben hat.

Es ist auch NP-easy. Wenn wir einen schwarzen Kasten hatten, der TEILMENGE-SUMME in der Einheitszeit gelöst hat, dann konnten wir es verwenden, um zu lösen, "FINDEN TEILMENGE-SUMME". Wenn es falsch zurückkehrt, geben wir sofort den leeren Satz zurück. Sonst besuchen wir jedes Element in der Ordnung und entfernen es vorausgesetzt, dass TEILMENGE-SUMME noch wahr zurückkehren würde, nachdem wir es entfernen. Sobald wir jedes Element besucht haben, werden wir nicht mehr im Stande sein, jedes Element zu entfernen, ohne die Antwort vom wahren bis falschen zu ändern; an diesem Punkt muss die restliche Teilmenge der ursprünglichen Elemente zur Null resümieren. Das verlangt, dass wir bemerken, dass spätere Eliminierungen von Elementen die Tatsache nicht verändern, dass die Eliminierung eines früheren Elements die Antwort vom wahren bis falschen geändert hat. Im Pseudocode:

Funktion "FINDET TEILMENGE-SUMME" (setzen Sie S)

wenn nicht (TEILMENGE-SUMME (S))

geben Sie {}\zurück

für jeden x in S

wenn TEILMENGE-SUMME (S - {x})

S: = S - {x }\

geben Sie S zurück

Ein anderes wohl bekanntes NP-equivalent Problem ist das Handelsreisender-Problem.

Referenzen

.