Teoretyczne informatyka monotone

4

Stan naszej wiedzy o ogólnych obwodach arytmetycznych wydaje się być podobny do stanu naszej wiedzy o obwodach boolowskich, tzn. Nie mamy dobrych dolnych granic. Z drugiej strony mamy wykładnicze granice wielkości dla monotonicznych obwodów boolowskich . Co wiemy o monotonii obwodach arytmetycznych? Czy mamy dla nich podobne dobre dolne granice? …

22 cc.complexity-theory circuit-complexity boolean-functions monotone arithmetic-circuits

1

Czy możesz zdecydować o równoważności monotonicznych wyrażeń boolowskich, które nie zawierają negacji w PTIME?

Czy następujący problem występuje w trybie PTIME lub coNP-hard: Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennyche1e1e_1e2e2e_2 , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań do zmiennych.x1,…,xnx1,…,xnx_1,\dots,x_n∧∧\wedge∨∨\veee1≡e2e1≡e2e_1 …

16 cc.complexity-theory time-complexity boolean-functions monotone

2

Ile negacji potrzebujemy do obliczenia funkcji monotonicznych?

Razborov udowodnił, że dopasowanie funkcji monotonicznej nie występuje w MP . Ale czy możemy obliczyć dopasowanie za pomocą obwodu wielkości wielomianowej z kilkoma negacjami? Czy istnieje obwód P / poli z który oblicza dopasowanie? Jaki jest kompromis między liczbą negacji a rozmiarem dopasowania?O(nϵ)O(nϵ)O(n^\epsilon)

14 cc.complexity-theory circuit-complexity lower-bounds matching monotone

2

Liczenie liczby spełniających zadania w POZYTYWNYM CNF-SAT

Wiemy, że problem zliczania liczby spełniających przypisanie w danej ogólnej formule boolowskiej (CNF-SAT), danej formule DNF, a nawet danej formule 2SAT jest problemem # P-zupełnym . Teraz rozważmy CNF-SAT bez literału ujemnego (no , zawsze ). Problem decyzyjny jest bardzo łatwy (ustaw wszystkie zmienne na PRAWDA i sprawdź, czy przypisanie …

13 sat counting-complexity polynomial-time monotone

2

Jaka jest równoważna definicja mP / poli w odniesieniu do maszyny Turinga?

P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n. mP / poli to klasa problemów decyzyjnych rozwiązanych przez rodzinę …

13 cc.complexity-theory complexity-classes circuit-complexity polynomial-time monotone

1

Złożoność obwodu monotonicznego funkcji obliczeniowych na rzadkich wejściach

Wagaciągu binarnego to liczba jedynek w ciągu. Co się stanie, jeśli będziemy zainteresowani obliczeniem funkcji monotonicznej na wejściach z kilkoma?x ∈ { 0 , 1 } n| x ||x||x|x ∈ { 0 , 1 }nx∈{0,1}nx\in\{0,1\}^n Wiemy, że podjęcie decyzji, czy wykres ma klasę jest trudne dla obwodów monotonicznych (patrz między …

12 cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone

Pytania otagowane jako monotone