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ść.

2
Przybliżenie rangi znaku macierzy
Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.AijBij>0AijBij>0A_{ij}B_{ij}>0i,ji,ji,j Moje pytanie brzmi: czy są jakieś znane algorytmy …
1
Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski , …
2
Numer podziału protokołu i deterministyczna złożoność komunikacji
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997) daje cc(R)/3≤log2(pp(R))≤cc(R).cc(R)/3≤log2⁡(pp(R))≤cc(R).cc(R)/3 \le \log_2(pp(R)) \le cc(R). Jeśli chodzi o drugą nierówność, łatwo jest podać …
1
Złożoność obliczania najkrótszych ścieżek w płaszczyźnie z wielokątnymi przeszkodami
Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że współrzędne s i t oraz współrzędne każdego wierzchołka …
2
Algorytmy aproksymacji czasu wielomianowego do planowania maszyny: ile pozostało otwartych problemów?
W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc świetnie i przydatne, gdyby każdy z nas mógł sporządzić …
4
Pozytywne uporządkowanie topologiczne, weź 3
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP również by go rozwiązał. Edycja: Laszlo Vegh …
2
Jaki jest „najbliższy” problem hipotezy Collatza, który został pomyślnie rozwiązany?
Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej …
2
Kompromis czasoprzestrzenny i najlepszy algorytm
Rozważmy język taki jak:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) i tak L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Innymi słowy, najszybsza maszyna oblicza L w czasie O ( f ( n ) ), a najbardziej wydajna pod względem przestrzeni maszyna M ' oblicza L , używając przestrzeni O ( g ( n …
2
Optymalny algorytm znajdowania obwodu rzadkiego wykresu?
Zastanawiam się, jak znaleźć obwód rzadkiego niekierowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy w , to znajdę obwód …
2
Rzutna płaszczyzna zamówienia 12
Cel : ustalenie przypuszczenia, że ​​nie ma rzutowej płaszczyzny rzędu 12. W 1989 r., Korzystając z wyszukiwania komputerowego na kredce, Lam udowodnił, że nie istnieje rzutowa płaszczyzna rzędu 10. Teraz, gdy Boski numer Kostki Rubika został ustalony po zaledwie kilku tygodniach masowych poszukiwań brutalnej siły (plus sprytnej matematyki symetrii), wydaje …
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.