Menemukan satu set dengan perbandingan persimpangan

Masalah berikut baru-baru ini muncul dari penelitian saya dan saya ingin bertanya apakah ada yang tahu apakah masalah ini dipertimbangkan sebelumnya atau telah mendengar apa pun yang mungkin terkait.

Pengaturan umum adalah sebagai berikut. Kita diberi $F$ , keluarga $t$ -subsets dari $\{1, 2, ..., n\}$ , untuk beberapa parameter $t$ (Saya paling tertarik dengan kasus di mana $t=\lfloor n/2\rfloor$ ). Ada musuh yang mengambil satu set di $F$ , dinotasikan dengan $S$ . Tugas kita adalah untuk menemukan apa $S$ adalah. Untuk melakukan ini, kami diizinkan mengirim dua set dalam $F$ ke musuh, katakan $A$ dan $B$dan musuh akan menghasilkan $A$ jika $|A\cap S|\geq |B\cap S|$dan $B$ jika $|B\cap S|\geq |A\cap S|$. Perhatikan bahwa jika $|A\cap S|=|B\cap S|$maka musuh bisa output baik $A$ atau $B$ .

Masalah ini dapat diselesaikan secara sepele jika kita tidak peduli berapa banyak pertanyaan yang dapat kita tanyakan karena jika kita membandingkan semua pasangan set, $S$ akan menjadi satu-satunya set yang selalu dikembalikan kembali dari musuh ketika kita mengirim kueri $(S, B)$ , untuk setiap $B\neq S$ . Namun, tujuan kami adalah untuk meminimalkan jumlah kueri.

Tujuan saya adalah untuk menunjukkan bahwa masalah ini dapat diselesaikan dengan menggunakan kueri $O(poly(n))$ atau jumlah kueri super polinomial diperlukan. Saya sangat tertarik dalam kasus di mana $F$ adalah himpunan semua $\lfloor n/2\rfloor$ -subsets dari $\{1, ..., n\}$ .

Petunjuk apa pun yang terkait akan dihargai.

Ini adalah variasi dari teka-teki terkenal tentang menemukan koin palsu dengan menggunakan saldo . Tetapi sebelum melanjutkan ke hal itu, pertama mari kita selesaikan pertanyaannya, karena teknik menyelesaikannya juga berguna untuk melihat hubungan dengan masalah koin palsu.

Pertama, anggaplah bahwa permintaan set A dan B tidak harus dari keluarga F . Kemudian Anda dapat menemukan set S paling banyak dengan kueri sebagai berikut. Buat kueri ({ a }, { b }) untuk 1≤ a < b ≤ n . Perhatikan bahwa setiap elemen i ∈ {1,…, n } digunakan dalam n −1 query. Jika elemen i milik S , maka himpunan { i } dijawab setidaknya ketika lawan bukan milik S ($\binom{n}{2}=O(n^2)$$\binom{n}{2}$, dan oleh karena itu himpunan { i } dijawab setidaknya n - t kali. Jika elemen i bukan milik S , maka himpunan { i } tidak dapat dijawab jika lawan milik S , dan oleh karena itu himpunan { i } dijawab paling banyak n - t −1 kali. Oleh karena itu, menghitung berapa kali setiap set dijawab, kita dapat menentukan seluruh set S .

Ini membutuhkan set kueri yang bukan dari keluarga F , yang tidak diizinkan dalam masalah. Tapi kita bisa mengatasinya dengan menambahkan elemen t −1 yang sama ke kedua sisi. Misalnya, alih-alih membuat kueri ({1}, {2}), kita dapat membuat kueri ({1,3,4, ..., t +1}, {2,3,4, ..., t +1 }). Oleh karena itu, masalahnya dapat diselesaikan dengan kueri O ( n ² ).

Sekarang bagian yang menyenangkan dimulai. Pertimbangkan n koin berlabel 1,…, n , dan t di antaranya palsu dan sedikit lebih berat dari koin asli. Semua koin palsu memiliki bobot yang sama. Anda harus menemukan set S dari label dari t koin palsu dengan menggunakan keseimbangan hanya poli ( n ) kali. Setiap kali Anda menggunakan saldo, Anda dapat menempatkan koin min { t , n - t } paling banyak ke setiap sisi saldo. Keseimbangannya sedikit tidak akurat dalam arti bahwa jika kedua belah pihak memiliki bobot yang sama, kedua belah pihak dapat turun (berlawanan). Seperti yang saya harap Anda bisa lihat sekarang, ini persis masalah yang sama dengan pertanyaan.

Sunting : Revisi 4 dan sebelumnya memiliki satu kesalahan atau yang lain (oops) dalam koneksi yang tepat ke puzzle koin palsu.

... uhm ... Saya mencoba mencari algoritme polinomial ... masih mengerjakannya ... tapi saya pikir masalahnya harus dirumuskan kembali dengan lebih baik, karena ada kasus di mana tidak mungkin untuk menang (setidaknya jika F adalah keluarga dari semua himpunan bagian)

Sebagai contoh:

Let n=3

F={{1},{2},{3},{1,2},{1,3},{2,3}}

Queries     S={1}    S={1,2}
{1}>={2}      T      lie
{1}>={3}      T       T
{2}>={1}      F      lie 
{2}>={3}     lie      T
{3}>={1}      F       F
{3}>={2}     lie      F
{1}>={2,3}    T      lie
{2}>={1,3}    F      lie
{3}>={1,2}    F       F
{2,3}>={1}    F      lie
{1,3}>={2}    T      lie 
{1,2}>={3}    T       T

$S=\{1\}$$S=\{1,2\}$

$4$

Sepertinya varian dari Master Mind Game yang biasanya polinomial tetapi memiliki versi statis yang NP-complete ( lihat bukti ).

... Permainan Mastermind yang asli diciptakan pada tahun 1970 oleh Meirowitz, sebagai permainan papan yang memiliki lubang untuk urutan panjang N = 4 dan K = 6 pasak berwarna. Knuth (1) kemudian menunjukkan bahwa turunan Mastermind ini dapat diselesaikan dalam lima tebakan atau kurang. Chv´atal (2) mempelajari kombinatorik Mastermind umum, menunjukkan bahwa hal itu dapat diselesaikan dalam waktu polinomial, dalam kasus K> = N .... Stuckman dan Zhang (3) menunjukkan bahwa NP-complete untuk menentukan apakah urutan tebakan dan tanggapan pada umumnya dobel perhitungan Mastermind memuaskan. ...

(1) D. Knuth. Komputer sebagai master mind. Jurnal Matematika Rekreasi, 9: 1-5, 1977.

(2) V. Natal. Dalang. Combinatorica, 3 (3/4): 325–329, 1983.

(3) J. Stuckman dan G.-Q. Zhang. Mastermind adalah np-complete, 2005. http://arxiv.org/abs/cs/0512049 .