<blockquote>
<p>I believe that all primitive recursive functions are in P (correct me if I'm wrong!).</p>
</blockquote>
<p>Exponentiation is primitive recursive <a href="https://en.wikipedia.org/wiki/Primitive_recursive_function#Some_common_primitive_recursive_functions" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Primitive_recursive_function#Some_common_primitive_recursive_functions</a></p>

CC BY-SA 4.0
2024-09-24T06:19:46.047Z
Don't you have to go a bit higher? We're measuring complexity in the number of bits, not the number itself.
Andrej Bauer
CC BY-SA 4.0
2024-09-24T07:45:36.870Z
You can either iterate it twice or go unary.
Li-yao Xia
CC BY-SA 4.0
2024-09-24T10:28:41.373Z
@AndrejBauer This does not matter. Whichever way you measure it, the output of exponentiation is exponentially larger than the input. What is more of a problem is that P is a class of decision problems rather than function problems. Though at the level of thorough confusion displayed in the question, this makes no difference either.
Emil Jeřábek
CC BY-SA 4.0
2024-09-24T12:42:16.560Z
Right, I stand corrected. Regarding P being a class of decision problems, I just re-interpreted it as FP (and the confusion remained).
Andrej Bauer
CC BY-SA 4.0
2024-09-25T16:09:29.927Z
Of course $P$ is a class of decision problems, but I was asking about a decision problem in my question. I should have said "all primitive recursive decision problems are in $P$". I see now that this is wrong -- but what does exponentiation being primitive recursive have to do with that? Exponentiation can be performed in polynomial ( viz. linear) time. Can you be more specific about my "level of thorough confusion"?
Kevin Reiss
CC BY-SA 4.0
2024-09-25T19:25:37.923Z
I actually thought you were loosely saying that primitive recursive functions run in polynomial time. But even if you meant "all problems decidable by primitive recursive functions are in P" the fact that the exponential function is primitive recursive lets you do this: (1) compute `2^O(size_of_input)` (2) use that as fuel to simulate an algorithm that takes exponential time. Anyway, you should ask this question on cs.stackexchange.com if you want to continue the discussion.
Li-yao Xia
CC BY-SA 4.0
2024-09-26T02:03:04.367Z
Right, I got it now. Thanks for clearing that up!
Kevin Reiss
CC BY-SA 4.0
2024-09-24T01:30:44.817Z
2024-09-24T01:30:44.817Z
Li-yao Xia
<p>I learned that in formal systems, establishing proof-pair-ness is primitive recursive, i.e. if <code>a</code> is a valid proof (as represented by Gödel numbering) of the theorem <code>a'</code>, then there exists some primitive recursive function <code>proof-pair{a,a'}</code> which returns True, otherwise False. I believe that all primitive recursive functions are in <span class="math-container">$P$</span> (correct me if I'm wrong!). However, by Church's theorem, it's impossible to construct an algorithm which, for any theorem <code>a'</code> constructs the valid proof <code>a</code>. This seems to me to be the case of a problem whose solution can be efficiently verified (by construction of the function <code>proof-pair{a,a'}</code>) but which not only can't be solved in polynomial time, but can't be solved at all (in general)!</p>
<p>Therefore, Church's theorem seems to imply that <span class="math-container">$P\neq NP$</span>. Does this mean if we were to find that <span class="math-container">$P = NP$</span>, Church's theorem wouldn't be valid? Or am I missing something? What about other problems which can be verified efficiently (are in <span class="math-container">$P$</span>) but finding a solution, in general, is undecidable?</p>

CC BY-SA 4.0
2024-09-24T06:21:33.393Z
Two points. First, it is not true that primitive recursive functions are all polynomial-time computable. Second, you did not explain `proof-pair` in a sensible way. Third, and most important, this is not a research-level question, please delete it and ask at https://cs.stackexchange.com (but perhaps don't ask and instead try to understand why there are primitive recursive functions which are not in $P$). Foruth, I cannot count.
Andrej Bauer
CC BY-SA 4.0
2024-09-25T16:05:11.067Z
I now understand that not all primitive recursive functions can be solved in polynomial time. I had thought since you can only apply loops with a fixed length, they would have to be polynomial e.g. nested loops. But I see now that you could e.g. compute the exponential of your input and have a loop that runs that long. I'm sorry if I didn't define `proof-pair` sensibly, it's the function defined in pages 448-451 of the book Gödel Escher Bach. Finally: if a decision problem is in $P$ but its associated solution is undecidable, does that prove $P\neq NP$? Is that a research-level question?
Kevin Reiss
CC BY-SA 4.0
2024-09-26T08:32:59.957Z
If a decision problem is in $P$ then its solutions (the set of accepted instances) form a decidable set.
Andrej Bauer
<cc.complexity-theory><complexity-classes><undecidability><church-turing-thesis><formal-systems>
Does Church's Theorem rely on $P \neq NP$?
Kevin Reiss
# Does Church's Theorem rely on $P \neq NP$?

(Asked by: username_0 on 2024-09-23)

I learned that in formal systems, establishing proof-pair-ness is primitive recursive, i.e. if `a` is a valid proof (as represented by Gödel numbering) of the theorem `a'`, then there exists some primitive recursive function `proof-pair{a,a'}` which returns True, otherwise False. I believe that all primitive recursive functions are in $P$ (correct me if I'm wrong!). However, by Church's theorem, it's impossible to construct an algorithm which, for any theorem `a'` constructs the valid proof `a`. This seems to me to be the case of a problem whose solution can be efficiently verified (by construction of the function `proof-pair{a,a'}`) but which not only can't be solved in polynomial time, but can't be solved at all (in general)!

Therefore, Church's theorem seems to imply that $P\neq NP$. Does this mean if we were to find that $P = NP$, Church's theorem wouldn't be valid? Or am I missing something? What about other problems which can be verified efficiently (are in $P$) but finding a solution, in general, is undecidable?

**Tags:** cc.complexity-theory, complexity-classes, undecidability, church-turing-thesis, formal-systems

> **Comments:**
> **username_1**: Two points. First, it is not true that primitive recursive functions are all polynomial-time computable. Second, you did not explain `proof-pair` in a sensible way. Third, and most important, this is not a research-level question, please delete it and ask at https://cs.stackexchange.com (but perhaps don't ask and instead try to understand why there are primitive recursive functions which are not in $P$). Foruth, I cannot count.  
> **username_0**: I now understand that not all primitive recursive functions can be solved in polynomial time. I had thought since you can only apply loops with a fixed length, they would have to be polynomial e.g. nested loops. But I see now that you could e.g. compute the exponential of your input and have a loop that runs that long. I'm sorry if I didn't define `proof-pair` sensibly, it's the function defined in pages 448-451 of the book Gödel Escher Bach. Finally: if a decision problem is in $P$ but its associated solution is undecidable, does that prove $P\neq NP$? Is that a research-level question?  
> **username_1**: If a decision problem is in $P$ then its solutions (the set of accepted instances) form a decidable set.  

---

## 1 answers

### Answer by username_2 on 2024-09-24. Score: 1

> I believe that all primitive recursive functions are in P (correct me if I'm wrong!).

Exponentiation is primitive recursive <https://en.wikipedia.org/wiki/Primitive_recursive_function#Some_common_primitive_recursive_functions>

> **Comments:**
> **username_1**: Don't you have to go a bit higher? We're measuring complexity in the number of bits, not the number itself.  
> **username_2**: You can either iterate it twice or go unary.  
> **username_3**: @AndrejBauer This does not matter. Whichever way you measure it, the output of exponentiation is exponentially larger than the input. What is more of a problem is that P is a class of decision problems rather than function problems. Though at the level of thorough confusion displayed in the question, this makes no difference either.  
> **username_1**: Right, I stand corrected. Regarding P being a class of decision problems, I just re-interpreted it as FP (and the confusion remained).  
> **username_0**: Of course $P$ is a class of decision problems, but I was asking about a decision problem in my question. I should have said "all primitive recursive decision problems are in $P$". I see now that this is wrong -- but what does exponentiation being primitive recursive have to do with that? Exponentiation can be performed in polynomial ( viz. linear) time. Can you be more specific about my "level of thorough confusion"?  
> **username_2**: I actually thought you were loosely saying that primitive recursive functions run in polynomial time. But even if you meant "all problems decidable by primitive recursive functions are in P" the fact that the exponential function is primitive recursive lets you do this: (1) compute `2^O(size_of_input)` (2) use that as fuel to simulate an algorithm that takes exponential time. Anyway, you should ask this question on cs.stackexchange.com if you want to continue the discussion.  
> **username_0**: Right, I got it now. Thanks for clearing that up!  

---

