Teoretyczne informatyka

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

2
Czy każde wyzwanie obliczeniowe można przekształcić w proof-of-work?
Pozornie bezcelowość wydobywania kryptowalut wywołała pytanie o przydatne alternatywy, zobacz te pytania na Bitcoin , CST , MO . Zastanawiam się, czy istnieje algorytm, który może przekonwertować praktycznie każde wyzwanie obliczeniowe doC\mathcal C (którego rozwiązanie można skutecznie zweryfikować) na inne takie wyzwanie Ψ ( C)Ψ(C)\Psi(\mathcal C) (które jest używane do …
5
Łatwe problemy z trudnymi do zliczenia wersjami
Wikipedia podaje przykłady problemów, w których liczenie wersji jest trudne, natomiast wersja decyzyjna jest łatwa. Niektóre z nich liczą doskonałe dopasowania, licząc liczbę rozwiązań SAT i liczbę sortowań topologicznych.222 Czy są jeszcze jakieś inne ważne klasy (powiedzmy przykłady z sieci, drzew, teorii liczb i tak dalej)? Czy istnieje kompendium takich …
3
Kto wprowadził niedeterministyczne obliczenia?
Mam dwa historyczne pytania: Kto pierwszy opisał obliczenia niedeterministyczne? Wiem, że Cook opisał problemy z NP-zupełnością i że Edmonds zaproponował, że algorytmy P są algorytmami „wydajnymi” lub „dobrymi”. Przeszukałem ten artykuł w Wikipedii i odszukałem „O złożoności obliczeniowej algorytmów”, ale nie mogłem znaleźć żadnego odniesienia do pierwszego omówienia obliczeń niedeterministycznych. …
2
Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować
Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować ? Algorytm niedeterministyczny czasu wielomianowego natychmiast implikowałby to, ponieważ ale nikt nie wierzy, że . Jeśli zrobiłem algebrę w prawo (patrz poniżej), twierdzenie o hierarchii czasu nadal dawałoby implikację dla czasów uruchamiania dla dowolnego wielobiegunowego , ale dla wszystko, co …
3
Ile czasu rozpoznaje palindromy w przestrzeni logarytmicznej?
Dobrze wiadomo, że palindromy można rozpoznać w czasie liniowym na maszynach Turinga z taśmami, ale nie na maszynach Turinga z pojedynczą taśmą (w takim przypadku potrzebny czas jest kwadratowy). Algorytm czasu liniowego wykorzystuje kopię danych wejściowych, a zatem wykorzystuje również przestrzeń liniową.222 Czy potrafimy rozpoznać palindromy w czasie liniowym wielowarstwowej …
1
Konsekwencje ?
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq \mathsf{P}/\text{poly} Twierdzenie Adlemana jest czasem nazywane „protoplastą argumentów derandomizacji”. Uważa się, że podlega derandomizacji, podczas gdy nie ma dowodów na to, że „kwantowość” mogłaby …
2
Relacja między
Niech będzie klasą wszystkich zwykłych języków.REGREG\mathsf{REG} Znane jest i . Ale czy istnieje jakaś charakterystyka języków w \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}REG⊄AC0REG⊄AC0\mathsf{REG} \not\subset \mathsf{AC}^0AC0∩REGAC0∩REG\mathsf{AC}^0 \cap \mathsf{REG}
1
Minimalne ukończenie wykresu nieparzystych cykli nieparzystych: czy jest trudne NP?
W moich badaniach pojawił się ostatnio następujący interesujący problem: INSTANCJA: Wykres .G ( V, E)G(V,E)G(V, E) ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda krawędź w jest zawarta w bezciężkim cyklu nieparzystym.mi′E′E'miEEsol′( V, E′)G′(V,E′)G'(V, E')sol′G′G' POMIAR: …
2
Czy istnieje typowany rachunek lambda, który jest spójny i kompletny Turinga?
Czy istnieje typowany rachunek lambda, w którym odpowiednia logika w korespondencji Curry-Howarda jest spójna i gdzie istnieją możliwe do wpisania wyrażenia lambda dla każdej funkcji obliczeniowej? Jest to wprawdzie pytanie nieprecyzyjne, pozbawione precyzyjnej definicji „typowanego rachunku lambda”. Zastanawiam się, czy istnieją (a) znane przykłady tego, lub (b) znane dowody niemożności …
4
Do czego służą wykresy nieskończone?
Właśnie przeczytałem na niemieckiej Wikipedii, że nieskończony wykres to wykres z nieskończoną liczbą węzłów lub nieskończoną liczbą krawędzi. Znam tylko aplikacje i algorytmy dla grafów skończonych. Do czego służą wykresy nieskończone? Jakie są ich zastosowania? Nie wyobrażam sobie algorytmów, które działałyby na nieskończonych grafach, ponieważ nie można przechowywać nieskończonego wykresu. …
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.