Pytania otagowane jako cc.complexity-theory

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

3
Dodawanie liczb całkowitych reprezentowanych przez ich faktoryzację jest tak trudne, jak faktoring? Wniosek o referencję
Szukam odwołania do następującego wyniku: Dodanie dwóch liczb całkowitych do reprezentacji faktoryzowanej jest tak trudne, jak dodanie dwóch liczb całkowitych do zwykłej reprezentacji binarnej. (Jestem prawie pewien, że tam jest, ponieważ zastanawiałem się nad tym, a potem byłem podekscytowany, gdy w końcu zobaczyłem to w druku). Problemem jest „dodanie dwóch …
2
Zależność między trudnością rozpoznawania klasy grafowej a zakazaną charakterystyką subgrafu
Rozważam klasy grafów, które można scharakteryzować za pomocą zabronionych subgrafów. Jeśli klasa grafów ma skończony zestaw zabronionych podgraphów, wówczas istnieje trywialny algorytm wielomianowego rozpoznawania czasu (można po prostu użyć brutalnej siły). Ale nieskończona rodzina zakazanych subgraphów nie oznacza twardości: istnieją pewne klasy z nieskończoną listą zakazanych subgrafów, tak że rozpoznanie …
1
Czy twardość NP oznacza twardość P?
Jeśli problem jest trudny dla NP (przy użyciu wielomianowych redukcji czasu), czy to oznacza, że ​​jest trudny dla P (przy użyciu przestrzeni dziennika lub redukcji NC)? Wydaje się intuicyjne, że jeśli jest tak trudny jak jakikolwiek problem w NP, powinien być tak trudny jak jakikolwiek problem w P, ale nie …
1
W jaki sposób papier BosonSampling unika łatwych klas złożonych matryc?
W złożoności obliczeniowej optyki liniowej ( ECCC TR10-170 ) Scott Aaronson i Alex Arkhipov twierdzą, że jeśli komputery kwantowe mogą być skutecznie symulowane przez klasyczne komputery, hierarchia wielomianowa upadnie na trzeci poziom. Problemem motywującym jest próbkowanie z rozkładu określonego przez sieć liniowo-optyczną; rozkład ten można wyrazić jako stały dla określonej …
1
Zagadnienia energetyczne dotyczące obliczeń
Aby sprawdzić moje zrozumienie, chciałbym podzielić się przemyśleniami na temat wymagań energetycznych obliczeń. Jest to kontynuacja mojego poprzedniego pytania i może być związana z pytaniem Vinaya dotyczącym praw ochrony . Przyszło mi do głowy, że z termodynamicznego punktu widzenia prowadzenie obliczeń można w pewnym stopniu uznać za analogiczne do przemieszczania …
1
Ile mocy obliczeniowej mieści się w centymetr sześcienny?
To pytanie stanowi odpowiedź na pytanie o algorytmy DNA zadane przez Aaditę Mehrę . W komentarzach Joe Fitzsimmons powiedział częściowo: Promień układu musi być skalowany proporcjonalnie do masy, aby tego uniknąć. Moc obliczeniowa jest skalowana co najwyżej liniowo w masie. Zatem twoja wykładnicza ilość maszyn ma wykładniczy promień. Ponieważ nie …
2
Multiplikatywna wersja 3-SUM
Co wiadomo na temat złożoności czasowej następującego problemu, który nazywamy 3-MUL? Biorąc pod uwagę zestaw z liczb całkowitych, czy są elementami taki sposób, że ?SSSnnna,b,c∈Sa,b,c∈Sa,b,c\in Sab=cab=cab=c Ten problem jest podobny do problemu 3-SUM, który pyta, czy istnieją trzy elementy tak, że (lub równoważnie ). Przypuszcza się, że 3-SUM wymaga czasu …
2
Czy „teoria złożoności eksperymentalnej” jest używana do rozwiązywania otwartych problemów?
Scott Aaronson zaproponował interesujące wyzwanie : czy możemy dziś wykorzystać superkomputery, aby pomóc rozwiązać problemy z CS w taki sam sposób, w jaki fizycy używają zderzaczy dużych cząstek? Mówiąc konkretniej, moja propozycja polega na poświęceniu części światowej mocy obliczeniowej na całkowitą próbę odpowiedzi na następujące pytania: czy obliczenie stałej macierzy …
2
W jaki sposób podejście geometryczne Mulmuleya-Sohoniego do wytwarzania dolnych granic unika tworzenia naturalnych dowodów (w sensie Razborowa-Rudicha)?
Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód występujących w pytaniu P / poli kontra NP (brak relatywizacji, brak algebrazowania, prawdopodobnie …
1
Złożoność problemu macierzowego
Następujący problem pojawił się ostatnio w moich badaniach. Nie będąc ekspertem od zagadnień algorytmicznych, obszernie poszukiwałem odpowiednich problemów, które można by zmniejszyć. Nie rozumiem, jak działałby 3SAT i chociaż ZOE jest podobny w duchu, redukcja nie jest oczywista. Inną możliwością byłaby egzystencjalna teoria rzeczywistości. To też nie wydaje się pasować, …
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.