Pytania otagowane jako np-complete

1
Domysł: Wszystkie języki FPT NP-complete mają stały parametr izomorficzny
Hipoteza Bermana – Hartmanisa: wszystkie języki NP-zupełne wyglądają podobnie, w tym sensie, że mogą być ze sobą powiązane przez wielomianowe izomorfizmy czasowe [1]. Interesuje mnie bardziej szczegółowa wersja „czasu wielomianowego”, to znaczy, jeśli zastosujemy sparametryzowane redukcje. Problem sparametryzowany to podzbiór , gdzie jest skończonym alfabetem, a to zbiór liczb nieujemnych. …
1
Naturalni kandydaci na NP-E i E-NP
Od wczesnych lat 70. wiadomo, że i nie są równe (ponieważ nie jest zamknięty w czasie wielomianowym wiele -jedna redukcja, w przeciwieństwie do ). O ile mi wiadomo, wciąż pozostaje otwarte, czy jedna klasa jest podzbiorem drugiej, czy też są nieporównywalne, co oznacza, że i są niepuste.NPNP{\bf NP}E=DTIME(2O(n))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)})EE{\bf E}NPNP{\bf …
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 …
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.