# Do all languages in $P$ have polynomial proofs that they are in $P$?

A proof for a language $$L$$ belonging to a complexity class $$C$$ can be framed as there existing a verifier $$V$$ that accepts this proof as the first part of their input and the language as the second. The verifier verifies this language is a member (a word) in the language representing the complexity class.

Verifier: (Proof for $$L$$ in $$C$$, $$L$$)$$\longrightarrow$$[0,1]

Do all languages in $$P$$ have a proof of the fact that they are in $$P$$ that can be verified in polynomial time? Given a language, determining if an arbitrary $$L$$ is in $$P$$ is undecidable; however, given a proof for a language in $$P$$, can that language be verified to be in $$P$$ in polynomial time?

• I'm afraid your question makes little sense. How is the language provided as input? Also, what do you mean by polynomial time? What is the input size? – Yuval Filmus Jun 7 '20 at 7:16
• well input size is proof length + length of description of language – DeeDee Jun 7 '20 at 13:41
• how you want to represent the complexity class (what language you choose for it) is up to the programmer. Im just wondering, given any language in P and a proof for that language in P can L's membership to P be verified in polynomial time? – DeeDee Jun 7 '20 at 13:43
• The common notion of "proof" in theoretical computer science is an argument which can be verified in polynomial time. So if you are using this notion of proof, then the answer is trivially affirmative. – Yuval Filmus Jun 7 '20 at 13:47
• okay cool so it's trivially true that all languages in P have a polynomial proof of this fact. If you are solvable in poly time you can be proved to be solvable in poly time. But how can this be true if when given a language it is undecidable weather it is in P or not? – DeeDee Jun 7 '20 at 14:17

Depending on how the language is specified, the answer may be yes or no. For instance, consider the following language: $$L_S = \{0\}$$ if statement $$S$$ is true, otherwise $$L_S =$$ the language of the halting problem. Note that if $$S$$ is true, then $$L_S$$ is in $$P$$, otherwise $$L_S$$ is not in $$P$$. Now by Goedel's incompleteness theorem, there exists a true statement $$S$$ that has no proof that it is true. Thus, the corresponding language $$L_S$$ is in $$P$$ but has no proof that it is in $$P$$. You haven't given us enough details about how you propose to represent a language to determine whether your representation is expressive enough to allow defining such a language. So, the answer is unanswerable as stated.