5
$\begingroup$

Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or whatever? (obviously that's an absurd example, I just mean to indicate claims which use a result about complexity to demonstrate a result about Turing or tt or m etc reducibility)

I always thought that you'd be able to use complexity theoretic assumptions to demonstrate certain diagnolizations succeeded or didn't but I've never seen such a theorem. Do they exist? Is there a reason we shouldn't expect them to?

Improve this question
$\endgroup$
6
  • $\begingroup$ I'm sure you know about this, but the fact that there are oracles relative to which P = NP and other oracles relative to which P != NP probably has some implications for this question. $\endgroup$
    – James E Hanson
    Commented Nov 7, 2023 at 18:44
  • $\begingroup$ Sorry, I don't really follow. I'm not asking about P v NP particularly but are you suggesting that this kind of relativization blocks such theorems? I'm not seeing why. I mean from a computability POV those oracles can all just be computable sets I believe. $\endgroup$
    – Peter Gerdes
    Commented Nov 7, 2023 at 18:52
  • 1
    $\begingroup$ @PeterGerdes I believe that James Hanson is pointing out that those arguments often use an oracle which is in some parts chosen randomly. For example, the standard oracle separating P and NP does so. For that argument to go through, one is implicitly using that a random language with probability 1 is not computable (although this is for simple reasons of countable v. uncountable). So this is in a limited fashion going from computability theory to complexity theory. $\endgroup$
    – JoshuaZ
    Commented Nov 7, 2023 at 23:10
  • $\begingroup$ Ahh, I see, that's not the proof I was familiar with. I'm familiar with a proof that directly constructs a language B s.t. B* = {1^n : B contains a string of length n} isn't in P^B via a measure/counting argument (but as it's obv in NP^B we get seperation). That proof builds a computable language B. I see that the proof somewhat resembles construction of 1-randoms so I can guess what you have in mind but thus my confusion. $\endgroup$
    – Peter Gerdes
    Commented Nov 8, 2023 at 4:43
  • 1
    $\begingroup$ @PeterGerdes This may not be what you're looking for, but Michael Freedman has a paper on k-SAT on groups and undecidability which tries to build a bridge between complexity theory and computability theory. Unfortunately, I don't think that this line of research has been very successful so far. $\endgroup$
    – Timothy Chow
    Commented Nov 8, 2023 at 18:45

0

Reset to default

You must log in to answer this question.