= 27d567bc2d48d9f40e9ccc20ea370b15)
Vladimir_Nesov comments on What would you do with a solution to 3-SAT? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (78)
If one kind of atoms were NP oracles, that universe would classify as NP-capable even if P!=NP, and NP-hard would play the same role over there as P does here (if we ignore quantum).
Edit: Removed nonsense.
If the inhabitants of a universe with atomic NP oracles developed a computational complexity theory which accordingly considered performing an NP oracle operation to be O(1), then their "P" and "NP" would be analogous to what we call "P" and "NP", but they wouldn't be the same objects.
Sure, hence merely "play the same role". Note that analogy for P in NP-universe is NP-hard, not NP.
(In case anyone read parent comment before the edit, I apologize. In other news, yesterday I forgot that it's April. I need my reflection.)