show/hide this revision's text 2 added 395 characters in body

Okay, so here is what we can do, and this I'mma put in an answer, because it's something like an answer. If we assume something stronger than P \neq NP, like that the polynomial hierarchy doesn't collapse, then we can prove that some things aren't NP-complete.

The standard best example of such a result (actually, it's the only first one I knowthought of, although in retrospect I've seen the ones other people mentioned too) is that if graph isomorphism is NP-complete, the polynomial hierarchy collapses to the second level. I can't seem to find an online version of the paper in which this is proved (it's by Boppana et al.) but I believe the argument goes more or less as follows: Graph isomorphism is in NP, easily. Graph isomorphism is also in co-AM; if you don't know what this means or haven't seen the proof, basically it means that if you have two graphs and I tell you they're not isomorphic, you can check that I'm telling the truth probabilistically. How: ou secretly choose one of the two graphs, randomly permute its vertices, and send it to me; I tell you which one it is. If the graphs are isomorphic, I won't be able to give you the right answer more than half the time, but if they aren't isomorphic, I can always give you the right answer. (We're assuming here that I have unbounded computational power.)

So we apply a derandomization result, to show that co-AM is contained in some level of the polynomial hierarchy (I think the second level), and then we're done.

As far as I know this is the only method that gives these kinds of conditional results. The reason it works is that PH is robust against things like randomization, but of course we have to assume stronger conjectures in complexity theory, so there's definitely a tradeoff.

Here's something else I just thought of: Is there anything known about what a conditional proof that a certain problem isn't NP-hard can't be? (Along the lines of relativization, etc.) It's not as straightforward as relativization, since all we want is a conditional proof, but it seems like an interesting question.
show/hide this revision's text 1

Okay, so here is what we can do, and this I'mma put in an answer, because it's something like an answer. If we assume something stronger than P \neq NP, like that the polynomial hierarchy doesn't collapse, then we can prove that some things aren't NP-complete.

The standard example of such a result (actually, it's the only one I know) is that if graph isomorphism is NP-complete, the polynomial hierarchy collapses to the second level. I can't seem to find an online version of the paper in which this is proved (it's by Boppana et al.) but I believe the argument goes more or less as follows: Graph isomorphism is in NP, easily. Graph isomorphism is also in co-AM; if you don't know what this means or haven't seen the proof, basically it means that if you have two graphs and I tell you they're not isomorphic, you can check that I'm telling the truth probabilistically. How: ou secretly choose one of the two graphs, randomly permute its vertices, and send it to me; I tell you which one it is. If the graphs are isomorphic, I won't be able to give you the right answer more than half the time, but if they aren't isomorphic, I can always give you the right answer. (We're assuming here that I have unbounded computational power.)

So we apply a derandomization result, to show that co-AM is contained in some level of the polynomial hierarchy (I think the second level), and then we're done.

As far as I know this is the only method that gives these kinds of conditional results. The reason it works is that PH is robust against things like randomization, but of course we have to assume stronger conjectures in complexity theory, so there's definitely a tradeoff.