Czy są jakieś sprzeczne z intuicją wyniki w informatyce teoretycznej?

Pewne paradoksy matematyczne i logiczne można prawdopodobnie automatycznie zastosować do komputerów, ale czy istnieją jakieś paradoksy odkryte w samej informatyce?

Przez paradoksy rozumiem sprzeczne z intuicją wyniki, które wyglądają jak sprzeczność.

Uważam, że przepływ sieci jest wielomianowy, licznik czasu jest intuicyjny. Na pierwszy rzut oka wydaje się to o wiele trudniejsze niż wiele problemów NP-trudnych. Innymi słowy, w CS jest wiele wyników, w których czas ich rozwiązania jest o wiele lepszy niż można by się spodziewać.

Rodzina wyników sprzecznych z intuicją to cała rodzina wyników „udowodnić górną granicę, aby udowodnić dolną granicę”. Wynik Meyera, że implikuje jest jednym z przykładów tego, i przyszło mi to do głowy zarówno z pracy GET Ketana Mulmuleya, jak i niedawnej pracy Ryana Williamsa wynik, który ponownie użył górnej granicy dla CIRCUIT-SAT, aby udowodnić dolną granicę dla pod względem .$\mathsf{P} = \mathsf{NP}$N E X P A C $\mathsf{EXP} \not\subseteq \mathsf{P}/poly$$\mathsf{NEXP}$$\mathsf{ACC}$

SAT ma algorytm wielomianowy tylko wtedy, gdy P = NP. Nie wiemy, czy P = NP. Mogę jednak zapisać algorytm dla SAT, który jest czasem wielomianowym, jeśli P = NP jest prawdziwe. Nie znam prawidłowego odniesienia do tego, ale strona wikipedia podaje taki algorytm i przypisuje Levinowi.

Obliczalność z pewnością psuje większość uczniów. Piękny przykład z wysokim współczynnikiem zamieszania jest następujący:

$f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{cases}$

Czy obliczalny?$f$

Odpowiedź brzmi tak; zobacz dyskusję tutaj . Większość ludzi natychmiast próbuje zbudować z obecną wiedzą. To nie może działać i prowadzi do postrzeganego paradoksu, który jest tak naprawdę tylko subtelnością.$f$

Jednym z zaskakujących i sprzecznych z intuicją wyników jest to, że , udowodniono za pomocą arytmetyki około 1990 r.$IP = PSPACE$

Jak to ujęli Arora i Barak (s. 157) „Wiemy, że sama interakcja nie daje nam żadnych języków poza NP. Podejrzewamy również, że sama randomizacja nie dodaje znaczącej mocy do obliczeń. Więc ile mocy mogłaby kombinacja randomizacji i zapewnić interakcję? ”

Niby całkiem sporo!

Jak powiedział Philip, twierdzenie Rice'a jest dobrym przykładem: intuicja przed badaniem obliczalności jest taka, że ​​z pewnością musimy coś obliczyć w obliczeniach. Okazuje się, że możemy tylko obliczyć coś na temat niektórych obliczeń.

Co powiesz na publikacje Martina Escardo pokazujące, że istnieją nieskończone zbiory, które można wyczerpująco przeszukać w ograniczonym czasie? Zobacz post na blogu gościa Escardo na blogu Andreja Bauera, na przykład „Pozornie niemożliwe programy funkcjonalne” .

Twierdzenie o rekurencji z pewnością wydaje się sprzeczne z intuicją za pierwszym razem, gdy je widzisz. Zasadniczo mówi, że opisując Maszynę Turinga, możesz założyć, że ma ona dostęp do własnego opisu. Innymi słowy, mogę budować maszyny Turinga, takie jak:

TM M akceptuje n iff n jest wielokrotnością liczby pojawień się „1” w reprezentacji ciągu M.

TM N przyjmuje liczbę n i wysyła n kopii siebie.

Zauważ, że „reprezentacja ciągu” tutaj nie odnosi się do nieformalnego opisu tekstu, ale raczej do kodowania.

Udowodnienie wyników teorii informacji opartych na założeniach teorii złożoności to kolejny wynik sprzeczny z intuicją. Na przykład Bellare i in. w swoim artykule (Prawdziwa) złożoność wiedzy o zerowej statystyce konstruktywnie udowodniono, że zgodnie z założeniem certyfikowanego logarytmu dyskretnego każdy język, który przyjmuje rzetelną zerową wiedzę statystyczną, dopuszcza również wiedzę o zerowej statystyce.

Wynik był tak dziwny, że zaskoczył autorów. Wskazali ten fakt kilka razy; na przykład we wstępie:

Biorąc pod uwagę, że statystyczna wiedza zerowa jest pojęciem niezależnym obliczeniowo, jest nieco dziwne, że jej właściwości można udowodnić przy założeniu trudnej obliczeniowo.

PS: Silniejszy wynik został później bezwarunkowo udowodniony przez Okamoto ( O związkach między statystycznymi dowodami zerowej wiedzy ).

Opis niektórych terminów

Ponieważ powyższy wynik zawiera wiele kryptograficznego żargonu, staram się nieformalnie zdefiniować każdy termin.

1. $p$$p-1$
2. Zero wiedzy : protokół, który nie daje wiedzy stronom związanym z czasem wielomianowym.
3. Statystyczna wiedza zerowa: protokół, który nie dostarcza informacji, nawet podmiotom niepowiązanym obliczeniowo, z wyjątkiem mało prawdopodobnego prawdopodobieństwa.
4. Szczera weryfikacja zerowa wiedza: protokół, który nie daje wiedzy stronom związanym czasem wielomianowym, jeśli działają one zgodnie z protokołem.

Co powiesz na fakt, że obliczanie na stałe jest # P-Complete, ale wyznacznikiem obliczeń - sposób, w jaki dziwniejsze operacje są w klasie NC?

Wydaje się to dość dziwne - nie musiało tak być (a może tak ;-))

Problem programowania liniowego można rozwiązać w (słabo) czasie wielomianowym. To wydaje się bardzo zaskakujące: dlaczego mielibyśmy znaleźć jeden spośród wykładniczej liczby wierzchołków wielowymiarowego polytopa? Dlaczego mielibyśmy rozwiązać problem, który jest tak absurdalnie ekspresyjny?

Nie wspominając już o wszystkich programach liniowych wielkości wykładniczej, które możemy rozwiązać za pomocą metody elipsoidy i wyroczni separacyjnych oraz innych metod (dodawanie zmiennych itp.). Na przykład zadziwiające jest to, że LP z wykładniczą liczbą zmiennych, takich jak relaksacja Karmakar-Karp z Pakowania bin, może być skutecznie przybliżone.

Ilekroć uczę automatów, zawsze pytam moich uczniów, czy nie dziwi ich, że niedeterminizm nie dodaje żadnej mocy automatom skończonym (tj. Że dla każdego NFA istnieje odpowiednik - być może znacznie większy - DFA). Około połowa klasy jest zaskoczona, więc proszę bardzo. [Sam straciłem „wyczucie” tego, co zaskakuje na poziomie wstępu.]

$R\neq RE$

Odkryłem, że Prosty kryptosystem z kluczem publicznym z podwójnym mechanizmem odszyfrowywania zapadni i jego aplikacjami jest paradoksalny, ponieważ jest to adaptacyjny wybrany bezpieczny schemat szyfrogramu, który jest homomorficzny.