Pytania otagowane jako np

NP oznacza niedeterministyczny czas wielomianowy.

1
Warunki podatności na zadowalanie 3SAT-Satisfiable
Zastanawiam się konkretnie, czy istnieje interesujący warunek dotyczący odsetka zadań spełniających formułę 3SAT, aby zagwarantować, że takie problemy są możliwe do rozwiązania. Załóżmy na przykład, że klasa problemów 3SAT z 2 n możliwych przypisań spełnia wzór logiczny; czy możemy skutecznie znaleźć satysfakcjonujące zadanie? Po co ϵ wynika problem w P?ϵ …
3
Czy istnieje prosta gra o asymetrycznej złożoności?
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch …
1
NP vs co-NP i logika drugiego rzędu
Załóżmy, że NP = co-NP i wielomian ogranicza długość dowodu niezadowolenia dla instancji 3-CNF . Czy są więc jakieś wyniki w jakiej formie może przyjąć jakiś dowód niezadowolenia dla długości ? Tzn. Ogólnie, czy taki dowód musiałby na przykład wykorzystać pełną moc logiki drugiego rzędu nad nieskończonymi strukturami (zdaję sobie …
3
Dwa warianty NP
Oto dwie odmiany definicji NP. (Prawie na pewno) definiują odrębne klasy złożoności, ale moje pytanie brzmi: czy istnieją naturalne przykłady problemów, które pasują do tych klas? (Mój próg, który jest tutaj naturalny, jest nieco niższy niż zwykle). Klasa 1 (nadklasa NP): problemy ze świadkami wielomianowymi, których weryfikacja wymaga czasu wielobiegunowego, …
1
Na czym polegają twierdzenia o dychotomii?
Powszechnie wiadomo, że pewne klasy NP -Problemy Have dychotomia twierdzeń, które gwarantują, że każde zadanie w klasie jest albo NP -Complete lub jest w P . Najbardziej znanym takim wynikiem jest twierdzenie Schaefera o dychotomii wraz z szeregiem uogólnień. Rozumiem, że udowodnienie tych twierdzeń o dychotomii nie jest naprawdę łatwe. …
3
Wykres teoretyczne ograniczenie do dowodów w teorii złożoności dowodu
Złożoność dowodu jest najbardziej podstawowym obszarem teorii złożoności obliczeniowej. Ostatecznym celem tego obszaru jest udowodnienie , co oznacza, że ​​żaden z proverów nie może dać dowodu na niezadowolenie danej formuły wejściowej. N.P.≠ c o NP.N.P.≠dooN.P.NP\neq coNP Wykres jest jednym z formalnych modeli dowodów. Moje pytanie dotyczy dalszego ograniczenia tego modelu. …
1
Niejednolici kontra Jednolici Przeciwnicy
To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access . Nieformalne oświadczenie: kiedy nierównomiernym przeciwnikom (tj. Wielorakiej …
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.