Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Optymalne losowe sortowanie porównania
Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla , dolna granica deterministyczna wynosi pięć porównań, ale algorytm randomizowany (losowo permutuje dane wejściowe, a …
2
Poszukuję źródła literatury do naśladowania
Jestem pewien, że nie jako pierwszy rozważyłem pomysł, który zamierzam przedstawić. Przydałoby się jednak znalezienie literatury związanej z tym pomysłem. Chodzi o to, aby zbudować Maszynę Turinga M z właściwością, że jeśli P = NP, wówczas M rozwiąże 3-SAT w czasie wielomianowym. (Wybór 3-SAT jest arbitralny. To może być naprawdę …
1
Duże klasy zawierające LOGSPACE, dla których ścisłe włączenia nie są znane
Strona wikipedii na PSPACE wspomina, że ​​włączenie nie jest znane jako ścisłe (niestety bez odnośników).NL⊂PHNL⊂PHNL\subset PH P1: Co z i - czy są one znane jako ścisłe?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Jeśli nie, czy istnieje ustalona klasa która zawiera i dla której nie wiadomo, czy włączenie jest ścisłe?CCCP#PP#PP^{\#P}L⊂CL⊂CL\subset C P3: Czy …
2
Jak nazywa się ten wariant problemu z ustawieniem pokrycia zestawu?
Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli .UUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełniafaF{\cal F}ZA= { E1, E2), … , E| ZA|}A={E1,E2,…,E|A|}{\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\} 1) ,∀ E∈ A, …
1
Czy różni się od ?
Czy możemy udowodnić, że dla każdego języka który nie jest -hard (zakłada to ), ? Alternatywnie, czy można to udowodnić przy jakichkolwiek uzasadnionych założeniach?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}
2
Cykl hamiltonowski na wykresach bez małych cykli
Odpowiadając na to pytanie w cstheory , (nieformalnie) udowodniłem w locie następujące twierdzenie: Twierdzenie : Dla dowolnego ustalonego sonda cyklu Hamiltoniana pozostaje NP-kompletna, nawet jeśli jest ograniczona do płaskich dwustronnych grafów niekierowanych o maksymalnym stopniu 3, które nie zawierają cykli o długości ≤ l .l≥3l≥3l \geq 3≤l≤l\leq l Wydaje się …
1
Istnienie długo indukowanych ścieżek na wykresach ekspanderów
Powiedzmy, że rodzina grafów ma długo indukowane ścieżki, jeśli istnieje stała ϵ > 0, tak że każdy wykres G w F zawiera ścieżkę indukowaną na | V ( G ) | ϵ wierzchołki. Interesują mnie właściwości rodzin grafów, które zapewniają istnienie długo indukowanych ścieżek. W szczególności zastanawiam się obecnie, czy …
3
Miejsca na krótkie artykuły badawcze
Właśnie ukończyłem krótki (5-stronicowy) artykuł na temat udowodnienia pewnej gry kombinatorycznej NP-Complete. Nie jest to w żaden sposób wynikiem wielkiego znaczenia, ale uważam, że można je opublikować. Jakie miejsca byłyby dobre dla takiego papieru? Jedyne, o czym wiem, to Listy przetwarzające informacje; czy są jeszcze takie?
12 journals 
1
Czy twierdzenie Kannana implikuje, że NEXPTIME ^ NP ⊄ P / poly?
Czytałem artykuł Buhrmana i Homera „Obwody wielobiegunowe, Prawie rzadkie wyrocznie i hierarchia wykładnicza” . Na dole strony 2 zauważają, że wyniki sugerują, że nie ma obwodów wielomianowych. Wiem, że w wykładniczej hierarchii czasu to po prostu , a także wiem, że wynikiem jest to, że tak, że . Oczywiście twierdzenie …
1
Czy ta gra się kończy?
Rozważ następującą grę karcianą (znaną we Włoszech jako „Cavacamicia”, którą można przetłumaczyć jako „stripshirt”): Dwóch graczy losowo dzieli na dwie talie standardową talię kart. Każdy gracz otrzymuje jedną talię. Gracze naprzemiennie umieszczają na stosie następną kartę ze swojej talii. Jeśli gracz (A) odkłada kartę specjalną, tj. I, II lub III, …
2
Czy możemy sortować bez permutacji?
Dobrze wiadomo, że permutacje sortujące według transpozycji są w , ponieważ minimalna liczba transpozycji wymagana do sortowania π ∈ S n wynosi dokładnie i n v ( π ) = { ( i , j ) ∈ [ n ] × [ n ] : i < j i π …
12 sorting 
2
?
Czy to możliwe, że ? Czy są interesujące konsekwencje takiego ograniczenia? Czy byłoby to sprzeczne z hipotezą o wykładniczym czasie?S.A T.¯¯¯¯¯¯¯¯¯¯∈ N.T.jaM.mi( exp( n0,9) )S.ZAT.¯∈N.T.jaM.mi(exp⁡(n0,9))\overline{SAT} \in NTIME(\exp(n^{0.9}))
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.