Skip to main content
MathOverflow

Return to Question

removed capitals from title
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Complexity Implications On Computabilityimplications on computability

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?

Complexity Implications On Computability

Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP != 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?

Complexity implications on computability

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?

Source Link
Peter Gerdes
Peter Gerdes
  • 3k
  • 16
  • 18

Complexity Implications On Computability

Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP != 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?