Elemen minimal predikat monoton di atas powerset

Pertimbangkan predikat monoton atas powerset (dipesan dengan disertakan). Dengan "monoton" Maksud saya: sedemikian rupa sehingga , jika maka . Saya mencari algoritma untuk menemukan semua elemen minimal , yaitu, sedemikian rupa sehingga $P$ $2^{|n|}$ $\forall x, y \in 2^{|n|}$ $x \subset y$ $P(x)$ $P(y)$ $P$ $x \in 2^{|n|}$ $P(x)$ tapi $\forall y \subset x$ , $\neg P(y)$ . Karena lebar $2^{|n|}$ adalah , mungkin ada banyak elemen minimal secara eksponensial, dan oleh karena itu waktu menjalankan algoritma seperti itu bisa eksponensial secara umum. Namun, mungkinkah ada algoritma untuk tugas ini yang jumlahnya banyak dalam ukuran output? $n \choose n/2$

[Konteks: Pertanyaan yang lebih umum ditanyakan tetapi tidak ada upaya dalam jawaban untuk mengevaluasi kompleksitas algoritma dalam ukuran output. Jika saya berasumsi bahwa hanya ada satu elemen minimal, misalnya, maka saya dapat melakukan pencarian biner mengikuti jawaban ini dan menemukannya. Namun, jika saya ingin terus menemukan elemen yang lebih minimal, saya perlu mempertahankan informasi terkini yang saya miliki tentang $P$ dengan cara yang akan membuatnya lebih mudah untuk melanjutkan pencarian tanpa membuang waktu untuk apa yang sudah diketahui. Apakah mungkin untuk melakukan ini dan menemukan semua elemen minimal dalam waktu polinomial dalam ukuran output?]

Idealnya, saya ingin memahami apakah ini dapat dilakukan dengan DAG umum, tetapi saya sudah tidak tahu bagaimana menjawab pertanyaan untuk . $2^{|n|}$

ds.algorithms ds.data-structures partial-order order-theory search-problem a3nm
sumber

The powerset dipesan dengan dimasukkan adalah DAG (dengan berbagai bagian sebagai simpul dan satu ujung antara pasangan bagian yang termasuk dalam satu sama lain, hanya menyimpan reduksi transitif grafik ini untuk menghilangkan tepi yang berlebihan yang tersirat oleh transitivitas). Tampaknya wajar untuk mengajukan pertanyaan yang sama tentang DAG sewenang-wenang.

2^{| n |}

$2^{|n|}$

{1, . . ., n}

$\{1, ..., n\}$

a3nm

Jawaban:

Masalah Anda dikenal dalam literatur pembelajaran sebagai "mempelajari fungsi monoton menggunakan kueri keanggotaan". Kelas fungsi monoton di mana seseorang dapat mengidentifikasi semua minterms dikenal sebagai "dipelajari secara polinomi menggunakan kueri keanggotaan".

Tampaknya keberadaan algoritma waktu polinomial masih terbuka. Schmulevich et al. membuktikan bahwa "Hampir semua fungsi Boolean monoton secara politis dapat dipelajari menggunakan kueri keanggotaan". Jika kita juga mengharuskan th minterm dihasilkan dalam waktu polinomial di dan , maka masalahnya adalah setara dengan monoton dualization, seperti yang ditunjukkan oleh Bioch dan Ibaraki . Berikut ini adalah survei yang membahas dualisasi monoton. $t$ $n$ $t$

Yuval Filmus
sumber

Terima kasih atas jawaban yang sangat berguna ini. Apakah Anda mengetahui generalisasi untuk DAG sewenang-wenang (yaitu, lebih dari kasus khusus dalam bagian 5.2 dari Eiter et al.)?

a3nm

Tidak, sayangnya tidak.

Yuval Filmus

Oke, saya akan menerima jawaban ini. Keterangan tambahan: (1) jawaban ini adalah tentang kompleksitas komputasi, bukan kompleksitas dalam jumlah evaluasi (lihat cstheory.stackexchange.com/a/14862/4795 untuk kasus terakhir ini), dan (2) pembukaan persis pertanyaannya adalah "dapatkah Anda mempelajari fungsi boolean monoton dalam waktu polinomial dalam dan jumlah minimum dan maksimumnya", tidak ada harapan untuk melakukannya dalam waktu polinomial dalam dan jumlah maxima karena dapat ada jumlah linier maksima tetapi angka eksponensial dari minima (lih. 6.1 paragraf 2 dalam survei yang disebutkan di atas).

P

$P$

n

$n$

n

$n$

a3nm

Lihat pertanyaan saya yang lain cstheory.stackexchange.com/q/16258/4795 untuk informasi tentang kompleksitas kueri kasus terburuk global untuk DAG sewenang-wenang.

a3nm

dualisasi monoton (CNF ← → DNF) & DAGs. Kedengarannya sangat mirip teorema dari kompleksitas fungsi juknas book boolean sec 9.4. "kriteria batas bawah" thm 9,17

vzn