Pytania otagowane jako cc.complexity-theory

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

2
Funkcja boolowska, która nie jest stała w podprzestrzeniach afinicznych o wystarczająco dużym wymiarze
Interesuje mnie wyraźna funkcja boolowska fa:0 , 1n→0 , 1fa:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}z następującą właściwością: jeśli jest stałe w jakiejś podprzestrzeni afinicznejfafaf , wówczas wymiar tej podprzestrzeni wynosi o ( n ) .0 , 1n0,1n\\{0,1\\}^no ( n )o(n)o(n) Nie jest trudno wykazać, że funkcja symetryczna nie spełnia tej właściwości, …
1
Najbardziej znane wspólne pojemniki dla / przez NP i Parity-P?
Parzystość-P jest zbiorem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji). Zatem Parity-P jest w zasadzie PP „s karłowate młodsze rodzeństwo: podczas liczy PP czy liczba przyjmujących ścieżkach NP-maszyna jest większość, czy nie ( …
2
Dolne granice złożoności Gaussa
Określić Gaussa złożoność danego matrycy, tak aby minimalna ilość elementarnych wierszy i kolumn operacji wymaganych do matrycy w postaci górnej trójkątnej. Jest to wielkość od do (poprzez eliminację Gaussa). Pojęcie ma sens w każdej dziedzinie.n×nn×nn \times n000n2n2n^2 Ten problem z pewnością wydaje się bardzo podstawowy i musiał zostać zbadany. O …
3
Modele obliczeń ściśle między klasycznym a kwantowym pod względem złożoności zapytań
Powszechnie wiadomo, że komputery kwantowe są silniejsze niż ich klasyczne odpowiedniki pod względem złożoności zapytań . Czy istnieją inne modele (naturalne lub sztuczne), które są ściśle kwantowe i klasyczne pod względem złożoności zapytań? Separacja może być włączona specyficzne problemy: model X oblicza funkcję ze znacznie większą liczbą zapytań niż kwantowe, …
5
P z wyrocznią z faktoryzacji liczb całkowitych
Właśnie przeczytałem pytanie „ Czy rozkład liczb całkowitych jest problemem NP-zupełnym? ” ... więc postanowiłem poświęcić trochę mojej reputacji :-) zadając kolejne pytanie mając :QQQP(Q is trivial)≈1P(Q is trivial)≈1P(\text{Q is trivial}) \approx 1 Jeśli jest wyrocznią, która rozwiązuje faktoryzacji liczb całkowitych, co jest moc P A ? AAAPAPAP^A Myślę, że …
1
Jaka jest wyrocznia o minimalnej złożoności, która oddziela PSPACE od hierarchii wielomianowej?
tło Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Wiadomo nawet, że separacja dotyczy przypadkowej wyroczni. Nieformalnie można to interpretować w ten sposób, że istnieje wiele wyroczni, dla których i są osobne.P HPSPACEPSPACEPSPACEPHPHPH Pytanie Jak skomplikowane są te wyrocznie, …
3
Jak często występuje przejście fazowe w problemach z NP-zupełnym?
Powszechnie wiadomo, że wiele problemów z kompletnym NP wykazuje przejście fazowe. Interesuje mnie przejście fazowe w odniesieniu do ograniczenia w języku, a nie twardości danych wejściowych w stosunku do algorytmu. Aby pojęcie było jednoznaczne, formalnie zdefiniujmy go w następujący sposób. Język wykazuje przejście fazowe (w odniesieniu do powstrzymywania), jeśliLLL Istnieje …
2
Złożoność problemu przecięcia cosetów
Biorąc pod uwagę grupę symetrii i dwie podgrupy i , czy ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset O ile mi wiadomo, problem ten znany jest jako problem przecięcia cosetów. Zastanawiam się, jaka jest złożoność? W szczególności, czy wiadomo, że ten problem występuje w CoAM? Co więcej, jeśli jest ograniczone do abelowego, …
2
Minimalna skumulowana suma zestawu
Rozważ ten problem: biorąc pod uwagę listę zbiorów skończonych, znajdź porządek który minimalizuje .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Czy istnieją na to znane algorytmy? Jaka jest jego złożoność? Nie byłem jeszcze w stanie wymyślić wydajnego optymalnego algorytmu, ale nie …
1
Jakie mamy dowody na ?
Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie. Jakie mamy dowody na ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną ścieżkę akceptacji w instancjach „tak” i brak ścieżki akceptacji w instancjach „nie”.UPUP\mathsf{UP} Oczywiście , …
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.