Pytania otagowane jako cc.complexity-theory

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

1
Jaka jest złożoność tego problemu obejmującego?
Edycja: Najpierw źle sformułowałem moje ograniczenie (2), teraz jest poprawione. Dodałem także więcej informacji i przykładów. Z niektórymi kolegami, badającymi inne pytania algorytmiczne, byliśmy w stanie zredukować nasz problem do następującego interesującego problemu, ale nie byliśmy w stanie rozwiązać problemu jego złożoności. Problem jest następujący. Przykład: całkowita oznacza liczbę całkowitą …
1
Co jest
Jest to związane z pytaniem Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany? Niektóre naturalne problemy (-kompletne) mają świadków o długości liniowej: zadowalające przypisanie dla , ciąg wierzchołków dla itp.NPNP\mathsf{NP}SATSATSATHAMPATHHAMPATHHAMPATH Rozważ klasę złożoności „ ograniczoną do świadków o długości liniowej”. Formalna definicja tej klasy złożoności, nazwij ją …
3
Twardość aproksymacji - błąd addytywny
Istnieje bogata literatura i co najmniej jedna bardzo dobra książka określająca znaną twardość wyników przybliżenia dla problemów trudnych dla NP w kontekście błędu multiplikatywnego (np. 2-przybliżenie dla pokrywy wierzchołków jest optymalne przy założeniu UGC). Obejmuje to również dobrze zrozumiałe klasy złożoności aproksymacji, takie jak APX, PTAS i tak dalej. Co …
6
Czy występują problemy NP-zupełne z rozwiązaniami wielomianowego oczekiwanego czasu?
Czy są jakieś problemy z NP-zupełnością, dla których znany jest algorytm, że oczekiwany czas działania jest wielomianowy (dla pewnego rozsądnego rozkładu między instancjami)? Jeśli nie, to czy istnieją problemy, dla których ustalono istnienie takiego algorytmu? Czy istnienie takiego algorytmu sugeruje istnienie deterministycznego wielomianowego algorytmu czasu?
3
Jakie są relacje między tymi hipotezami w teorii drobnoziarnistej złożoności?
Teoria złożoności, poprzez takie koncepcje jak kompletność NP, rozróżnia problemy obliczeniowe, które mają względnie skuteczne rozwiązania, i te, które są trudne do rozwiązania. Złożoność „drobnoziarnista” ma na celu dopracowanie tego jakościowego rozróżnienia w ilościowy przewodnik co do dokładnego czasu potrzebnego na rozwiązanie problemów. Więcej informacji można znaleźć tutaj: http://simons.berkeley.edu/programs/complexity2015 Oto …
2
Rozpoznawanie węzłów jako dowód pracy
Obecnie bitcoin ma system proof of work (PoW) wykorzystujący SHA256. Inne funkcje skrótu wykorzystują wykresy wykorzystania systemu dowodu pracy, częściowe odwrócenie funkcji skrótu. Czy można zastosować problem decyzyjny w teorii węzłów, taki jak rozpoznawanie węzłów, i uczynić z niego funkcję dowodu pracy? Czy ktoś już to zrobił? Ponadto, kiedy będziemy …
3
Reprezentowanie OR za pomocą wielomianów
Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .nnnx1,…,xnx1,…,xnx_1,\ldots, x_np(x1,…,xn)p(x1,…,xn)p(x_1,\ldots,x_n)p(x1,…,xn)=1−∏ni=1(1−xi)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)nnn Ale jak mogę pokazać, co wydaje się oczywiste, że jeśli jest wielomianem, który dokładnie reprezentuje funkcję OR (więc ), a następnie ?∀ x ∈ …
5
Problemy z EXPSPACE
Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników. Jak dotąd je znalazłem i mam problem z rozwinięciem listy: uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem. problemy związane z systemami dodawania wektorów nieobserwowalne gry (patrz na przykład ten …
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.