Contoh di mana ukuran alfabet (

Biarkan menjadi alfabet, yaitu himpunan terbatas yang tidak kosong. String adalah setiap urutan elemen (karakter) hingga dari Σ . Sebagai contoh, { 0 , 1 } adalah alfabet biner dan 0110 adalah string untuk alfabet ini.$\Sigma$$\Sigma$$\{0, 1\}$$0110$

Biasanya, selama mengandung lebih dari 1 elemen, jumlah pasti elemen dalam Σ tidak masalah: paling baik kita berakhir dengan konstanta berbeda di suatu tempat. Dengan kata lain, tidak masalah jika kita menggunakan alfabet biner, angka, alfabet Latin atau Unicode.$\Sigma$$\Sigma$

Apakah ada contoh situasi yang penting seberapa besar alfabetnya?

Alasan saya tertarik pada ini adalah karena saya kebetulan menemukan satu contoh seperti:

Untuk setiap alfabet kita mendefinisikan oracle acak O Σ menjadi oracle yang mengembalikan elemen acak dari Σ , sehingga setiap elemen memiliki peluang yang sama untuk dikembalikan (sehingga peluang untuk setiap elemen adalah $\Sigma$$O_{\Sigma}$$\Sigma$).$\frac{1}{|\Sigma|}$

Untuk beberapa huruf dan Σ 2 - kemungkinan ukuran berbeda - pertimbangkan kelas mesin oracle dengan akses ke O Σ 1 . Kami tertarik pada mesin oracle di kelas ini yang berperilaku sama dengan O Σ 2 . Dengan kata lain, kami ingin mengubah oracle O Σ 1 menjadi oracle O Σ 2 menggunakan mesin Turing. Kami akan menyebut mesin Turing seperti itu sebagai program konversi.$\Sigma_1$$\Sigma_2$$O_{\Sigma_1}$$O_{\Sigma_2}$$O_{\Sigma_1}$$O_{\Sigma_2}$

Biarkan dan Σ = { 0 , 1 , 2 , 3 } . Mengubah O Σ 1 menjadi oracle O Σ 2 itu mudah: kita query O Σ 1 dua kali, mengonversi hasilnya sebagai berikut: 00 → 0 , 01 → 1 , 10 → 2 , 11 → 3 . Jelas, program ini berjalan di O $\Sigma_1 = \{ 0, 1 \}$$\Sigma = \{ 0, 1, 2, 3 \}$$O_{\Sigma_1}$$O_{\Sigma_2}$$O_{\Sigma_1}$$00 \rightarrow 0$$01 \rightarrow 1$$10 \rightarrow 2$$11 \rightarrow 3$ waktu.$O(1)$

Sekarang dan Σ = { 0 , 1 , 2 } . Untuk dua bahasa ini, semua program konversi berjalan dalam waktu O ( ∞ ) , yaitu tidak ada program konversi dari O Σ 1 ke O Σ 2 yang berjalan dalam waktu O ( 1 ) .$\Sigma_1 = \{ 0, 1 \}$$\Sigma = \{ 0, 1, 2 \}$$O(\infty)$$O_{\Sigma_1}$$O_{\Sigma_2}$$O(1)$

Ini dapat dibuktikan dengan kontradiksi: misalkan ada program konversi dari O Σ 1 ke O Σ 2 yang berjalan dalam waktu O ( 1 ) . Ini berarti ada d ∈ N sehingga C membuat paling banyak d query ke Σ 1 .$C$$O_{\Sigma_1}$$O_{\Sigma_2}$$O(1)$$d \in \mathbb{N}$$C$$d$$\Sigma_1$

dapat membuat kurang dari d kueri di jalur eksekusi tertentu. Kami dapat dengan mudah membuat program konversi C ′ yang mengeksekusi C , melacak berapa kali permintaan oracle dibuat. Biarkan k menjadi jumlah permintaan oracle. C ′ kemudian membuat d - k permintaan oracle tambahan, membuang hasilnya, mengembalikan apa yangakan dikembalikan$C$$d$$C'$$C$$k$$C'$$d-k$$C$

Dengan cara ini, ada persisnya jalur eksekusi untuk C ′ . Tepat $|\Sigma_1|^d = 2^d$$C'$ dari jalur eksekusi ini akan menghasilkanC′mengembalikan0. Namun,2$\frac{1}{|\Sigma_2|} = \frac{1}{3}$$C'$$0$ bukan angka integer, jadi kami memiliki kontradiksi. Karenanya, tidak ada program semacam itu.$\frac{2^d}{3}$

Lebih umum, jika kita memiliki huruf dan Σ 2 dengan | Σ 1 | = n dan | Σ 2 | = k , maka ada program konversi dari O Σ 1 ke O Σ 2 jika dan hanya jika semua bilangan prima yang muncul dalam faktorisasi utama n juga muncul dalam faktorisasi utama k (sehingga eksponen bilangan prima dalam faktorisasi tidak itu penting).$\Sigma_1$$\Sigma_2$$|\Sigma_1|=n$$|\Sigma_2|=k$$O_{\Sigma_1}$$O_{\Sigma_2}$$n$$k$

$l$$\{0, 1, 2\}$

Saya memikirkan masalah di atas ketika berdiri di supermarket, merenungkan apa yang harus saya makan malam. Saya bertanya-tanya apakah saya bisa menggunakan lemparan koin untuk memutuskan antara pilihan A, B dan C. Ternyata, itu tidak mungkin.

Ada beberapa contoh dalam teori bahasa formal di mana huruf 2-karakter dan 3-karakter memberikan perilaku yang berbeda secara kualitatif. Kozen memberikan contoh yang bagus berikut (diparafrasakan):

$\Sigma$$\in$

Jika A bebas konteks maka sort (A) bebas konteks.

$\ge$

Bukti Dinur tentang teorema PCP sangat bergantung pada manipulasi ukuran alfabet.

Secara khusus, keseluruhan struktur bukti adalah aplikasi berulang teknik penguat grafik logaritma dalam ukuran grafik beberapa kali. Pada setiap iterasi, grafik di pra-diproses menjadi grafik ekspansi reguler, diperkuat oleh kekuatan (yang meledakkan ukuran alfabet), dan kemudian komposisi PCP diterapkan (mengubah setiap kendala menjadi alfabet besar menjadi sistem kendala atas alfabet kecil).

Tujuan implisit dari proses ini adalah untuk menemukan cara untuk menggunakan kembali langkah amplifikasi sampai nilai UNSAT menjadi fraksi konstan (membuktikan teorema PCP). Poin kuncinya adalah bahwa kecuali ukuran alfabet ditarik kembali setiap kali, grafik yang dihasilkan tidak apa yang diperlukan untuk reduksi akhir.

$O(1)$$\{0,1,2\}$

$\{0,1,2\}$$\{0,1\}$$O(1)$ oleh Dodis, Patrascu, dan Thorup di atasnya, dan referensi di dalamnya, harus menjadi titik awal yang baik.

Dalam kode koreksi kesalahan, ada kemungkinan bahwa ada perbedaan mendasar antara kode biner dan kode pada huruf yang lebih besar dalam contoh Gilbert Varshamov untuk kode yang mengoreksi sebagian kesalahan (yang pada dasarnya adalah contoh serakah atau acak) yang diyakini oleh beberapa ketat dalam kasus biner dan diketahui tidak ketat pada alfabet besar melalui kode aljabar-geometri. Hal ini menyebabkan beberapa orang berspekulasi bahwa definisi standar kode koreksi kesalahan untuk alfabet besar bukanlah analog yang benar dari kode koreksi kesalahan biner.

$\ge 3$

Hasilnya agak teknis, tetapi jika Anda tertarik, Anda dapat membandingkan Lemma 8 dengan Bagian 4.1 untuk pernyataan teorema yang relevan.