Dalam pengujian properti grafik, suatu algoritma meminta grafik target untuk ada atau tidaknya edge dan perlu untuk menentukan apakah target memiliki properti tertentu atau jauh dari memiliki properti. (Algoritme dapat diminta untuk berhasil dengan kesalahan 1-sisi atau 2-sisi.) Grafik adalah jauh dari memiliki properti jika tidak ada tepi dapat ditambahkan / dikurangi untuk membuat itu memiliki properti.ϵ
Properti dikatakan dapat diuji jika dapat diuji dengan cara yang ditentukan di atas dalam jumlah kueri sub-linier, atau lebih baik lagi, dalam sejumlah kueri yang tidak bergantung pada (tetapi bukan ). Gagasan tentang sifat apa yang juga dapat diformalkan, tetapi harus jelas.
Ada banyak hasil yang mengkarakterisasi sifat apa yang dapat diuji, dengan banyak contoh sifat yang dapat diuji alami. Namun, saya tidak mengetahui banyak sifat alami yang diketahui tidak dapat diuji (katakan dalam jumlah permintaan yang konstan) - yang saya kenal adalah pengujian isomorfisme pada grafik yang diberikan.
Jadi, pertanyaan saya adalah: sifat grafik alami apa yang diketahui tidak dapat diuji?
Jawaban:
Dalam model matriks adjacency, ada batas yang lebih rendah dari pada kerumitan kueri pengujian apakah grafik vertex terdiri dari dua salinan isomorfik dari beberapa grafik -vertex (lihat Pengantar pengujian properti grafik - Goldreich untuk survei).Ω(n) n n/2
Juga, ada banyak batas bawah yang bergantung pada untuk penguji dengan kesalahan satu sisi, misalnya: pengujian -Clique, -Cut, dan -Bisection (lihat Pengujian properti dan hubungannya dengan pembelajaran dan perkiraan - Goldreich , Goldwasser, Ron )n ρ ρ ρ
Selain itu, dalam model grafik derajat terbatas, pengujian 3-Colorability memerlukan permintaan , sedangkan pengujian 2-Colorability (yaitu, Bipartiteness) memerlukan (lihat pengujian properti dalam grafik derajat terbatas - Goldreich, Ron ).Ω(n) Ω(n−−√)
sumber