Pytania otagowane jako p-vs-np

9
Jakie byłyby rzeczywiste implikacje konstruktywnego dowodu ?
Rozumiem na wysokim poziomie problem i rozumiem, że gdyby absolutnie „udowodniono”, że jest to prawdą w dostarczonym rozwiązaniu, otworzyłoby to drzwi do rozwiązania wielu problemów w dziedzinie informatyki.P=NPP=NPP=NP Moje pytanie brzmi: jeśli ktoś opublikowałby niepodważalny, konstruktywny dowód , jakie byłyby natychmiastowe skutki takiego odkrycia? P=NPP=NPP=NP Nie proszę o opinie na …
3
Dlaczego relatywizacja jest barierą?
Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.P = N PP=NP\mathsf{P} = \mathsf{NP}P ≠ …
3
Czy oznacza, że?
Czy to możliwe, że a liczność jest taka sama jak liczność ? Czy też oznacza, że i muszą mieć różne liczności?P N P P ≠ N P P N PP≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}
1
Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP
Załóżmy, że .P≠NPP≠NPP\neq NP Co możemy powiedzieć o granicach czasu działania wszystkich problemów związanych z NP-zupełnością? tj. jakie są najostrzejsze funkcje dla których możemy zagwarantować, że optymalny algorytm dla dowolnego problemu z NP zakończony będzie w czasie co najmniej i co najwyżej na wejściu o długości ? ω ( L …
2
Jak udowodnić P
Zdaję sobie sprawę, że wydaje się to bardzo głupie (lub zbyt oczywiste, by stwierdzić) pytanie. Jednak w pewnym momencie jestem zdezorientowany. Możemy pokazać, że P NP=== wtedy i tylko wtedy, gdy możemy zaprojektować algorytm, który rozwiązuje dowolny przypadek problemu w NP w czasie wielomianowym. Nie rozumiem jednak, jak, u licha, …
2
Dlaczego twierdzenie Schaefera nie dowodzi, że P = NP?
To chyba głupie pytanie, ale po prostu nie rozumiem. W kolejnym pytaniu wymyślili dychotomia twierdzenia Schaefer jest . Dla mnie wygląda na to, że udowadnia, że ​​każdy problem CSP jest w P lub NP-kompletny, ale nie pomiędzy. Skoro każdy problem NP można przekształcić w czasie wielomianowym w CSP (ponieważ CSP …
5
Wada mojego NP = dowód CoNP?
Mam ten bardzo prosty „dowód” na NP = CoNP i myślę, że gdzieś coś zrobiłem źle, ale nie mogę znaleźć, co jest nie tak. Czy ktoś może mi pomóc? Niech A będzie pewnym problemem w NP, i niech M będzie decydującym dla A. Niech B będzie dopełnieniem, tj. B jest …
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.