Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

3
Problemy z NP-zupełnością nie „oczywiście” w NP
Wielu przyszło na myśl, że we wszystkich dowodach kompletności , które przeczytałem (które pamiętam), zawsze trywialne jest pokazanie, że problem jest w i pokazanie, że jest to -hard jest ... trudną częścią. Jakie problemy zakończone to te, których weryfikatory czasu wielomianowego są wysoce nietrywialne?NP NP NPNPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}
1
Czy regex golf NP-Complete?
Jak widać na ostatnim pasku XKCD i najnowszym poście na bloguwedług Petera Norviga (i opowiadania Slashdota z tym ostatnim) „regex golf” (który można by lepiej nazwać problemem separacji wyrażeń regularnych) jest zagadką polegającą na zdefiniowaniu najkrótszego możliwego wyrażenia regularnego, które akceptuje każde słowo w zestawie A i nie ma słowa …
2
Ogólna zasada, aby wiedzieć, czy problem może być NP-zupełny
To pytanie zostało zainspirowane komentarzem na StackOverflow . Oprócz znajomości problemów NP-zupełnych z książki Garey Johnson i wielu innych; czy istnieje ogólna zasada, aby wiedzieć, czy problem wygląda jak NP-zupełny? Nie szukam czegoś rygorystycznego, ale czegoś, co działa w większości przypadków. Oczywiście za każdym razem, gdy musimy udowodnić, że problem …
2
Wersja optymalizacyjna problemów decyzyjnych
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Wiadomo, że każdy problem optymalizacji / wyszukiwania ma równoważny problem decyzyjny. Na przykład problem najkrótszej ścieżki Optymalizacja / Wersja: Biorąc pod uwagę nieukierunkowane nieważony wykres a …
2
Czy Dominosa NP-Hard?
To pytanie zostało przeniesione z Mathematics Stack Exchange, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 6 lat temu . Dominosa to stosunkowo nowa gra logiczna. Jest odtwarzany na siatce . Przed rozpoczęciem gry kości domina są umieszczane na siatce (tworząc idealne kafelki ). W następnym kroku …
1
Najdłuższa powtarzająca się (rozproszona) sekwencja w ciągu
Nieformalne oświadczenie o problemie: Biorąc pod uwagę ciąg znaków, np. ACCABBABACCABBABACCABBAB , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie litery. W przykładzie możemy je pokolorować w …
3
Nauczanie kompletności NP - redukcje Turinga i karp
Interesuje mnie pytanie, jak najlepiej uczyć kompletności NP na kierunkach informatycznych. W szczególności, czy powinniśmy tego uczyć stosując redukcje Karp czy redukcje Turinga? Uważam, że koncepcje kompletności i redukcji NP są czymś, czego powinien nauczyć się każdy kierunek informatyki. Jednak ucząc kompletności NP zauważyłem, że stosowanie redukcji Karp ma pewne …
5
Dlaczego nie jest to nierozstrzygalny problem w NP?
Najwyraźniej nie ma żadnych nierozstrzygalnych problemów w NP. Jednak według Wikipedii : NP jest zbiorem wszystkich problemów decyzyjnych, dla których przypadki, w których odpowiedź brzmi „tak”, mają […] dowody, które są] weryfikowalne w czasie wielomianowym przez deterministyczną maszynę Turinga. [...] Mówi się, że problem występuje w NP wtedy i tylko …
2
Czy są jakieś problemy, które są łatwe do obliczenia, ale trudne do zweryfikowania?
Zakładając, że P NP, problemy z kompletnością NP są „trudne do rozwiązania, ale mają odpowiedzi, które można łatwo sprawdzić”. Czy ma sens rozważenie czegoś przeciwnego, to znaczy problemów, dla których łatwo jest poprawnie obliczyć prawidłową odpowiedź, ale trudno jest zweryfikować dowolne rzekome rozwiązanie?≠≠\neq Myślę, że taki problem oznaczałby albo: Wykładniczo …
2
Czy istnieje czasem skuteczny algorytm do rozwiązania #SAT?
Niech będzie formułą logiczną składającą się ze zwykłych operatorów AND, OR i NOT oraz niektórych zmiennych. Chciałbym policzyć liczbę spełniającą zadania dla . To znaczy, chcę znaleźć liczbę różnych przypisań wartości prawdy do zmiennych dla których przyjmuje wartość prawdziwą. Na przykład formuła ma trzy zadowalające przypisania; ma cztery. To jest …
2
Czy Logical Min-Cut NP-Complete?
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Definicja problemu Logical Min Cut (LMC) Załóżmy, że jest nieważonym wykresem, i są dwoma wierzchołkami , a jest osiągalne z . LMC Problem badania jak możemy nieosiągalny ze …
2
Problemy z optymalizacją „NP-complete”
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Jestem nieco zdezorientowany pewną terminologią, którą napotkałem, dotyczącą złożoności problemów związanych z optymalizacją. W klasie algorytmów miałem duży problem z oszczędnością opisany jako NP-zupełny. Nie jestem jednak do …
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.