Pytania otagowane jako np

NP oznacza niedeterministyczny czas wielomianowy.

1
NP-Kompletność problemu decyzyjnego dla uogólnionego 15-puzzle
Interesuje mnie naturalne uogólnienie słynnej 15-puzzli , w których musisz przesuwać bloki, dopóki nie posortujesz wszystkich podanych liczb (zwykle jest przerwa 1 blok). Teraz uogólnieniem byłoby zwiększenie rozmiaru układanki z 15 do , gdzie jedno pole jest wolne. Stworzyłem małą ilustrację (przerywane strzałki pokazują dozwolone ruchy, a dolna konfiguracja pokazuje …
6
Naturalne problemy NP-zupełne z „dużymi” świadkami
Pytanie dotyczące teorii „ Co to jest NP ograniczony do świadków wielkości liniowej? ” Dotyczy klasy NP ograniczonej do świadków wielkości liniowej , aleO ( n )O(n)O(n) Czy istnieją naturalne problemy NP-zupełne, w których (tak) przypadki wielkości wymagają świadków o rozmiarze większym niż n ?nnnnnn Oczywiście możemy budować sztuczne problemy, …
3
Problem decyzyjny, o którym nie wiadomo, że występuje w PH, ale będzie w P, jeśli P = NP
Edycja : Jak Ravi Boppana słusznie wskazał w swojej odpowiedzi, a Scott Aaronson dodał również inny przykład w swojej odpowiedzi , odpowiedź na to pytanie okazała się „tak” w sposób, którego w ogóle się nie spodziewałam. Najpierw pomyślałem, że nie odpowiedzieli na pytanie, które chciałem zadać, ale po pewnym zastanowieniu …
2
Powody, by wierzyć
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 6 lat temu . Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do rozwiązania. (Shiva Kintali wymienił tutaj kilka …
7
Nietrywialne członkostwo w NP
Czy jest przykładem języka, który jest w NPNPNP , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku? Zamiast tego fakt, że język znajduje się w NPNPNP , można udowodnić, redukując go do innego języka w NPNPNP , gdzie powiązanie …
27 reductions  np 
2
Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi
Peter Shor pokazał, że dwa z najważniejszych problemów pośrednich NP, faktoring i dyskretny log, są w BQP. Natomiast najbardziej znany algorytm kwantowy dla SAT (poszukiwanie Grovera) zapewnia jedynie kwadratową poprawę w porównaniu z klasycznym algorytmem, co sugeruje, że problemy z całkowitą NP są wciąż trudne do rozwiązania na komputerach kwantowych. …
3
Problemy naturalne w
Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w U P ∩ c o U P ?N.P.∩ c o NP.NP∩coNPNP \cap coNPUP.∩ c o UP.UP∩coUPUP \cap coUP Oczywiście wielki każdy wie o w jest wersja decyzja faktoringu (czy n mają …
4
Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP
Ta odpowiedź na główne nierozwiązane problemy w informatyce teoretycznej? pytanie stwierdza, że ​​jest otwarte, jeśli określony problem w NP wymaga czasu .Ω ( n2))Ω(n2)\Omega(n^2) Patrząc na komentarze pod odpowiedzią, zastanawiałem się: Oprócz paddingu i podobnych sztuczek, jaka jest najbardziej znana złożoność czasowa dolna granica deterministycznej maszyny RAM (lub deterministycznej maszyny …
1
Co jest
Jest to związane z pytaniem Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany? Niektóre naturalne problemy (-kompletne) mają świadków o długości liniowej: zadowalające przypisanie dla , ciąg wierzchołków dla itp.NPNP\mathsf{NP}SATSATSATHAMPATHHAMPATHHAMPATH Rozważ klasę złożoności „ ograniczoną do świadków o długości liniowej”. Formalna definicja tej klasy złożoności, nazwij ją …
2
Czy znane są problemy NP-zupełne, ani trudne NP w silnym znaczeniu, ani algorytm pseudopolinomalny?
W swoim artykule (s. 503) Garey i Johnson zauważają: ... może istnieć problem NP-zupełny, który nie jest ani NP-zupełny w sensie silnym, ani rozwiązany przez algorytm pseudo-wielomianowy ... Czy ktoś zna problemy z kandydatami dotyczące wyżej wymienionych właściwości? Myślę, że możliwą odpowiedzią na to pytanie może być lista problemów NP-zupełnych …
2
Czy istnieje niedeterministyczny algorytm liniowego czasu dla CNF-SAT?
Problem decyzyjny CNF-SAT można opisać następująco: Dane wejściowe: wzór logiczny ϕϕ\phi w spójnej postaci normalnej. Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕϕ\phi ? Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema taśmami . Uważam, że istnieje NTM, który rozwiązuje CNF-SAT etapami n⋅poly(log(n))n⋅poli(log⁡(n))n \cdot \texttt{poly}(\log(n)) …
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.