Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

2
Czy możemy skonstruować redukcję Karp z redukcji Cooka między problemami NP?
Mieliśmy kilka pytań na temat relacji redukcji Cooka i Karp . Oczywiste jest, że redukcje Cooka (redukcje Turinga w czasie wielomianowym) nie definiują tego samego pojęcia kompletności NP jak redukcje Karp (redukcje w postaci wielomianu w jednym czasie), które są zwykle stosowane. W szczególności redukcje Cooka nie mogą oddzielić NP …
3
Po co używać języków w teorii złożoności
Właśnie zaczynam wchodzić w teorię obliczeń, która bada, co można obliczyć, jak szybko, z wykorzystaniem ilości pamięci iz jakim modelem obliczeniowym. Mam dość podstawowe pytanie, ale naprawdę mam nadzieję, że niektórzy z was pomogą mi zrozumieć koncepcję: Dlaczego wszystko koncentruje się wokół pojęcia i definicji JĘZYKÓW (tj. Języków zwykłych i …
1
Intuicja stojąca za relatywizacją
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka kolejnych zdań to pytania, a moje przemyślenia …
1
Matematyka dla TCS major
Szukam specjalizacji z informatyki teoretycznej; szczególnie interesuje mnie teoria złożoności i teoria automatów probabilistycznych. Kiedy kończę rok, jakie zaawansowane kursy matematyczne (jak na przykład teoria Galois lub analiza harmoniczna) są przydatne do przejęcia kolejnych dwóch semestrów? Dlaczego?
1
Wykazać, że funkcja boolowska obliczalna w T (n) przez maszynę RAM jest w DTIME (T (n) ^ 2)
Pytanie brzmi: ćwiczenie 1.9 z książki Arory-Barak Computational Complexity - A Modern Approach : Zdefiniuj maszynę RAM Turing jako maszynę Turinga, która ma pamięć o dostępie swobodnym. Sformalizujemy to w następujący sposób: Maszyna ma nieskończoną tablicę A, która jest inicjalizowana dla wszystkich spacji. Uzyskuje dostęp do tej tablicy w następujący …
2
NP-Kompletność problemu kolorowania wykresu
Alternatywne sformułowanie Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do NP. Alternatywne sformułowanie wykorzystuje rozłączny zestaw przychodzących i wychodzących węzłów, co upraszcza definicję problemu. Biorąc pod uwagę …
1
Jak udowodnić, że ograniczona wersja 3SAT, w której dosłowność nie może wystąpić więcej niż jeden raz, można rozwiązać w czasie wielomianowym?
Próbuję wypracować zadanie (zaczerpnięte z książki Algorytmy - S. Dasgupta, CH Papadimitriou i UV Vazirani , Rozdział 8, problem 8.6a), i parafrazuję to, co mówi: Biorąc pod uwagę, że 3SAT pozostaje NP-kompletny, nawet jeśli ogranicza się do formuł, w których każdy literał pojawia się co najwyżej dwa razy, pokaż, że …
3
Czy łączenie wysp z pontonami NP-zupełne?
Mam w głowie problem, myślę, że jest to problem NPC, ale nie wiem, jak to udowodnić. Oto problem: Istnieje k wyspy w bardzo dużym jeziorem, a tam są n kształcie wachlarza pontony. Te pontony są tego samego rozmiaru, ale mają różne początkowe kierunki i znajdują się w różnych oryginalnych pozycjach …
1
Dlaczego P i P / poli nie są takie same?
Definicja P jest językiem, o którym decyduje algorytm wielomianowy. Definicja P / poly może być rozumiana jako język, który może być ustalony przez obwód wielkości wielomianowej (patrz http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Dlaczego więc nie można symulować obwodu wielomianowego w czasie wielomianowym?
2
Złożoność znalezienia związku z kompresją ścieżki, bez rangi
Wikipedia twierdzi, że związek według rangi bez kompresji ścieżki daje zamortyzowaną złożoność czasu O(logn)O(log⁡n)O(\log n)oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową O(α(n))O(α(n))O(\alpha(n)) (gdzie αα\alphajest odwrotnością funkcji Ackermana). Jednak nie wspomina o czasie działania kompresji ścieżki bez rangi związkowej, co zwykle realizuję sam. Jaka …
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.