Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

2
Złożoność zliczania wszystkich połączonych podgrafów
Niech G będzie połączonym wykresem. Jaka jest złożoność zliczania wszystkich połączonych podgrafów, jeśli G jest następujących typów? G jest ogólny. G jest planarne. G jest dwustronny. Nie dbam o żadne struktury lub ..., po prostu muszę policzyć wszystkie połączone podgrupy! Interesuje mnie również złożoność zliczania wszystkich połączonych podsgrafów z dokładnie …
2
Problemy, które można rozstrzygać, ale których nie można zweryfikować w czasie wielomianowym
Pracując nad nieco niezwiązanym projektem dla Suresh, ostatnio natknąłem się na pracę wykonaną przez Page i Opper na temat systemów tworzonych przez użytkowników, a część ich pracy krótko omówiła problemy, których nie można zweryfikować w czasie wielomianowym. Nie udało mi się znaleźć wielu informacji o innych problemach, których nie można …
10
Materiały do ​​nauki o problemie P vs. NP
Niedawno przypomniano mi o problemie vs. jak wyjaśnił Stephen A. Cook z Clay Mathematics Institute.N PP.P.\mathsf{P}N P.N.P.\mathsf{NP} To wzbudziło moje zainteresowanie i chciałbym dowiedzieć się więcej na ten temat. Pierwszym krokiem byłoby lepsze zrozumienie problemu i ogólne zrozumienie tego obszaru. Czy możesz polecić jakieś książki lub inne zasoby, w których …
1
Jawne wielomiany w 1 zmiennej o dolnych granicach złożoności obwodu superlogarytmicznego?
Zliczając argumenty, można pokazać, że istnieją wielomiany stopnia n w 1 zmiennej (tj. Coś w postaci które mają złożoność obwodu n. Można również pokazać, że wielomian taki jak wymaga co najmniej mnożenia (potrzebujesz tego tylko, aby uzyskać wystarczająco wysoki stopień). Czy są jakieś wyraźne przykłady wielomianów w 1 zmiennej o …
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?ϵ …
2
Czy
Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jeśli jest językiem PSPACE uzupełniania, P = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jeśli jest deterministyczną wyrocznią wielomianową, P B ≠ N P B (przy założeniu P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP to klasa problemów decyzyjnych analogiczna dla # P i P ⊆ P P ⊆ P S P …
3
Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur …
1
Problem techniczny z dowodem twierdzenia PCP
Czytam stąd dowód i natknąłem się na problem techniczny (ale kluczowy). Wiem, że jest to dość specyficzne i kontekst jest problematyczny, ale sam nie mogłem tego pojąć. Na stronach 51 i 55, po przedstawieniu „standardowych” weryfikatorów, przechodzą do modyfikacji weryfikatorów w celu sprawdzenia podzielonych zadań. W pierwszym przypadku (s. 51) …
1
Przykład logarytmicznej długości świadka jest łatwiejszy do zweryfikowania niż znalezienia
Łatwe spostrzeżenie, że, jeżeli problem jest rozstrzygalne przez wielomian czasu niedeterministycznych programu przy O ( log n ) niedeterministycznych bitów (czyli wszystkie świadków logarytmiczna długości), a następnie ∈ P .ZAAAO(logn)O(log⁡n)O(\log n)A∈PA∈PA \in \mathsf{P} Jeśli ktoś zadaje pytanie: „Czy łatwiej jest zweryfikować świadka niż go znaleźć?” dla takich problemów, i uważa …
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.