Pytania otagowane jako p-vs-np

Pytania dotyczące lub związane z P vs. NP

1
Podejście Gowersa do „dyskretnej determinacji Borela”
Gowers przedstawił ostatnio problem, który nazywa „dyskretną determinacją Borela”, którego rozwiązanie dotyczy dolnych granic obwodu dowodzenia. Czy możesz podać podsumowanie podejścia, które jest dostosowane do grupy teoretyków złożoności? Co potrzeba, aby to podejście wykazało cokolwiek , w tym ponowne udowodnienie znanych dolnych granic?
1
Bariery, aby pokazać
Wszyscy wiemy, że pokazanie ma bariery. Wszyscy badaliśmy te bariery, ponieważ uważamy, że P ≠ N P.P≠NPP≠NPP\ne NPP≠NPP≠NPP\ne NP . Załóżmy jednak, że i są mądrzy ludzie, którzy wierzą, że taka możliwość istnieje . Jeśli tak rzeczywiście jest, to sam fakt, że nie widzieliśmy żadnych dobrych algorytmów, wskazuje, że mogą …
15 p-vs-np  barriers 
3
Dlaczego informatycy w ogóle pracują przy założeniu, że P ≠ NP?
Jadąc od tła matematyki, wydaje mi się, że interesujący na całego komputera naukowcy mają tendencję do pracy przy założeniu, że P≠NPP≠NPP \neq NP . Chociaż nie ma żadnego dowodu w obu przypadkach, chyba że coś może być szczególnie niepotwierdzone zarówno w matematyce, jak i nauce, jest podejmowane z dużą ilością …
12 p-vs-np 
2
Poszukuję źródła literatury do naśladowania
Jestem pewien, że nie jako pierwszy rozważyłem pomysł, który zamierzam przedstawić. Przydałoby się jednak znalezienie literatury związanej z tym pomysłem. Chodzi o to, aby zbudować Maszynę Turinga M z właściwością, że jeśli P = NP, wówczas M rozwiąże 3-SAT w czasie wielomianowym. (Wybór 3-SAT jest arbitralny. To może być naprawdę …
1
Optymalne solwery NP
Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć testy czy jest to poprawna”. Jest optymalna w tym sensie, że biorąc pod uwagę …
10
Materiały do ​​nauki o problemie P vs. NP
Niedawno przypomniano mi o problemie vs. jak wyjaśnił Stephen A. Cook z Clay Mathematics Institute.N PP.P.\mathsf{P}N P.N.P.\mathsf{NP} To wzbudziło moje zainteresowanie i chciałbym dowiedzieć się więcej na ten temat. Pierwszym krokiem byłoby lepsze zrozumienie problemu i ogólne zrozumienie tego obszaru. Czy możesz polecić jakieś książki lub inne zasoby, w których …
2
Zmniejszenie P vs. NP do SAT
W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna. Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów, prawdopodobnie jest to nieco niepoprawnie podane. Prosimy o wskazanie poprawek w swoich …
2
O wiarygodności P w porównaniu z NP
Po pierwsze, moje rozumienie twierdzenia o niekompletności Gödla (i logiki formalnej w ogóle) jest bardzo naiwne, podobnie jak moja wiedza z zakresu teoretycznej informatyki (co oznacza, że ​​tylko jeden kurs magisterski odbył się, gdy jestem jeszcze studentem), więc pytanie może być bardzo naiwny. O ile mogłem znaleźć, wiarygodność P w …
3
Czy może istnieć wyjątkowo duży ukryty podzbiór problemów wielomianowo możliwych do rozwiązania w ramach problemów NP-Complete?
Załóżmy, że P! = NP. Wiemy, że w każdej chwili możemy wykonać proste instancje 3-SAT. Możemy również wygenerować coś, co uważamy za trudne wystąpienie (ponieważ nasze algorytmy nie potrafią ich szybko rozwiązać). Czy jest coś, co przeszkadza, by zbiór twardych instancji był arbitralnie mały, o ile dla dowolnej wielkości instancji …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.