Powody, by wierzyć

Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do rozwiązania. (Shiva Kintali wymienił tutaj kilka innych problemów z kandydatami ).$P \ne NP \cap coNP$

Z drugiej strony Grötschel, Lovász i Schrijver napisali, że „wiele osób uważa, że ”. Ten cytat można znaleźć w Algorytmach geometrycznych i optymalizacji kombinatorycznej, a Schrijver czyni podobne stwierdzenia w optymalizacji kombinatorycznej: wielościany i wydajność . To zdjęcie wyraźnie pokazuje, jak Jack Edmonds zajmuje się tą kwestią.$P=NP\cap coNP$

Jakie dowody potwierdzają wiarę w ? Lub w celu wsparcia P = N P ∩ c o N P ?$P\ne NP\cap coNP$$P=NP\cap coNP$

$P≠UP∩coUP$$P≠UP∩coUP$

$UP \ne NP$$P \ne NP ∩ coNP$

Uwaga: Przesunąłem edycję Mohammada Al-Turkistany'ego mojej odpowiedzi na tę wiki odpowiedź społeczności. Uważa, że ​​doskonale odpowiada na pytanie, ponieważ powszechnie uważa się istnienie permutacji jednokierunkowych. Sam jeszcze nie zrozumiałem wystarczająco różnicy między funkcjami jednokierunkowymi „najgorszego przypadku” i „średniego przypadku”, aby stwierdzić, że naprawdę odpowiada na pytanie.

Uważam, że istnieją bardzo wydajne przestrzennie generatory liczb losowych wysokiej jakości. Pomimo tego przekonania, zwykle używam twistera Mersenne w moim kodzie, który jest wysokiej jakości, ale nie zajmuje dużo miejsca. Brakuje ogniwa między efektywnością przestrzeni a NP∩coNP, to tylko przeczucie, że istnieje związek.

Pozwól, że spróbuję podać jeden powód, dla którego uważam, że „prawdziwą przypadkowość” można bardzo skutecznie symulować / aproksymować przestrzeń. Wiemy, że możliwe jest tworzenie liczb pseudolosowych, które są wystarczająco losowe dla wszystkich praktycznych celów (w tym kryptografii). Wiemy również, że stosowanie (niewielkiej liczby ustalonych) dużych liczb pierwszych w konstrukcji generatorów liczb pseudolosowych rzadko jest złym pomysłem. Wiemy z domniemań takich jak Riemanna, że ​​prawie wszystkie liczby pierwsze zawierają wysoki stopień przypadkowości, ale wiemy również, że nie jesteśmy jeszcze w stanie tego rygorystycznie udowodnić.

Czy istnieje intuicyjne wyjaśnienie, dlaczego liczby pierwsze zachowują się jak liczby losowe? Liczby pierwsze są uzupełnieniem liczb złożonych. Uzupełnienie dobrze wychowanego zestawu jest często bardziej skomplikowane niż zestaw oryginalny. Liczby złożone składają się z liczb pierwszych, co z kolei już nadaje temu zestawowi pewną złożoność.

Tło Próbowałem kiedyś zrozumieć, dlaczego P ≠ NP jest trudne. Zastanawiałem się, czy przybliżenie wewnętrznych grup symetrii instancji problemu przez grupy nilpotentne może nie prowadzić do „algorytmu abstrakcji” zdolnego do wglądu w wewnętrzną strukturę instancji problemu. Ale potem zdałem sobie sprawę, że nawet obliczenie struktury grupy nilpotentnej zawiera faktoring jako szczególny przypadek. Pytanie o proste podgrupy cyklicznej grupy rzędu n jest równoznaczne z wyznaczeniem czynników pierwszych n. I klasyfikacja skończonych grup nilpotentnychzawiera jeszcze gorsze podproblemy związane z izomorfizmem grafowym. To wystarczyło, aby przekonać mnie, że takie podejście nie pomoże. Ale moim następnym krokiem było zrozumienie, dlaczego faktoring jest trudny i powyższa odpowiedź jest tym, co wymyśliłem. To wystarczyło, żeby mnie przekonać, więc może będzie to również przekonujące dla innych ludzi. (Nie wiedziałem wtedy o grupoidach lub odwrotnych półgrupach, które prawdopodobnie są bardziej odpowiednie niż grupy nilpotentne do obsługi wewnętrznych symetrii. Mimo to argument, dlaczego takie podejście nie będzie skuteczne, pozostaje taki sam.)