Pytania otagowane jako big-picture

Znacznik dużego obrazu służy do „szerokiego, ogólnego widoku lub perspektywy problemu lub problemu”.

10
Prawdziwe komputery mają tylko skończoną liczbę stanów, więc jakie jest znaczenie maszyn Turinga dla prawdziwych komputerów?
Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty. Dlaczego informatycy teoretyczni używają maszyn Turinga (i innych równoważnych modeli) do badania komputerów? Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu do prawdziwych komputerów? Dlaczego model automatów skończonych nie wystarczy?
4
Dlaczego nie udało nam się opracować jednolitej teorii złożoności obliczeń rozproszonych?
Dziedzina przetwarzania rozproszonego okazała się bardzo krótka w opracowaniu jednej teorii matematycznej opisującej algorytmy rozproszone. Istnieje kilka „modeli” i struktur obliczeń rozproszonych, które po prostu nie są ze sobą kompatybilne. Sama eksplozja różnych właściwości czasowych (asynchronia, synchronizacja, synchronizacja częściowa), różne prymitywy komunikacyjne (przekazywanie wiadomości w stosunku do pamięci współużytkowanej, transmisja …
2
Program GCT Mulmuleya
Czasami twierdzi się, że teoria złożoności geometrycznej Ketana Mulmuleya jest jedynym wiarygodnym programem do rozstrzygania otwartych pytań teorii złożoności, takich jak pytanie P vs. NP. Było wiele pozytywnych komentarzy od słynnych teoretyków złożoności na temat programu. Według Mulmuleya osiągnięcie pożądanych rezultatów zajmie dużo czasu. Wejście w ten obszar nie jest …
2
Klasy złożoności semantycznej a składniowej
W swojej książce „Computational Complexity” Papadimitriou pisze: RP jest w pewnym sensie nową i niezwykłą klasą złożoności. Żadna żadna wieloznacznie niedeterministyczna maszyna Turinga nie może być podstawą do zdefiniowania języka w RP. Aby maszyna N mogła zdefiniować język w RP , musi mieć niezwykłą właściwość, która na wszystkich wejściach albo …
5
Nieuzasadniona moc niejednolitości
Z punktu widzenia zdrowego rozsądku łatwo jest uwierzyć, że dodanie niedeterminizmu do znacznie rozszerza jego moc, tj. jest znacznie większy niż . W końcu niedeterminizm umożliwia wykładniczy paralelizm, który niewątpliwie wydaje się bardzo silny. PP\mathsf{P}NPNP\mathsf{NP}PP\mathsf{P} Z drugiej strony, jeśli po prostu dodamy niejednolitość do , uzyskując , wówczas intuicja jest …
7
Soczewka algorytmiczna w naukach społecznych
Patrzenie na pytania przez obiektyw algorytmiczny (tj. Z punktu widzenia algorytmu lub złożoności) stało się przydatne w dyscyplinach poza „standardową dziedziną” informatyki. W szczególności CS wywarł wpływ na biologię poprzez biologię obliczeniową, na fizykę poprzez kwantowe przetwarzanie informacji, a AI i teoria złożoności wydają się regularnie oddziaływać z neuronauką. Nauki …
11
Co to jest kwantowy model obliczeniowy?
Od czasu do czasu słyszałem, jak ludzie mówią o algorytmach kwantowych oraz o stanach i możliwości rozważenia wielu możliwości naraz, ale nigdy nie udało mi się przekonać kogoś do wyjaśnienia stojącego za tym modelu obliczeniowego. Żeby było jasne, nie pytam o to, jak fizycznie zbudowane są komputery kwantowe, ale raczej, …
7
Czy powinniśmy uznać
Wielu ekspertów uważa, że hipoteza jest prawdziwa i wykorzystuje ją w swoich wynikach. Obawiam się, że złożoność silnie zależy od hipotezy .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Więc moje pytanie brzmi: Dopóki hipoteza nie zostanie udowodniona, czy można / należy uznać ją za prawo natury, jak wskazano w cytacie ze Strassen? …
17
Przykłady, w których wgląd w geometrię był przydatny do rozwiązania czegoś całkowicie niegeometrycznego
Jedną z miłych rzeczy w ewolucji we wszechświecie o trzech wymiarach przestrzennych jest to, że rozwinęliśmy umiejętności rozwiązywania problemów dotyczące obiektów w przestrzeni. Tak więc na przykład możemy myśleć o tryplecie liczb jako o punkcie 3-d, a zatem obliczenia o tripletach liczb jako o obliczeniach o punktach w 3-d, które …
5
Ekologia i ewolucja poprzez soczewkę algorytmiczną
Badanie ekologii i ewolucji staje się coraz bardziej matematyczne, ale wydaje się, że większość narzędzi teoretycznych pochodzi z fizyki. Jednak w wielu przypadkach problemy mają bardzo dyskretny charakter (patrz na przykład SLBS00 ) i mogą skorzystać z perspektywy informatyki . Jednak wiem tylko o kilku poważnych wynikach TCS, które próbują …
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.