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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jun 7 '20 at 7:16
  • $\begingroup$ well input size is proof length + length of description of language $\endgroup$ – DeeDee Jun 7 '20 at 13:41
  • $\begingroup$ 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? $\endgroup$ – DeeDee Jun 7 '20 at 13:43
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 7 '20 at 13:47
  • $\begingroup$ 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? $\endgroup$ – 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.

This highlights why it is crucial to explain how you represent the inputs. There is no accepted, standard way to represent a language as a finite bit string -- indeed, the set of all languages is uncountable, so for any representation you might have in mind, there will always exist some languages that cannot be represented. Without this, the question isn't well-posed and can't be answered until you specify this deatil.

As Yuval Filmus explains, the usual understanding of the word "proof" in CS is something that can be verified in polynomial time, so if it has a proof, it has a proof that can be verified in polynomial time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.