Kompleksitas sirkuit monoton dari fungsi komputasi pada input yang jarang

Berat $|x|$ dari string biner $x\in\{0,1\}^n$ adalah jumlah yang ada dalam string. Apa yang terjadi jika kita tertarik untuk menghitung fungsi monoton pada input dengan sedikit?

Kita tahu bahwa memutuskan apakah sebuah grafik memiliki $k$ -clique sulit untuk rangkaian monoton (lihat antara lain Alon Boppana, 1987), tetapi jika sebuah grafik memiliki paling banyak $k^3$ sisi, mungkin untuk menemukan rangkaian kedalaman dengan ukuran monoton yang dibatasi. $f(k)\cdot n^{O(1)}$ yang menentukan $k$ -clique.

Pertanyaan saya: apakah ada fungsi yang sulit dihitung oleh rangkaian monoton bahkan pada input dengan berat kurang dari $k$ ? Sarana Berikut keras ukuran sirkuit $n^{{k}^{\Omega(1)}}$ .

Bahkan lebih baik: apakah ada fungsi monoton eksplisit yang sulit untuk menghitung bahkan jika kita hanya peduli tentang masukan berat $k_1$ dan $k_2$ ?

Emil Jeřábek telah mengamati bahwa batas bawah yang diketahui berlaku untuk sirkuit monoton yang memisahkan dua kelas input ( $a$ -cliques vs maksimal $(a-1)$ -grafik berwarna), sehingga dengan mengorbankan independensi dalam argumen probabilistik dimungkinkan untuk membuatnya bekerja untuk dua kelas input bobot tetap. Ini akan menyebabkan $k_2$ menjadi fungsi dari $n$ yang ingin saya hindari.

Apa yang benar-benar ingin adalah fungsi keras eksplisit untuk $k_1$ dan $k_2$ jauh lebih kecil dari $n$ (seperti dalam kerangka kompleksitas parameterisasi). Lebih baik lagi jika $k_1=k_2+1$ .

Perhatikan bahwa jawaban positif untuk $k_1=k_2$ akan menyiratkan batas bawah eksponensial untuk sirkuit arbitrer.

Pembaruan : Pertanyaan ini mungkin sebagian relevan.

cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone MassimoLauria
sumber

2

$2$

n \times m

$n\times m$

G

$G$

m = o (n)

$m=o(n)$

u

$u$

x_{u}

$x_u$

f_{G} (x)

$f_G(x)$

x_{u} \land x_{v}

$x_u\land x_v$

u v

$uv$

G

$G$

s (G)

$s(G)$

f_{G}

$f_G$

\leq 2

$\leq 2$

s (G) \geq (2 + c) n

$s(G)\geq (2+c)n$

c > 0

$c>0$

≫ n / 2

$\gg n/2$

\exp (min {a, n / b}^{1 / 4})

$\exp(\min\{a,n/b\}^{1/4})$

b

$b$

a

$a$

a < b

$a<b$

k

$k$

n^{k}

$n^k$

k \geq 3

$k\geq 3$

(n - k)

$(n-k)$

O (n^{2} \log n)

$O(n^2\log n)$ untuk setiap konstanta .

k

$k$

Stasys

Saya harus mengklarifikasi bahwa saya peduli dengan input jarang dalam arti grafik jarang. Mencari -clique dalam grafik yang sangat jarang (dengan mengatakan tepi) dapat dilakukan dalam ukuran sirkuit monoton FPT.

k

$k$

k^{10}

$k^{10}$

MassimoLauria

Contoh Anda di komentar pertama sangat bagus. Jika saya mengerti benar ini adalah masalah yang sama dengan fungsi monoton yang sulit pada berat yang tetap . Menggunakan fungsi komplemen semu untuk mensimulasikan input yang dinegasikan, kompleksitas sirkuit tidak berbeda antara case monoton dan non-monoton. Untuk konstanta (atau kecil) komplemen semu ini dapat diimplementasikan secara efisien oleh rangkaian monoton.

k

$k$

k

$k$

MassimoLauria

komentar pertama saya mengandalkan kompleksitas grafik. Fenomena " " dapat ditemukan di halaman 13 draf ini . Btw saya belum mengerti apa yang Anda maksud dengan menjadi "sulit untuk k dan k +1"? (Kesalahan saya, tentu saja.)

(2 + c) n

$(2+c)n$

Stasys

khusus mempertimbangkan satu bagian dari pertanyaan (misalnya untuk = 1, = 2), Lokam mempelajari fungsi "2-slice" dalam makalah ini & membuktikan bahwa batas bawah yang kuat pada mereka dapat digeneralisasi, oleh karena itu ini adalah masalah terbuka yang sangat sulit terkait dengan pemisahan kelas kompleksitas dasar & setiap konstruksi / fungsi eksplisit akan menjadi terobosan; dari abstrak: $k_1$ $k_2$

Fungsi Boolean f disebut fungsi 2-slice jika ia mengevaluasi ke nol pada input dengan kurang dari dua 1 dan mengevaluasi ke satu pada input dengan lebih dari dua 1. Pada input dengan tepat dua 1 f dapat didefinisikan secara nontrivial. Ada korespondensi alami antara fungsi 2-slice dan grafik. Menggunakan kerangka kompleksitas grafik, kami menunjukkan bahwa batas bawah monoton superlinear yang cukup kuat untuk kelas fungsi 2-irisan yang sangat khusus akan menyiratkan batas bawah superpolinomial atas dasar lengkap untuk fungsi tertentu yang berasal dari mereka.

Kompleksitas Grafik dan Fungsi Iris / Satyanarayana V. Lokam, Teori Komputasi. Sistem 36, 71-88 (2003)

juga seperti dalam komentarnya SJ meliput kasus serupa ini dalam bukunya di bagian yang mengeksplorasi kompleksitas bintang dari grafik sec1.7.2.

Kompleksitas fungsi Boolean: kemajuan dan batas , Stasys Jukna

vzn
sumber

Kompleksitas sirkuit monoton dari fungsi komputasi pada input yang jarang

Jawaban: