Computational Complexity

submited by

Style Pass

2024-09-09 22:00:08

I was not surprised when Linear Programming was in P since it was already in \( NP \cap coNP \), and problems in that intersection tend to be in P.

is in \( {\rm NP} \cap {\rm coNP} \). Is that indicative that FACTORING is in P? I do not think so, though that's backwards-since I already don't think FACTORING is in P, I don't think being in the intersection is indicative of being in P.

PARITY GAMES-thought to not be in P. (See Lance's post on the theorem that PARITY GAMES are in Quasi-poly time see here.)

Graph Isomorphism. Its in NP and its in co-AM. Under the standard derandomization assumptions GI is in AM=NP so then GI would be in \( {\rm NP} \cap {\rm coNP} \). Not known to be in P. Is it in P? I do not think there is a consensus on this.

Darn, only one that I know of. If you know of others, then let me know, but make sure they are not in the third category below.