Batas bawah menghitung fungsi suatu set

Memiliki himpunan dari elemen, katakanlah saya ingin menghitung fungsi yang sensitif terhadap semua bagian dari input, yaitu tergantung pada anggota (yaitu mungkin untuk mengubah setiap anggota menjadi sesuatu lain untuk mendapatkan baru masukan nilai st dari pada dan yang berbeda). $A$ $n$ $f(A)$ $A$ $A$ $A'$ $f$ $A$ $A'$

Sebagai contoh, dapat menjadi jumlah atau rata-rata. $f$

Apakah ada hasil yang membuktikan bahwa, dalam beberapa kondisi, waktu yang diperlukan untuk mesin Turing deterministik untuk menghitung adalah ? $f$ $\Omega(n)$

complexity-theory Виталий Олегович
sumber

Perhatikan bahwa jika

adalah urutan dengan akses acak, dan asumsi sensitivitas melemah, ini tidak selalu berlaku. Misalnya,

dapat dihitung dengan dua pertanyaan, meskipun itu bukan junta.

A

$A$

(i, x_{1}, \dots, x_{n}) \to x_{i}

$(i,x_1,\dots,x_n) \to x_i$

sdcvvc

@sdcvvc contoh Anda mengingatkan saya instruksi bahasa C V[i]. Apa definisi junta ?

Виталий Олегович

Sebuah

-junta adalah fungsi boolean yang hanya tergantung pada

argumen, yaitu ada satu set

dari ukuran

sehingga untuk setiap

, jika

dan

hanya berbeda pada posisi di luar

, maka

. Saya menyalahgunakan istilah ini berarti fungsi yang tidak bergantung pada semua argumen.

k

$k$

k

$k$

A \subset {1, 2, \dots, n}

$A\subset\{1,2,\dots,n\}$

k

$k$

x

$x$

y

$y$

x

$x$

y

$y$

A

$A$

f (x) = f (y)

$f(x)=f(y)$

sdcvvc

Jika Anda mencoba mencari dukungan untuk jawaban Anda terhadap masalah jarak rata-rata pada math.se, sayangnya, ini tidak akan berhasil.

Aryabhata

@Aryabhata niat pertama adalah untuk menemukan dukungan untuk jawaban saya untuk pertanyaan ini: math.stackexchange.com/questions/129969/… , tetapi satu-satunya hal yang akan dikatakan oleh hasil ini adalah jika ada

simpul dalam grafik, algoritme menghitung jarak rata-rata mereka adalah

, yang cukup obvius. Saya telah menghapus jawaban saya di sana, karena ketika Anda menulis saya tidak membuktikan apa pun.

n

$n$

Ω (n)

$\Omega(n)$

Виталий Олегович

Jawaban:

Anda harus menentukan model perhitungan dan properti . Dalam argumen berikut ini saya akan menyatakan asumsi yang saya butuhkan. Ini dapat digeneralisasikan sedikit lebih jauh tetapi saya pikir itu harus cukup untuk memberi Anda ide. $f$

Asumsikan bahwa mesin tidak pernah membaca nilai salah satu anggota (set tetap, dan diberikan sebagai daftar). Asumsikan lebih lanjut bahwa merupakan masukan sehingga mengubah nilai yang anggota th tidak berubah jawaban 's. Asumsikan lebih lanjut bahwa sensitif terhadap seluruh bagian input, yaitu tergantung pada yang sangat anggota (yaitu dimungkinkan untuk mengubah setiap anggota ke sesuatu yang lain untuk mendapatkan masukan baru nilai st dari pada dan berbeda). $M$ $A$ $A$ $A$ $i$ $M$ $f$ $A$ $A$ $A'$ $f$ $A$ $A'$

Kita dapat menggunakan argumen musuh untuk menunjukkan bahwa mesin tidak dapat menghitung jawaban yang benar dengan mengubah nilai yang anggota untuk mendapatkan yang lain st nilai yang berbeda. Nilai pada dua set ini adalah sama, jadi salah satunya pasti salah dan karena itu tidak dapat menghitung dengan benar. $A$ $A'$ $f$ $M$ $M$ $f$

Oleh karena itu setiap mesin yang menghitung perlu membaca semua input yang mengambil langkah . $M$ $f$ $\Omega(n)$

(Di sisi lain, asumsikan bahwa kita memiliki mesin akses acak nondeterministic, dan kami ingin menghitung ATAU dari bit dalam input. Kita tidak dapat menebak sedikit dan memeriksa apakah itu 1, jika itu 1, kita menghasilkan 1 Mesin ini hanya membaca sedikit input pada langkah-langkah dan menjawab masalah dengan benar. Jadi tanpa asumsi pada dan hasilnya tidak berlaku.) $O(\lg n)$ $M$ $f$

Kaveh
sumber

Maaf saya lupa menulis bahwa model perhitungan saya adalah mesin Turing deterministik.

Виталий Олегович

+1 untuk argumen musuh, yang merupakan cara terbaik untuk mulai memahami batas bawah.

Joe