Eğer bir problemin X (karar problemi) NP-Complete olduğu biliniyorsa ve problem Y'ye indirgenmişse, problem Y'nin NP-Complete olduğunu söyleyebilir misiniz?

Question

Bir problem X'in (karar problemi) NP-Complete olduğu biliniyorsa ve polinomsal zamanda Y'ye indirgenmiş olduğu kanıtlanırsa, problem Y'nin NP-Complete olduğunu söyleyebilir misiniz?

İlk düşüncem hayır, sorun Y'nin NP'de olduğunu göstermesi gerekiyordu. Fakat daha sonra düşündüğümüzden sonra, X Y'ye düşerse, Y zaten NP-Complete olarak kabul edilir. Şimdi sadece kafam karıştı ... herhangi bir yardım takdir edilecektir. contrarium başına

Answer 1

Argumentum:

x ∈ NP ve X, ⇔, Y ve Y ∉ NP X ∉ NP edin.

Answer 2

Sorun X - Emin
Sorun Y - X NP olduğunu kanıtlamak için

NP

, size Sonra bunu biliyor Y deki bir probleme X her problemi azaltmak için adımları izleyebilirsiniz olduğunu göstermektedir X problemi en azından eşdeğer Y problemi kadar zor.

Yani hayır, sen Y ile başlamak ve daha sonra X

azaltmayı gerekir

Answer 3

SAT TÜM için tek bir çağrıda çözülebilir, ama bu TÜM NP olduğu anlamına gelmez.

Answer 4

Evet, doğru. Sorununuzu zaten bilinen NP tamamlanmış bir soruna polinom zamanında azaltabilirsiniz, ancak bu çok zor bir görev olarak kabul edilir. Bu yüzden zaten bir NP tam problemi seçin ve sorununuzu azaltın ve bunun NP'de olduğunu da gösterin, o zaman probleminiz NP tam olacaktır.

Answer 5

Henüz değil, bir sorun L NP-tam olduğunu kanıtlamak için birkaç adım

gerekir, aşağıdaki adımları yapmanız gerekir:

1. senin sorunun L aittir kanıtlayın np
3. Pro L'lik L 'dönüştüren bir algoritma f tarif
4. ', bilinen bir NP tam problem L seçin (o polinom zaman içinde kontrol edilebilir bir çözelti verilmiştir) senin algoritma doğru olduğunu ettik (resmi: x ∈ L' f (x) ∈ L yalnızca ve varsa)
5. o algo f polinom zamanda gerçekleşir kanıtlayın

Şimdiye kadar adımı 2,3 var 4
Redüksiyonun polinom olduğunu (adım 5)
ve problemin NP'ye (adım 1) ait olduğunu göstermeniz gerekir, bu bir çözüm polinom zamanında doğrulanabilir.