Teoretyczne informatyka

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

1
Ważność potęgowania w wielomianowym skrócie czasu
Zadałem to pytanie 10 dni temu na cs.stackexchange tutaj, ale nie miałem żadnej odpowiedzi. W bardzo słynnego papieru (w środowisku sieciowym), Wang i Crowcroft przedstawić kilka -completeness wyniki obliczeń ścieżki pod kilkoma dodatkami / multyplikatywnych ograniczeń. Pierwszy problem jest następujący:NPNP\mathsf{NP} Biorąc pod uwagę ukierunkowany wykres i dwie miary wagi w …
3
Ilościowe formuły logiczne z logarytmicznymi przemianami
Badam problem, który jest trudny dla klasy skwantyfikowanych formuł boolowskich z logarytmiczną liczbą zmian kwantyfikatorów. Problem w tej klasie wyglądałby następująco: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalog⁡n−1,…xalog⁡n)F\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F Gdzie log n = N , a M jest wartością logiczną wzór …
2
(Jak) Czy możemy odkryć / przeanalizować problemy NP przy braku modelu obliczeniowego Turinga?
Z czysto abstrakcyjnego punktu widzenia rozumowania matematycznego / obliczeniowego (jak) można nawet odkryć lub wyjaśnić problemy takie jak 3-SAT, suma częściowa, podróżny sprzedawca itp.,? Czy bylibyśmy w stanie w jakikolwiek sensowny sposób uzasadnić je tylko z funkcjonalnego punktu widzenia? Czy to w ogóle możliwe? Zastanawiam się nad tym pytaniem wyłącznie …
3
Nieredukowalne języki
To niekoniecznie jest pytanie badawcze. Tylko pytanie z ciekawości: Próbuję zrozumieć, czy można zdefiniować języki „nieredukowalne”. Na pierwszy rzut oka nazywam język L „redukowalny”, jeśli można go zapisać jako z i , w przeciwnym razie nazywam język „nieredukowalny” . Czy to prawda:L=A⋅BL=A⋅BL = A \cdot BA∩B=∅A∩B=∅A \cap B = \emptyset|A|,|B|>1|A|,|B|>1|A|,|B|>1 …
1
Jak ustalić, czy dowód wymaga „technik wnioskowania wyższego rzędu”?
Pytanie: Załóżmy, że mam specyfikację problemu składającego się z aksjomatów i celu (tj. Powiązanym problemem dowodowym jest to, czy cel jest zadowalający, biorąc pod uwagę wszystkie aksjomaty). Załóżmy również, że problem nie zawiera żadnych niespójności / sprzeczności między aksjomatami. Czy istnieje sposób na wcześniejsze ustalenie (tj. Bez uprzedniego zbudowania pełnego …
3
Przykłady udanej derandomizacji z BPP na P.
Jakie są główne przykłady udanej derandomizacji lub przynajmniej postępów w wykazywaniu konkretnych dowodów w kierunku celu (a nie związku losowości z twardością)?P=BPPP=BPPP=BPP Jedyny przykład, jaki przychodzi mi na myśl, to deterministyczne badanie pierwotności wielomianów czasowych AKS (nawet w tym przypadku istniała metodologia zakładająca GRH). Więc jakie konkretne dowody na przykładzie …
1
Czy programowanie dynamiczne nigdy nie jest słabsze niż chciwy?
W złożoności obwodu mamy rozdzielenia mocy różnych modeli obwodów. W złożoności dowodu mamy rozróżnienia między mocami różnych systemów dowodu. Ale w algorytmie wciąż mamy tylko kilka różnic między potęgami paradygmatów algorytmicznych . Moje pytania poniżej mają na celu dotknięcie tego ostatniego problemu w dwóch paradygmatach: Chciwy i Programowanie dynamiczne. Mamy …
1
2FA złożoność stanu k-Clique?
W prostej formie: Można dwukierunkowa skończony automat rozpoznaje vvv wykresy -Vertex które zawierają trójkąt z o(v3)o(v3)o(v^3) stany? Detale Zainteresowania są tu vvv wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki {0,1,…,v−1}{0,1,…,v−1}\{0,1,\dots,v-1\} . Załóżmy, że (Mv)(Mv)(M_v) jest ciągiem dwukierunkowy automaty skończone (deterministyczny lub niedeterministyczny), tak że …
2
Biorąc pod uwagę 4-cyklowy wykres , czy możemy ustalić, czy ma on 3-cykl w czasie kwadratowym?
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O ( n2))O(n2))O(n^2) . Raphael Yuster, Uri Zwick: Znalezienie …
2
Co wiadomo o tym wariancie TSP?
To pytanie zostało wcześniej opublikowane w Computer Science Stack Exchange tutaj . Wyobraź sobie, że jesteś odnoszącym sukcesy podróżnym sprzedawcą z klientami w całym kraju. Aby przyspieszyć wysyłkę, opracowałeś flotę dronów jednorazowego użytku o efektywnym zasięgu 50 kilometrów. Dzięki tej innowacji zamiast podróżować do każdego miasta w celu dostarczenia towarów, …
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.