Apakah ada referensi yang membahas hal ini?
25
Apakah ada referensi yang membahas hal ini?
Serta menyiratkan NP = co-NP, itu juga akan menyiratkan bahwa BQP mengandung NP.
Tampaknya juga menyiratkan bahwa contoh sulit dari masalah NP-lengkap mudah untuk dihasilkan.
Karena faktorisasi bilangan bulat diketahui berada di NP dan co-NP , bukti bahwa NP- lengkap akan menyiratkan NP = co-NP , yang dianggap sangat tidak mungkin.
Ada diskusi yang menarik di pos lama ini oleh Lance Fortnow .