Pytania otagowane jako cc.complexity-theory

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

2
Czy nie możemy przedstawić złożoności Kołmogorowa?
Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga UUU która na wejściu (T,x)(T,x)(T,x) (zakodowana jako kod bez prefiksu TTT a następnie xxx ) wyprowadza dowolne TTT na wejściu xxx (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla xxx , K(x)K(x)K(x) , jako długość najkrótszego programu ppp tak aby …
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, …
16
Trudno wyglądające problemy algorytmiczne ułatwiane przez twierdzenia
Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe) twierdzenia. Ma to na celu zilustrowanie uczniom, że uczenie się większej …
5
Szybka redukcja z RSA do SAT
Wpis na blogu Scotta Aaronsona przedstawił dziś listę interesujących otwartych problemów / zadań w złożoności. Jeden zwrócił moją uwagę: Zbuduj bibliotekę publiczną instancji 3SAT z jak najmniejszą liczbą zmiennych i klauzul, które mogłyby mieć godne uwagi konsekwencje, jeśli zostaną rozwiązane. (Na przykład, instancje kodujące wyzwania faktoringu RSA.) Zbadaj wydajność najlepszych …
2
Ciasne dolne granice twierdzenia Savitcha
Przede wszystkim z góry przepraszam za wszelką głupotę. W żadnym wypadku nie jestem ekspertem od teorii złożoności (a nawet daleko! Jestem studentem, który bierze moją pierwszą klasę z teorii złożoności). Oto moje pytanie. Teraz Twierdzenie Savitcha stwierdza, że Teraz jestem ciekawy, czy ta dolna granica była ścisła, tj. Czy jest …
3
Ile wystąpień 3-SAT jest zadowalających?
Rozważ problem 3-SAT na n zmiennych. Liczba możliwych odrębnych klauzul wynosi: C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. Liczba przypadków problemem jest ilość wszystkich podzbiorów zestawu możliwych punktach: . Trywialnie, dla każdego n ≥ 3 istnieje co najmniej jeden przypadek satysfakcjonujący i jeden …
1
Czy istnieją kanoniczne techniki nierelatywizujące?
W wielu domenach istnieją techniki kanoniczne, które każdy specjalista w tej dziedzinie powinien opanować. Na przykład, w przypadku redukcji przestrzeni logicznej, „sztuczka bitowa” dla kompozycji polega na tym, że nie konstruuje się pełnego wyniku złożonej funkcji, ale zawsze prosi o ponowne obliczenie wyniku dla każdego bitu wyjściowego, co pozwala zachować …
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
Złożoność n-królowych?
Klasyczne problemy z kolejką pytają, biorąc pod uwagę dodatnią liczbę całkowitą n , czy istnieje tablica Q [ 1 .. n ] liczb całkowitych spełniająca następujące warunki:nnnnnnQ [ 1 .. n ]Q[1..n]Q[1..n] dla wszystkich i1 ≤ Q [ i ] ≤ n1≤Q[i]≤n1\le Q[i] \le njaii dla wszystkich i ≠ jQ …
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.