Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Czy wszystkie klasy złożoności mają charakterystykę języka liścia?
Języki liścia są pięknym sposobem na jednolite zdefiniowanie wielu klas złożoności. Większość klas złożoności jest zwykle określana przez model obliczeniowy (np. Deterministyczna / losowa TM) i związany z zasobami (czas dziennika, przestrzeń wielopunktowa itp.). Jednak w sformułowaniu języka liścia istnieje tylko jeden model obliczeń, a klasa jest określona przez podanie …
2
normalne zachowanie maszyn Turinga
Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.ℓpℓp\ell_p Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem wprowadzającym jest praca Fortnowa, której link zamieścił tutaj Joshua Grochow …
3
Czy możliwe są rekurencyjne formy wypowiedzi Godela?
Samoreferencyjność problemu P / NP była czasem podkreślana jako bariera dla jego rozwiązania, patrz na przykład artykuł Scotta Aaronsona, czy P vs. NP jest formalnie niezależny ? Jednym z wielu możliwych rozwiązań P / NP byłby dowód, że problem jest formalnie niezależny od ZFC lub prawdziwy, ale niemożliwy do udowodnienia. …
3
kosmiczne bazy TM i wyrocznie
Zasadniczo taśma zapytania dla wyroczni liczy się do złożoności przestrzennej bazy TM. Wydaje się jednak prawdopodobne, aby zezwolić na taśmę Oracle tylko do zapisu (na przykład w przypadku redukcji przestrzeni L). Czy taka konstrukcja jest przydatna? Czy przynosi jakieś absurdalne wyniki?
3
NP kompletne problemy graficzne na temat właściwości strukturalnych
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie N.P.NP\mathcal{NP} -complete.For jakiegoś powodu mam problemy ze znalezieniem nawet …
3
Obliczanie liczb rzeczywistych: zmiennoprzecinkowy vs TTE vs teoria domen vs itd
Obecnie obliczanie liczb rzeczywistych w najpopularniejszych językach jest nadal wykonywane za pomocą operacji zmiennoprzecinkowych. Z drugiej strony, teorie takie jak efektywność typu drugiego (TTE) i teoria domen od dawna obiecują dokładne obliczenie rzeczywistych liczb. Najwyraźniej problem precyzji zmiennoprzecinkowej nie zmniejszył się, więc dlaczego te teorie nie stały się bardziej popularne …
2
Argumenty za / przeciw hipotezie Kołmogorowa o złożoności obwodu P.
Według (niezweryfikowanego) rachunku historycznego Kołmogorow uważał, że każdy język w ma złożoność obwodów liniowych. (Zobacz wcześniejsze pytanie Hipoteza Kołmogorowa, że ma obwody o rozmiarach liniowych .) Zauważ, że implikuje .PP\mathsf{P}PPPP≠NPP≠NP\mathsf{P}\neq \mathsf{NP} Jednak przypuszczenie Kołmogorowa może się nie powieść. Na przykład Ryan Williams pisze w niedawnym artykule: „Przypuszczenie byłoby zaskakujące, jeśli …
2
Czy problem zestawu wierzchołków sprzężenia zwrotnego można rozwiązać w czasie wielomianowym dla wykresów ograniczonych do 3 stopni?
Sprzężenie zwrotne Zestaw wierzchołków jest NP-kompletny dla ogólnych wykresów. Wiadomo, że jest NP-kompletny dla wykresów ograniczonych do stopnia 8 ze względu na redukcję z pokrycia wierzchołków. Artykuł w Wikipedii mówi, że jest on rozwiązany w czasie wielozakresowym dla grafów związanych ze stopniem 3 i jest NP-kompletny dla grafów związanych ze …
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.