Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Jakiś szybki algorytm problemu z ustawieniem łuku zwrotnego przy minimalnych kosztach?
Na ukierunkowanym wykresie , F ⊂ E , jeśli G ∖ F jest DAG (ukierunkowany wykres acykliczny), F nazywa się zestawem łuku zwrotnego. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Jeżeli każda krawędź jest powiązana z wagą , problem z zestawem łukowym sprzężenia zwrotnego przy minimalnym koszcie polega na znalezieniu F takiej, że W …
3
Dwa warianty NP
Oto dwie odmiany definicji NP. (Prawie na pewno) definiują odrębne klasy złożoności, ale moje pytanie brzmi: czy istnieją naturalne przykłady problemów, które pasują do tych klas? (Mój próg, który jest tutaj naturalny, jest nieco niższy niż zwykle). Klasa 1 (nadklasa NP): problemy ze świadkami wielomianowymi, których weryfikacja wymaga czasu wielobiegunowego, …
7
Jak informatyka teoretyczna odnosi się do bezpieczeństwa?
Kiedy myślę o oprogramowaniu, które nie jest bezpieczne, myślę, że jest ono „zbyt przydatne” i może zostać wykorzystane przez napastnika. W pewnym sensie zabezpieczenie oprogramowania to proces zmniejszania jego użyteczności. W informatyce teoretycznej nie pracujesz w prawdziwym świecie. Czy są jakieś obawy związane z bezpieczeństwem podczas pracy z czystą teorią? …
7
Obliczenia kwantowe - postulaty QM
Właśnie zacząłem (niezależne) uczenie się ogólnie o obliczeniach kwantowych z książki Nielsen-Chuang. Chciałem zapytać, czy ktokolwiek mógłby spróbować znaleźć czas, aby pomóc mi w tym, co się dzieje z postulatem pomiaru mechaniki kwantowej. To znaczy, nie próbuję kwestionować postulatu; po prostu nie rozumiem, w jaki sposób wartość stanu układu po …
1
Jaki jest najtrudniejszy przykład problemu grupowego izomorfizmu?
Mówi się, że dwie grupy (G,⋅)(G,⋅)(G,\cdot) i (H,×)(H,×)(H, \times) są izomorficzne, jeśli istnieje homomorfizm od GGG do HHH który jest bijectywny. Problem z izomorfizmem grupowym jest następujący: biorąc pod uwagę dwie grupy, sprawdź, czy są izomorficzne, czy nie. Istnieją różne sposoby wprowadzania grupy, dwa najczęściej używane są przez tabelę Cayleya …
3
Równoważne sformułowanie teorii złożoności w rachunku Lambda?
W teorii złożoności definicja złożoności czasu i przestrzeni odnosi się do uniwersalnej maszyny Turinga: odpowiednio. liczba kroków przed zatrzymaniem i liczba dotkniętych komórek na taśmie. Biorąc pod uwagę tezę Kościoła-Turinga, powinno być możliwe zdefiniowanie złożoności również pod względem rachunku lambda. Moje intuicyjne założenie jest takie, że złożoność czasu może być …
2
Przykład czegoś innego dla ogólnych i losowych wyroczni?
Niech będzie ogólną wyrocznią w sensie kategorii Cohen / Baire. Niech będzie losową wyrocznią.GGGRRR Czy istnieją klasy złożoności A i B z lub na odwrót, AG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^RAG≠BGandAR=BR?AG≠BGandAR=BR?\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?} Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .
2
Czy sieci społecznościowe są zwykle dobrymi ekspansorami?
Interesują mnie kombinatoryczne właściwości sieci społecznościowych w postaci grafów. Ludzie patrzyli na takie rzeczy, jak rozkład stopni, współczynnik grupowania i ściśliwość tych wykresów. Jedno podstawowe pytanie brzmi: czy te wykresy są zazwyczaj dobrymi wykresami ekspanderów? Czy ktoś sprawdził, powiedzmy, lukę spektralną wykresu na Facebooku? Lub luka widmowa innych dużych sieci …
3
Co faktycznie powinien udowodnić dowód poprawności dla sprawdzającego typ?
Programuję od kilku lat, ale nie znam teoretycznej CS. Niedawno próbowałem uczyć się języków programowania, a w ramach tego sprawdzania i wnioskowania. Moje pytanie brzmi: jeśli spróbuję napisać program wnioskowania i sprawdzania języka programowania i chcę udowodnić, że mój program do sprawdzania typów działa, jaki dokładnie jest dowód, którego szukam? …
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.