Pytania otagowane jako cc.complexity-theory

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

2
„Klasa Steve'a”: pochodzenie SC
„Wiemy”, że nazwano na cześć Steve'a Cooka, a nazywa się Nick Pippenger. Jeśli się nie mylę, Steve Cook nazwał NC na cześć Nicka Pippengera i powiedziano mi, że jest też odwrotnie. Nie znalazłem jednak żadnego dowodu na ten ostatni fakt ani w pracy Steve'a Cooka na temat DCFL, ani w …
5
Nieuzasadniona moc niejednolitości
Z punktu widzenia zdrowego rozsądku łatwo jest uwierzyć, że dodanie niedeterminizmu do znacznie rozszerza jego moc, tj. jest znacznie większy niż . W końcu niedeterminizm umożliwia wykładniczy paralelizm, który niewątpliwie wydaje się bardzo silny. PP\mathsf{P}NPNP\mathsf{NP}PP\mathsf{P} Z drugiej strony, jeśli po prostu dodamy niejednolitość do , uzyskując , wówczas intuicja jest …
4
Zgodność między klasami złożoności a logiką
Raz wziąłem klasę na temat obliczalności i logiki. Materiał zawiera korelację między klasami złożoności / obliczalności (R, RE, co-RE, P, NP, Logspace, ...) i Logiką (rachunek predykatów, logika pierwszego rzędu, ...). Korelacja obejmowała kilka wyników w jednym polu, które zostały uzyskane przy użyciu technik z drugiego pola. Przypuszczano, że P! …
3
złożoność największego wspólnego dzielnika (gcd)
Rozważ następujący problem zliczania (lub związany z tym problem decyzyjny): Biorąc pod uwagę dwie dodatnie liczby całkowite zakodowane w systemie binarnym, oblicz ich największy wspólny dzielnik (gcd). Jaka jest najmniejsza klasa złożoności, w której występuje ten problem? Czy możesz podać referencje? W tym pytaniu nie interesują mnie przede wszystkim asymptotyczne …
2
NTIME (n ^ k) ≠ DTIME (n ^ k)?
W „O determinizmie kontra niedeterminizm i pokrewnych problemach” (Proc. IEEE FOCS, strony 429–438, 1983) Paul, Pippenger, Szemerédi i Trotter udowodnili, że . N T I M E ( n ) ≠ D T I M E ( n )NTIME(n)≠DTIME(n)\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n) Odpowiada to na moje pytanie przy k = 1. Czy coś …
2
Konsekwencje
Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory: Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym. „Magia kwantowa nie wystarczy” (Bennett i in. 1997): jeśli odrzucisz strukturę problemu i po prostu weźmiesz …
1
vs?
Centralnym problemem teorii złożoności jest zapewne vs .P.PPN.P.NPNP Ponieważ natura jest kwantowa, bardziej naturalne wydaje się rozważenie klas (tj. Problemów decyzyjnych rozwiązanych przez komputer kwantowy w czasie wielomianowym, z prawdopodobieństwem błędu co najwyżej 1/3 dla wszystkich instancji) i (ekwiwalent kwantowy z ) zamiast.B Q PBQPBQPQ MZAQMAQMAN.P.NPNP Moje pytania: 1) Czy …
2
Status światów Impagliazzo?
W 1995 r. Russell Impagliazzo zaproponował pięć światów złożoności: 1- Algorytmika: ze wszystkimi niesamowitymi konsekwencjami.P.= NP.P.=N.P.P=NP 2- Heuristica: problemy kompletne są trudne w najgorszym przypadku ( ), ale można je skutecznie rozwiązać w przeciętnym przypadku.N.P.N.P.NPP.≠ N.P.P.≠N.P.P \ne NP 3- Pessiland: Występują problemy z niepełną średniej wielkości przypadków , ale funkcje …
3
Założenia antologii złożoności
W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń, albo hipotezy losowej wyroczni. Najważniejszym i powszechnie uznawanym założeniem jest to, …
1
Czy LOGLOG = NLOGLOG?
Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez niedeterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). …
5
Języki programowania dla wydajnych obliczeń
Niemożliwe jest napisanie języka programowania, który zezwala wszystkim maszynom, które zatrzymują się na wszystkich wejściach i żadnych innych. Wydaje się jednak, że łatwo jest zdefiniować taki język programowania dla dowolnej standardowej klasy złożoności. W szczególności możemy zdefiniować język, w którym możemy wyrazić wszystkie wydajne obliczenia i tylko wydajne obliczenia. Na …
5
Dowód, że PPAD jest trudny?
Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że ​​klasa PPAD jest trudna do rozwiązania? Gdyby istniał algorytm …
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.