Skip to main content
MathOverflow

Return to Question

added 147 characters in body
Source Link
Tom Ellis
Tom Ellis
  • 2.9k
  • 2
  • 24
  • 27

[Edit: in the light of Nate Eldredge's answer below I rephrase the question]

P=NP is equivalent to the existence of a map of the following form:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language (call the language L) [Edit: we are not to assume these NDTMs come with any certificate proving they run in polynomial time -- Ryan requested this clarification, below]

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

Is it known that if such a map exists then it cannot be computable?

[Edit: in the light of Nate Eldredge's answer below I rephrase the question]

P=NP is equivalent to the existence of a map of the following form:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language (call the language L)

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

Is it known that if such a map exists then it cannot be computable?

[Edit: in the light of Nate Eldredge's answer below I rephrase the question]

P=NP is equivalent to the existence of a map of the following form:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language (call the language L) [Edit: we are not to assume these NDTMs come with any certificate proving they run in polynomial time -- Ryan requested this clarification, below]

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

Is it known that if such a map exists then it cannot be computable?

added 70 characters in body
Source Link
Tom Ellis
Tom Ellis
  • 2.9k
  • 2
  • 24
  • 27

Is it known that there[Edit: in the light of Nate Eldredge's answer below I rephrase the question]

P=NP is no algorithm forequivalent to the existence of a map of the following problemform:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language (call the language L, say)

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

(Of course Is it cannot be known that there isif such an algorithm, for that would prove P=NP.)a map exists then it cannot be computable?

Is it known that there is no algorithm for the following problem:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language L, say

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

(Of course it cannot be known that there is such an algorithm, for that would prove P=NP.)

[Edit: in the light of Nate Eldredge's answer below I rephrase the question]

P=NP is equivalent to the existence of a map of the following form:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language (call the language L)

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

Is it known that if such a map exists then it cannot be computable?

Source Link
Tom Ellis
Tom Ellis
  • 2.9k
  • 2
  • 24
  • 27

Non-existence of algorithm converting NP algorithm to P algorithm?

Is it known that there is no algorithm for the following problem:

  • Input: a polynomial-time non-deterministic Turing machine which accepts some language L, say

  • Output: a polynomial-time deterministic Turing machine which accepts the language L

(Of course it cannot be known that there is such an algorithm, for that would prove P=NP.)