Pytania otagowane jako open-problem

Problemy, o których wiadomo, że są otwarte w literaturze, i każdy problem, który po postawieniu decyduje się być otwarty przez społeczność.

1
Na podstawie wykresu zdecyduj, czy jego łączność brzegowa wynosi co najmniej n / 2, czy nie
Rozdział 1 książki Metoda probabilistyczna autorstwa Alona i Spencera wymienia następujący problem: Biorąc pod uwagę wykres , zdecyduj, czy jego łączność brzegowa wynosi co najmniej czy nie.GGGn/2n/2n/2 Autor wspomina o istnieniu przez Matula algorytmu i ulepsza go do .O(n3)O(n3)O(n^3)O(n8/3logn)O(n8/3log⁡n)O(n^{8/3}\log n) Moje pytanie brzmi: jaki jest najbardziej znany czas wykonywania tego …
2
Lista zagadnień teoretycznych lub algebraicznych w różnych klasach złożoności
Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład, GCD w jest otwarty,N.do1NC1NC^1 faktoring w jest otwarty,P.PP obliczanie kohomologii snopów to -hard# P#P\#P , Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie jest jasne, na podstawie dyskusji na NP-zupełnym wariantu faktoringu. ),N.P.NPNP …
4
Problemy, o których wiadomo, że nie są kompletne z PSPACE
Jakie są problemy z następującymi właściwościami: 1) są ograniczeniem (prawdopodobnie dobrze znanych) problemów, które są kompletne z PSPACE; 2) wersje ograniczone są w PSPACE, ale jest to otwarty problem, jeśli są one kompletne (lub nawet jeśli są trudne w wersji NP). Cztery przykłady z „puzzli i C.”: Złożoność 1x1 Godziny …
2
Czy
Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jeśli jest językiem PSPACE uzupełniania, P = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jeśli jest deterministyczną wyrocznią wielomianową, P B ≠ N P B (przy założeniu P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP to klasa problemów decyzyjnych analogiczna dla # P i P ⊆ P P ⊆ P S P …
2
Ogromna współpraca online w celu rozwiązania otwartego problemu w informatyce teoretycznej
W projektach Polymath duża grupa pracuje nad otwartym problemem. Jakie problemy wydają się działać najlepiej w tych ramach? Czy są jacyś dobrzy kandydaci na projekt polimorficzny w informatyce teoretycznej? Czy są jakieś przeszkody, które sprawiają, że projekty Polymath rzadziej odnoszą sukcesy w informatyce teoretycznej w porównaniu z innymi dziedzinami matematyki?
1
Czy Memcomputing naprawdę rozwiązuje problem NP-zupełny?
Zetknąłem się z artykułem opublikowanym w Science „Memcomputing NP-zupełne problemy w czasie wielomianowym z wykorzystaniem zasobów wielomianowych i stanów zbiorowych” , co czyni niektóre dość zaskakujące twierdzenia. Memcomputing to nowy nieturingowy paradygmat obliczeń, który wykorzystuje interakcyjne komórki pamięci (w skrócie memprocessors) do przechowywania i przetwarzania informacji na tej samej platformie …
1
Na
Wiemy to L⊆NL⊆P⊆NPL⊆NL⊆P⊆NP\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}. Z twierdzenia SavitchaNL⊆L2NL⊆L2\mathcal{N\!L}\subseteq\mathcal{L}^2, a od Space Hierarchy Teorem, L≠L2L≠L2\mathcal{L}\neq\mathcal{L}^2. Ponieważ nie wiemy, czyL≠PL≠P\mathcal L\neq\mathcal Pnie wiemy czy L2⊆PL2⊆P\mathcal L^2\subseteq\mathcal Pczy wiemy o tym L2⊈PL2⊈P\mathcal L^2\not\subseteq\mathcal P? Czy ktoś próbował udowodnić, że ? Jakie są najnowsze wyniki lub wysiłki w ten sposób? Próbowałem napisać ankietę na ten …
1
Nauka z (podpisanymi) błędami
Background––––––––––––––Background_\underline{\bf Background} W 2005 r. Regev [1] wprowadził problem uczenia się z błędami (LWE), uogólnienie problemu parzystości uczenia się z błędem. Założenie o twardości tego problemu dla niektórych wyborów parametrów leży obecnie u podstaw dowodów bezpieczeństwa dla wielu kryptosystemów post kwantowych w dziedzinie kryptografii opartej na sieci. „Kanoniczne” wersje LWE …
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.