In an informal sense disproving things is easier than proving things. For example theorems often say thing like "all objects of type Y have property X", its very difficult to work out even where to start proving such a statement unless you're an expert in Y and X, but to disprove it all you have to do is find some example Y which doesn't have property X. If you've worked with Y things for a while you probably have a bunch of "pet" Y objects you can think of and if someone proves something you kinda automatically check to see what their proof says about the ones you're familiar with.
> In an informal sense disproving things is easier than proving things.
Note that this is not true in general, and depends on the type of theorem.
The idea is that while it’s easy to show why a particular proof is incorrect, it’s much more difficult to show that every proof is incorrect.
Formally, this idea is captured by CoNP, which is believed to be different from NP and hence a strict superset of P.
> which is believed to be different from NP and hence a strict superset of P
“a strict superset of P” doesn’t really follow from that. P is also believed to be different from NP, and P is certainly not a strict superset of P.
Of course, I assume you just misspoke slightly, and that whatever it is that you actually meant to say, is correct.
E.g. maybe you meant to say “coNP is believed to both be strict superset of P (as is also believed about NP), and distinct from NP.”
I think it is believed that the intersection of NP and coNP is also a strict superset of P, but that this is believed with less confidence than that NP and coNP are distinct?
I imagine I’m not telling you anything you don’t already know, but for some reason I wrote the following parenthetical, and I’d rather leave it in this comment than delete it.
(If P=NP, then, as P=coP, then NP=P=coP=coNP , but this is considered unlikely.
It is also possible (in the sense of “no-one has yet found a way to prove otherwise” that coNP = NP without them being equal to P.
As a separate alternative, it is also possible (in the same sense) that they are distinct, but that their intersection is equal to P.
So, the possibilities:
P=NP=coNP,
P≠cocapNP=NP=coNP,
P=cocapNP≠NP,coNP,
All 4 are different,
(cocapNP is the intersection of NP and coNP)
Where the last of these is I think considered most likely?
)
I wonder if they are good, or if it's selection/confirmation/other biases that lead is to think say.
Also, aren't surprising results the most interesting!?