[Teoria obliczeń] P=NP?
[Teoria obliczeń] P=NP?
Problem \(\displaystyle{ P=NP?}\) jest \(\displaystyle{ NP-zupełny}\) więc \(\displaystyle{ P=NP}\). Czy takie rozumowanie jest poprawne?
Ostatnio zmieniony 5 sie 2021, o 10:50 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
Re: P=NP?
A może takie jest poprawne: Problem \(\displaystyle{ P=NP}\) jest \(\displaystyle{ NP}\). Załóżmy, że istnieje jakiś algorytm rozwiązujący zagadnienie \(\displaystyle{ P=NP}\) w czasie wielomianowym więc jest \(\displaystyle{ P}\) co daje sprzeczność z tym że jest \(\displaystyle{ NP}\).