Pytania otagowane jako norms

2
normalne zachowanie maszyn Turinga
Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.ℓpℓp\ell_p Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem wprowadzającym jest praca Fortnowa, której link zamieścił tutaj Joshua Grochow …
1
Jakieś dowody na to, że Linial, Shraibman niższa granica złożoności komunikacji kwantowej nie jest ścisła?
O ile mi wiadomo, dolna granica normy faktoryzacji podana przez Liniala i Shraibmana jest zasadniczo jedyną dolną granicą znaną ze złożoności komunikacji kwantowej (lub przynajmniej obejmuje wszystkie inne). Czy są jakieś dowody przeciwko ścisłości tego powiązania? Ograniczona normą faktoryzacji (zwana także granicą ), o której mówię, to Twierdzenie 13 Linial, …
1
Dolne granice niedeterministycznej komunikacji wielostronnej
Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy wykazują separacje następującego typu: dolna granica dla protokołu losowego i (mniejsza) górna granica dla …
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.