Apakah

19

Apakah mungkin dan kardinalitas dari sama dengan kardinalitas dari ? Atau apakah berarti bahwa dan harus memiliki kardinalitas yang berbeda?P N P P ≠ N P P N PP≠NPPNPP≠NPPNP

complexity-classes p-vs-np Jason Baker
sumber
tampaknya ada pengertian di mana bahasa yang lebih kompleks lebih banyak daripada yang kurang kompleks tetapi tampaknya tidak banyak dipelajari. sebagai gantinya, ada misalnya teorema ruang dan waktu ....
vzn

Jawaban:

69

Diketahui bahwa P NP ⊂ R, di mana R adalah himpunan bahasa rekursif. Karena R dapat dihitung dan P tidak terbatas (mis. Bahasa { n } untuk n ∈ N ada di P), kami mendapatkan bahwa P dan NP keduanya dapat dihitung.⊆⊂{n}n∈N

Yuval Filmus
sumber
Bagaimana R didefinisikan?
saadtaame
Ini adalah himpunan semua bahasa yang diterima oleh program C.
Yuval Filmus
7
Biarkan saya memperbaiki definisi: adalah himpunan semua bahasa yang diterima oleh program C yang selalu berhenti . Kita tidak memerlukan definisi yang lebih formal karena program C bergantung pada alfabet yang terbatas, dan hanya ada banyak di antaranya. Teori rekursi didasarkan pada wawasan ini, bahwa program-program dapat ditentukan secara terbatas (sebagai angka) dan dengan demikian dapat dimasukkan sebagai input ke program-program lain. R
Yuval Filmus
1
Sebuah produk yang dapat dihitung dari himpunan yang dapat dihitung hanya dapat dihitung jika semua tetapi sebagian besar dari mereka adalah lajang, atau jika setidaknya satu dari mereka kosong. Saya sarankan Anda mengajukan pertanyaan lebih lanjut tentang kardinalitas pada math.stackexchange, di mana mereka berada.
Yuval Filmus
1
@ernab Subset dari subset yang dapat dihitung adalah terbatas atau dapat dihitung.
Yuval Filmus
1

Jika Anda khawatir tentang ukuran dua set P dan NP, ukuran kedua set ini tidak terbatas dan sama.

Jika kedua set ini sama, maka ukurannya juga sama. Jika mereka tidak sama, karena mereka dapat dihitung maka kardinalitas mereka sama dengan kardinalitas bilangan alami dan sama.

Jadi, dalam kedua kasus, kardinalitas mereka sama.

orezvani
sumber
3
Cantor datang dengan cara membandingkan besarnya set tak terbatas yang sudah ada di abad ke-19.
Yuval Filmus
Jadi, apakah kardinalitas bilangan Natural lebih besar dari kardinalitas bilangan alami?
orezvani
1
Tidak, mereka memiliki kardinalitas yang sama. Anda dapat memeriksa buku apa pun tentang teori himpunan (atau Wikipedia) untuk definisi yang diperlukan. Dua set dikatakan memiliki kardinalitas yang sama jika ada penipisan di antara mereka. Satu set dikatakan memiliki paling kardinalitas B jika ada suntikan dari A ke B . Dengan asumsi aksioma pilihan, untuk setiap dua set A dan B , baik A memiliki paling banyak kardinalitas B atau sebaliknya. Kita mengatakan bahwa A memiliki kardinalitas lebih kecil dari B jika paling banyak kardinalitas BABABABABABBtapi tidak kardinalitas yang sama seperti . B
Yuval Filmus
P dan NP dapat dihitung, sehingga setiap elemen telah dipetakan ke bilangan alami, apakah ini benar?
orezvani
Benar, P dan NP memiliki kardinalitas yang sama dengan himpunan bilangan asli.
Yuval Filmus
0

Saya bekerja dalam matematika terutama dan hanya memiliki sedikit keakraban dengan masalah jenis ini. Namun, teori himpunan adalah salah satu bidang studi favorit saya, dan ini tampaknya menjadi pertanyaan teori himpunan.

Jadi, untuk memulainya, P dan NP keduanya tak terhingga seperti yang ditunjukkan sebelumnya. Jadi, tidak masuk akal untuk membahas kardinalitas P dan NP lebih jauh.

Namun, secara umum:

Set ketidaksetaraan tidak menginformasikan satu tentang ukuran set. Ambil contoh, dan B = { 4 , 5 , 6 } . A ≠ B , tapi | A | = | B | . Pertimbangkan juga, C = { 1 , 2 , 3 } dan D = { 4 , 5 } . C ≠A={1,2,3}B={4,5,6}A≠B|A|=|B|C={1,2,3}D={4,5} , dan | C | ≠ | D | .C≠D|C|≠|D|

Namun, menurut definisi, set kesetaraan tidak memberi tahu kami tentang kardinalitas. Jika , maka | A | = | B | . Pertimbangkan kasus A = { 1 , 2 , 3 } dan B = { 1 , 2 , 3 } . A = B , dan | A | = | B | .A=B|A|=|B|A={1,2,3}B={1,2,3}A=B|A|=|B|

Jika dua set sangat tak terhingga, maka mereka berbagi kardinalitas yang sama. P dan NP keduanya tak terhingga jumlahnya, sehingga cukup banyak jumlah itu.

Yuval Filmus
sumber
7
Re "P dan NP sama-sama tak terhingga seperti yang ditunjukkan sebelumnya. Jadi, masuk akal untuk membahas kardinalitas P dan NP.": Saya tidak setuju. Karena keduanya sama-sama tak terbatas, tidak ada lagi yang bisa dikatakan tentang kardinalitas mereka.
@ David Eppstein, setelah berpikir, Anda benar. Saya akan mengedit jawaban saya untuk memperbaikinya. Namun, saya akan meninggalkan beberapa diskusi tentang kardinalitas secara umum (menyebutkan kardinalitas set yang tak terhingga jumlahnya).
ABP⊆NP