Hi i ve been looking at the converstation and i want to tell you @vzn that indeed proving p !=NP^NP means that P!=NP the reason is that P is low for itself while NP is not. This means that P^P is equal to P while NP^NP, the second level of the polynomial hierarchy, is conjectured not to be equal to NP. This means that if P=NP by the lowness of P then NP^NP will be equal to NP so proving P!=NP^NP is enough to separate P from NP because if P=NP then P will be equal to NP^NP as well

if P=NP then PH collapses to P as well

@rotia thx! yes have heard some of the "high" and "low" concept before but it seems to be rarely defined/ described/ analyzed... nice high level overview... it seems to be a natural property of oracle constructions many of which are still somewhat mysterious...

the paper leads to wonder, maybe there is some kind of new/ undiscovered diagonalization method that works on the "high vs low" question(s)...?

ps did you see this news/ research? fun stuff, enjoyed seeing it, maybe a continuing increasing future for this type of research

csail.mit.edu/super_mario_brothers_is_np_hard

news.mit.edu/2016/…

I knew that some years ago they proved super Mario np hard. I'll check the new paper

Thanks for the info

It's worth noting that it is currently unproved if P=PSPACE, which should be much easier to solve (showing p!=np immediately shows p!=PSPACE). Getting PSPACE "for free" reduces the credibility of a paper

Since on its own solving p vs PSPACE would be a massive breakthrough in the field

PSPACE can be thought of as like the limit of PH; PH is the Union of all the classes of finitely many quantifiers, and then PSPACE lets you have number of quantifiers scale to the size of the input.

similar to how k-coloring for fixed k is in P, but taking k as input then k-coloring is NP complete. Similarly having fixed number of quantifiers is in PH, but taking number of quantifiers as input is PSPACE-complete

So having unlimited quantifiers we have not been able to show we can't solve in P, to see a researcher claim they have separated P from 2 quantifiers is a wild claim.

Sorry not k coloring, meant k clique.

@KurtMueller hi, yeah. (howd you find this room?) any sketch of why QBFs with two identifiers not in P is "wild"? is it two quantifiers "EA" or "AE" or are they equivalent?

Through Reddit. It's wild because we haven't been able to show a much much much harder problem is not in P, the relative power of PSPACE just completely dwarfs Sigma_2. The quantifiers are (I believe ) AE. NP is just E (there exists x_1...x_n such that P(x_1..x_n) is true) and it alternates each time

@KurtMueller agreed but it seems like to separate PH/Pspace from P, there would have to be some "transition point" relating to # of quantifiers. so why not 2? are you saying, intuitively or expectedly it could/ might/ would be much higher?

anyway, welcome to the room, are you studying CS at carnegie mellon? btw there are not a whole lot of undergraduates interested in these questions... :)