Pytania otagowane jako cc.complexity-theory

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

2
Czy można zastosować ograniczenia losowe, aby uzyskać dolną granicę dla
Istnieje wiele dobrze znanych C 0 wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu .AC0AC0\mathsf{AC^0} Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów TC0TC0\mathsf{TC^0} (podobnie do dolnej granicy dla AC0AC0\mathsf{AC^0} )? Czy jest jakaś nieodłączna przeszkoda w stosowaniu tego podejścia do …
2
Eliminacja gaussowska pod względem działania grupowego
Eliminacja Gaussa sprawia, że ​​wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że ​​obliczenia są trwałe, tj. Trudniejszy niż problemy ). Prowadzi to do pewnego rodzaju symetrii w wyznaczniku, np. …
2
Emulacja Oblivious Turing Machine w dolnej granicy
Czy istnieje dowód, że emulacji maszyny Turinga na nieświadomej maszynie Turinga nie można wykonać w mniej niż gdzie jest liczbą kroków, które wykonuje maszyna Turinga ? Czy to tylko górna granica?O ( m logm )O(mlog⁡m)\mathcal{O}\left(m\log m\right)mmm W artykule Paula Vitányi o relatywizowanych, nieświadomych maszynach Turinga, twierdzi Vitányi „Oni [ Pippenger …
1
Elementarne granice parametru w ciągliwości parametrów stałych?
W definicji (silnej) ciągliwości parametrów stałych ustalony czas jest wyrażeniem postaci gdzie instancja wejściowa to ( x , k ) z parametrem k , p jest wielomianem, a f jest funkcją obliczalną .f(k).p(|x|),f(k).p(|x|),f(k).p(|x|),(x,k)(x,k)(x,k)kkkpppfff Możliwe jest zastąpienie wymogu obliczeniowego dla innymi klasami funkcji, o ile pojęcie redukcji jest podobnie ograniczone. (Na …
1
Parzystość-L vs. NL
Parzystość-L, znana również jako , jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko liczbę parzystą lub nieparzystą liczby ścieżek „akceptacji”. Ostatnie powiązane pytanie zadał Niel de Beaudrap.⊕⊕\oplus Moje pytanie jest następujące: Czy wiemy, czy NL ⊕ L? Czy te dwie klasy są uważane za nieporównywalne?⊆⊆\subseteq ⊕⊕\oplus
1
Czy liczenie maksymalnych klików na wykresie nieporównywalności # P jest kompletne?
To pytanie jest motywowane pytaniem MathOverflow Peng Zhanga . Valiant wykazał, że zliczanie maksymalnych klików na wykresie ogólnym jest zakończone metodą # P, ale co jeśli ograniczymy się do wykresów nieporównywalności (tzn. Chcemy policzyć maksymalne antichains w skończonym zestawie)? To pytanie wydaje się na tyle naturalne, że podejrzewam, że zostało …
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.