<p>I think that there is a fundamental underlying difficulty with the question you are asking here (and that you asked in your related question about incomprehensible languages).</p>

<p>Roughly speaking, it seems you're seeking a language $L$ such that</p>

<blockquote>
  <p>$L\in P$ but ZFC doesn't know that $L\in P$.</p>
</blockquote>

<p>To understand the difficulties with your question, I think you must first appreciate that there's a fundamental difference between <i>intensional</i> and <i>extensional</i> definitions of a language $L$.  Extensionally, $L$ is determined by what words are or are not members of $L$.  That is, two languages $L$ and $L'$ are extensionally equal if and only if they contain exactly the same words as members.  In contrast, an <i>intensional</i> definition of $L$ describes some <i>conditions</i> for a word to be in $L$.  A Turing machine that accepts $L$, or a first-order formula $\phi(x)$ that holds if and only if $x\in L$, can be thought of as an intensional definition of $L$.</p>

<p>The point is that every $L$ that is (extensionally) in $P$ admits a description that is extremely straightforward, because $P$ is a so-called "syntactic" complexity class.  Namely, just take a <i>polynomially clocked</i> Turing machine, that terminates in exactly the amount of time desired.  Any "reasonable" system for doing mathematics, such as PA or ZFC, is going to be able to prove that $L\in P$ if you use this straightforward description of $L$.</p>

<p>So if you want to confuse ZFC, you're going to have to come up with some (intensional) description of $L$ that is "too complicated" for ZFC to recognize as being equivalent to the straightforward description of $L$.  This is possible, but in some sense it's too easy to be interesting.  All you have to do is to take something that we know that ZFC doesn't understand (e.g., its own consistency) and mix it up with the definition of $L$ somehow.  For example, here's a description of a set of integers:</p>

<blockquote>
  <p>$x$ is even and $x$ doesn't encode a proof that ZFC is inconsistent.</p>
</blockquote>

<p>Assuming ZFC is consistent, the above formula defines the set of even integers, but ZFC doesn't know it.  With a bit more tinkering, we can easily get a description of the set of even integers that ZFC won't be able to prove is in $P$.</p>

<p>The upshot is that if you're hoping that the reason it's hard to prove that $P\ne NP$ is that there are languages in $P$ that are "too complicated" for us to reason about, then I think you're barking up the wrong tree.  Extensionally, every language in $P$ is in $P$ for trivial reasons.  You can muddy the waters by playing around with impossibly opaque descriptions of languages in $P$, but this is a general trick that has nothing to do with $P$ in particular, so I don't think it yields much insight.</p>

CC BY-SA 3.0
2012-06-12T15:53:02.523Z
Timothy, thank you for this fine essay. Do I appreciate correctly, though, that the standard definition of *P* — per Arora & Barak *Computational Complexity: a Modern Approach* and/or Hartmanis *Feasible Computations and Provable Complexity Properties*, or the Millenium Prize statement — is *NOT* extensional? Yet perhaps some problems would be more tractable if the definition of *P* were suitably amended, on grounds that (per Hartmanis) "We need to explore further how our `world view' of the complexity of algorithms has to be changed if we consider only provable properties of algorithms."
John Sidles
CC BY-SA 3.0
2012-06-12T17:28:47.037Z
@JohnSidles the standard definition of P is "the set of all languages that can be decided by some polytime TM". how a language is defined (intensionally or extensionally) does not enter the picture at all: it only enters the picture once we need to prove that some particular machine accepts some particular language.
Sasho Nikolov
CC BY-SA 3.0
2012-06-12T17:47:58.827Z
Sasho, the thrust of Timothy Chow's answer (as I read it) is  "If we define *P* *extensionally*, then deciding membership in *P* is trivial."  The thrust of your comment (as I read it) is that by present-day convention, "*P* is defined *intensionally*." Combining these two observations leads us to appreciate Hartmanis' remark: "Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally."  And so we naturally wonder, how the definition of *P* might be varied, so as to more readily prove good theorems.
John Sidles
CC BY-SA 3.0
2012-06-12T18:14:12.500Z
@John: I introduced the terms "intensional" and "extensional" for expository purposes. The terms aren't formally used in mathematics. In particular, I'm not sure that it helps to apply these adjectives to "the standard definition of $P$." However, your other point, that exploring different ways of defining $P$ might be fruitful, is one I would agree with.
Timothy Chow
CC BY-SA 3.0
2012-06-12T18:38:34.530Z
Yes, the definitions of *gnostic* and *transcendental* are purposed with a view toward (eventually) proving statements like the following:     **Theorem**  Let *P'* and *NP'* be the gnostic restrictions of *P* and *NP* resp.  Then *P' ≠ NP'*.      For a suitably broad-yet-natural definition of "gnostic", such a proof might be comparably illuminating, and have comparable practical implications, to a (presumably far harder?) proof that *P ≠ NP*.  AFAICT, Juris Hartmanis was among the first complexity theorists to seriously pursue this line of investigation.
John Sidles
CC BY-SA 3.0
2012-06-21T13:19:48.930Z
Thank you @TimothyChow. After reflecting on both your answer and Ricky Demer's (below), **D1** has been amended by the substitution *real* -> [*computable real*](http://en.wikipedia.org/wiki/Computable_number), to close the loophole that Ricky identified, and also to mitigate your concern that *P*'s definition is "impossibly opaque*. However, the latter concern cannot be wholly mitigated, because the the question's motivation is the Hartmanis-style intuition that even the [standard complexity-theoretic definitions of *P*](http://www.claymath.org/millennium/P_vs_NP/) are "impossibly opaque."
John Sidles
CC BY-SA 3.0
2012-06-27T13:19:40.987Z
In preparation for conversion to community Wiki, and with due regard to Timothy Chow's distinction between *intensional* and *extensional*, and with regard also to closing Ricky Demer's loophole, a definition **DO** has been added which restricts  run-time exponents to the set of computable numbers *r* that are defined intensionally, that is, by "a Turing machine finitely given that provably halts and provably converges to a real number that is r by definition."  Thanks are given for these suggestions!
John Sidles
CC BY-SA 3.0
2012-06-28T10:46:56.083Z
Thank you, Timothy Chow.  Because you have the highest-rated answer, I have awarded you the bounty.  In particular, your answer greatly influenced both the starting definition **DO** and final nomenclature of *gnostic* verus *cryptic*.  I have flagged the question for conversion to community wiki.
John Sidles
CC BY-SA 3.0
2012-06-12T15:15:47.180Z
2012-06-12T15:15:47.180Z
Timothy Chow
<p>Definition 1: Let $x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$. Clearly, we can build a Turing machine which, given $n$, will compute $x_n$. Also the $x_n$ converge to $x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$.</p>

<p>So $x$ is a gnostic real, which is equal to 2 if and only if $\bf{ZF}$ is consistent.</p>

<p>Definition 2: For any gnostic real $x &gt; 1$, let $M'_x$ be a Turing machine which takes an index $n$ of a Turing machine $N$ and an input $s$, simulates $N$ on $s$ for $|s|^x/\log(|s|)$ steps (this function is time-constructible, because $x$ is gnostic), and inverts the result. By the Recursion Theorem, we may choose $M_x$ to be $M'_x$ with a fixed index of $M_x$ as its first input. Then a standard argument (the Time Hierarchy Theorem) shows that $M_x$ has runtime $\mathcal O(|s|^y)$ precisely when $y\ge x$, and that $M_x$ is efficient for its language.</p>

<p>Therefore, for $x$ as in Definition 1, $M_x$ will run in time $\mathcal O(|s|^2)$ precisely if $x = 2$, ie if $\bf{ZF}$ is consistent; moreover this fact will itself be provable in $\bf ZF$. So [if $\bf ZF$ is consistent], $M_x$ is a [strongly and canonically] cryptic machine, and this fact will be provable in $\bf ZF + Con(\bf ZF)$.</p>

<p>However, $\bf ZF + \not Con(\bf ZF)$ proves that all languages in $\bf P$ are gnostic, since it proves that $\bf ZF$ proves that every language has runtime $\mathcal O(|s|^z)$ for every $z$. So it is undecidable in $\bf ZF$ whether any cryptic language exists.</p>

<p>To answer your second and third questions, the definition I gave above for $M_x$ is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.</p>

CC BY-SA 3.0
2012-09-06T15:54:59.203Z
Ben, thank you for this carefully reasoned and thoughtfully phrased answer.  It will take a few days to digest it ... I hope to comment in a week or so!
John Sidles
CC BY-SA 3.0
2012-09-02T22:56:56.457Z
2012-09-02T22:56:56.457Z
Ben Standeven
<h3>Answer: not known.</h3>
<p>The questions asked are natural, open, and apparently difficult; the question now is a  community wiki.</p>
<h3>Overview</h3>
<p>The question seeks to divide languages belonging to the complexity class <span class="math-container">$P$</span>  — together with the decision Turing machines (TMs) that accept these languages — into two complementary subclasses:</p>
<ul>
<li><em>gnostic</em> languages and TMs (that are feasible to validate/understand), versus</li>
<li><em>cryptic</em> languages and TMs (that are infeasible to validate/understand).</li>
</ul>
<h3>Definitions: <em>gnostic</em> vs <em>cryptic</em> numbers, TMs, and languages</h3>
<p>Within the axiom frameworks <a href="https://en.wikipedia.org/wiki/Peano_axioms" rel="nofollow noreferrer">PA</a> and <a href="https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory" rel="nofollow noreferrer">ZFC</a>, we distinguish gnostic from cryptic Turing machines and languages as follows:</p>
<blockquote>
<p><strong>D0</strong>  We say that a <a href="https://en.wikipedia.org/wiki/Computable_number#Formal_definition" rel="nofollow noreferrer">computable real number</a> <span class="math-container">$r$</span> is <em>gnostic</em> iff it is associated to a non-empty set of TMs, with each TM specified in PA as an explicit list of numbers comprising valid code upon a universal TM, such that for any accuracy <span class="math-container">$\epsilon\gt0$</span> supplied as an input, each TM provably (in ZFC) halts with an output number <span class="math-container">$o$</span> that provably (in ZFC) satisfies <span class="math-container">$r-\epsilon\lt o\lt r+\epsilon$</span>.</p>
</blockquote>
<p><strong>Remark</strong>  It is known that some computable reals are not gnostic (for a concrete example see <a href="https://cstheory.stackexchange.com/a/12168/1519">Raphael Reitzig's answer</a> to jkff's question &quot;<a href="https://cstheory.stackexchange.com/q/12162/1519">Are there non-constructive algorithm existence proofs?</a>&quot;).  To avoid grappling with these computable-yet-awkward numbers, the restriction is imposed that runtime exponents be computable by TMs that are explicitly enumerated in PA (as contrasted with TMs implicitly specified in ZFC).  For further discussion see the section <strong>Definitional considerations</strong> (below).</p>
<p>Now we seek definitions that capture the intuition that the complexity class <span class="math-container">$P$</span> includes a subset of <em>cryptic</em> languages to which no (gnostic) runtime exponent lower-bound can provably be assigned.</p>
<p>To look ahead, the concluding definition (<strong>D5</strong>) specifies the idea of a <i>canonically cryptic decision TM</i>, whose definition is crafted with a view toward obviating reductions that (trivially) mask cryptic computations by overlaying computationally superfluous epi-computations.  The rationale and sources of this key definition are discussed later on — under the heading <strong>Definitional Considerations</strong> — and the contributions of comments by Timothy Chow, Peter Shor, Sasho Nikolov, and Luca Trevisan are gratefully acknowledged.</p>
<blockquote>
<p><strong>D1</strong>  Given a Turing machine M that halts for all input strings, M is called <em>cryptic</em> iff the following statement is neither provable nor refutable for at least one gnostic real number <span class="math-container">$r \ge 0$</span>:</p>
<blockquote>
<p><strong>Statement:</strong> M's runtime is <span class="math-container">${O}(n^r)$</span> with respect to input length <span class="math-container">$n$</span></p>
</blockquote>
<p>Turing machines that are not cryptic we say are gnostic TMs.</p>
<p><strong>D2</strong>  We say that a decision Turing machine M is <em>efficient</em> iff it has a gnostic runtime exponent <span class="math-container">$r$</span> such that the language L that M accepts is accepted by no other TM having a gnostic runtime exponent smaller than <span class="math-container">$r$</span>.</p>
<p><strong>D3</strong>  We say that a language L is <em>cryptic</em> iff it is accepted by <strong>(a)</strong> at least one Turing machine M is that is both efficient and cryptic, and moreover <strong>(b)</strong> no TM that is both efficient and gnostic provably accepts L.</p>
</blockquote>
<p>To express <strong>D3</strong> another way, a language is cryptic iff the TMs that accept that language most efficiently are themselves cryptic.</p>
<blockquote>
<p>Languages that are not cryptic we say are <em>gnostic</em> languages.</p>
<p><strong>D4</strong>  We say that a cryptic TM is <em>strongly cryptic</em> iff the language it accepts is cryptic.</p>
<p><strong>D5</strong>  We say that a strongly cryptic TM is <em>canonically cryptic</em> iff it is efficient.</p>
</blockquote>
<p>To express <strong>D5</strong> another way, every cryptic language is accepted by a set of canonically cryptic decision TMs, which are the most efficient decision TMs that accept that language.</p>
<h3>The questions asked</h3>
<p>The following conjecture <strong>C0</strong> is natural and (apparently) open:</p>
<blockquote>
<p><strong>C0</strong>  The complexity class P contains at least one cryptic language.</p>
</blockquote>
<p>Three questions are asked, <strong>Q1</strong>–<strong>Q3</strong>, of which the first is:</p>
<blockquote>
<p><strong>Q1</strong>  Is the <strong>C0</strong> conjecture independent of PA or ZFC?</p>
</blockquote>
<p>Under the assumption that <strong>C0</strong> is true — either provably in ZFC, or as an independent axiom that is supplemental to ZFC — two further questions are natural:</p>
<blockquote>
<p><strong>Q2</strong>  Can at least one cryptic language in <em>P</em> be presented concretely, that is, exhibited as a dictionary of explicit words in a finite alphabet that includes all words up to any specified length?  If so, exhibit such a dictionary.</p>
<p><strong>Q3</strong>  Can at least one canonically cryptic decision TM be presented concretely, that is, as an enabling description for building a physical Turing machine that decides (in polynomial time) all the words of the dictionary of <strong>Q2</strong>?   If so, construct such a Turing machine and by computing with it, exhibit the cryptic language dictionary of <strong>Q2</strong>.</p>
</blockquote>
<h3>Definitional considerations</h3>
<p>Definition <strong>D0</strong> implies that every gnostic real number is computable, but it is known that some computable real numbers are <em>not</em> gnostic.  For examples, see answers on <em>MathOverflow</em> by <a href="https://cstheory.stackexchange.com/a/1979/1519">Michaël Cadilhac</a> and <a href="https://cstheory.stackexchange.com/a/1991/1519">Ryan Williams</a> and on <em>TCS StackExchange</em> by <a href="https://cstheory.stackexchange.com/a/12168/1519">Raphael Reitzig</a>.  More generally, definitions <strong>D0–D5</strong> are crafted to exclude references to non-gnostic runtime exponents.</p>
<p>As discussed in the TCS wiki &quot;<a href="https://cstheory.stackexchange.com/q/11570/1519">Does P contain incomprehensible languages?</a>,&quot; definitions <strong>D0–D5</strong> ensure that every cryptic language is accepted by at least one TM that is canonically cryptic. (Note also that in the present question the word &quot;cryptic&quot; replaces the less descriptive word &quot;incomprehensible&quot; used in the wiki).</p>
<p>Moreover — in view of <strong>D3(a)</strong> and <strong>D3(b)</strong> — there exists no computationally trivial reduction of a canonically cryptic TM to a gnostic TM that provably recognizes the same language.  In particular, <strong>D3(a)</strong> and <strong>D3(b)</strong> obstruct the <em>polylimiter</em> reduction strategies that were outlined in comments by <a href="https://cstheory.stackexchange.com/questions/11570/does-p-contain-incomprehensible-languages-tcs-community-wiki#comment31657_11570">Peter Shor</a>, and by <a href="https://cstheory.stackexchange.com/questions/11570/does-p-contain-incomprehensible-languages-tcs-community-wiki/11575#11575">Sasho Nikolov</a>, and independently by <a href="https://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962" rel="nofollow noreferrer">Luca Trevisan</a>, and obstructs too the <em>polynomially clocked</em> reduction strategy of <a href="https://cstheory.stackexchange.com/a/11707/1519">Timothy Chow</a>, all of which similarly mask cryptic computations by overlaying a computationally superfluous <a href="https://cstheory.stackexchange.com/questions/11570/does-p-contain-incomprehensible-languages-tcs-community-wiki#comment31708_11592">epi-computation</a>.</p>
<p>In general, the definitions of &quot;gnostic&quot; and &quot;cryptic&quot; are deliberately tuned so as to be robust with respect to mathematically trivial reductions (and it is entirely possible that further tuning of these definitions may be desirable).</p>
<h3>Methodological considerations</h3>
<p>Lance Fortnow's review &quot;<a href="https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/abstract" rel="nofollow noreferrer">The status of the P versus NP problem</a>&quot; surveys methods for establishing the independence (or otherwise) of conjectures in complexity theory; particularly desired are suggestions as to how the methods that Lance reviews might help (or not) to answer <strong>Q1</strong>.</p>
<p>It is clear that many further questions are natural.  E.g., the <a href="https://rjlipton.wpcomstaging.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/" rel="nofollow noreferrer">Hartmanis-Stearns Conjecture</a> inspires us to ask &quot;Do cryptic real-time multitape Turing machines exist? Is their existence (or not) independent of PA or ZFC?&quot;</p>
<h3>Zeilberger-type considerations</h3>
<p>In the event that <strong>Q1</strong> is answered by &quot;yes&quot;, then oracles that decide membership in <span class="math-container">$P$</span> exist outside of PA or ZFC, and therefore, an essential element of modern complexity theory is (at present) not known to reside within any formal system of logic.</p>
<p>In this respect complexity theory stands apart from most mathematical disciplines, such that the apprehensions that Doron Zeilberger expresses in his recent &quot;<a href="https://sites.math.rutgers.edu/%7Ezeilberg/Opinion125.html" rel="nofollow noreferrer">Opinion 125: Now that Alan Turing turned 100-years-old, it is time to have a Fresh Look at His Seminal Contributions, that did lots of Good But Also Lots of Harm</a>&quot; arguably are well-founded.</p>
<p>Zeilberger's concerns take explicit form as the criterion <strong>Z0</strong> <span class="math-container">$\equiv $</span> ( !<strong>Q1</strong> ) &amp;&amp; ( !<strong>C0</strong> ), which is equivalent to the following criterion:</p>
<blockquote>
<p><strong>Z0:</strong>  <strong>Zeilberger's sensibility criterion</strong>  Definitions of the complexity class <em>P</em>  are called <em>Zeilberger-sensible</em> iff all languages in <em>P</em> are provably gnostic.</p>
</blockquote>
<p>At present it is not known whether <a href="https://web.archive.org/web/20130314011936/http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf" rel="nofollow noreferrer">Stephen Cook's definition of the complexity class <em>P</em></a>  is Zeilberger-sensible.</p>
<h3>Motivational considerations</h3>
<p>The definitions of &quot;gnostic&quot; and &quot;cryptic&quot; are crafted with a view toward (eventually) deciding conjectures like the following:</p>
<blockquote>
<p><strong>C1</strong>  Let <span class="math-container">$P'$</span> and <span class="math-container">$NP'$</span> be the gnostic restrictions of <span class="math-container">$P$</span> and <span class="math-container">$NP$</span> resp. Then <span class="math-container">$P' \ne NP'$</span> is either provable or refutable in PA or ZFC.</p>
<p><strong>C2</strong>  <span class="math-container">$P' \ne NP'$</span> (as explicitly proved in PA or ZFC)</p>
</blockquote>
<p>Clearly <strong>C2</strong> <span class="math-container">$\to$</span> <strong>C1</strong>, and conversely it is conceivable that a proof of the (meta) theorem <strong>C1</strong> might provide guidance toward a proof of the (stronger) theorem <strong>C2</strong>.</p>
<p>The overall motivation is the expectation/intuition/hope that for some well-tuned distinction between gnostic and cryptic TMs and languages, a proof of <strong>C1</strong> and possibly even <strong>C2</strong> might illuminate — and even have comparable practical implications to — a presumably far harder and deeper proof that <span class="math-container">$P\ne NP$</span>.</p>
<p>Juris Hartmanis was among the first complexity theorists to seriously pursue this line of investigation; see Hartmanis' monograph <em><a href="https://books.google.com/books?id=DTMrTZJH1NYC&amp;pg=PA1" rel="nofollow noreferrer">Feasible Computations and Provable Complexity Properties</a></em> (1978), for example.</p>
<h3>Nomenclatural considerations</h3>
<p>From the Oxford English Dictionary (OED) we have:</p>
<ul>
<li><p><strong>gnostic</strong> (adj)  <em>Relating to knowledge; cognitive; intellectual</em>  &quot;They [the numbers] exist in a vital, gnostic, and speculative, but not in an operative manner.&quot;</p>
</li>
<li><p><strong>cryptic</strong> (adj)  <em>Not immediately understandable; mysterious, enigmatic</em>  &quot;Instead of plain Rules useful to Mankind, they [philosophers] obtrude cruptick and dark Sentences.&quot;</p>
</li>
</ul>
<p>Apparently no Mathematical Review has previously used the word &quot;gnostic&quot; in any sense whatsoever.   However, attention is drawn to Marcus Kracht’s recent article “<a href="https://doi.org/10.1007/s10992-010-9156-0" rel="nofollow noreferrer">Gnosis</a>” (<em>Journal of Philosophical Logic</em>, MR2802332), which uses the OED sense.</p>
<p>Apparently no Mathematical Review has used the word &quot;cryptic&quot; — in its technical sense — with relation to complexity theory.  However, attention is drawn to Charles H. Bennett's article &quot;<a href="https://dl.acm.org/doi/10.5555/57249.57257" rel="nofollow noreferrer">Logical Depth and Physical Complexity</a>&quot; (in <em>The Universal Turing Machine: A Half-Century Survey</em>, 1988) which contains the passage</p>
<blockquote>
<p>Another kind of complexity associated with an object would be the difficulty,
given the object, of finding a plausible hypothesis to explain it. Objects
having this kind of complexity might be called <em>&quot;cryptic&quot;</em>: to find a
plausible origin for the object is like solving a cryptogram.</p>
</blockquote>
<h3>Considerations of naturality, openness, and difficulty</h3>
<p>The naturality of these questions illustrates the thesis of Juris Hartmanis' monograph <em><a href="https://books.google.com/books?id=DTMrTZJH1NYC&amp;pg=PA1" rel="nofollow noreferrer">Feasible Computations and Provable Complexity Properties</a></em> (1978) that:</p>
<blockquote>
<p>&quot;Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally.&quot;</p>
</blockquote>
<p>The openness and difficulty of these questions are broadly consonant with the conclusion of Lance Fortnow's review &quot;<a href="https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/abstract" rel="nofollow noreferrer">The Status of the P Versus NP Problem</a>&quot; (2009) that:</p>
<blockquote>
<p>&quot;None of us truly understands the P versus NP problem, we have only begun to peel the layers around this increasingly complex question.&quot;</p>
</blockquote>
<h3>Wiki guidance</h3>
<p>Particularly sought are definitional adjustments and proof strategies specifically relating to the questions <strong>Q1–Q3</strong> and broadly illuminating the Hartmanis-type conjectures <strong>C1–C2</strong>.</p>

CC BY-SA 3.0
2012-06-15T18:35:15.390Z
What is a positive semidefinite real number? I understand "positive semidefinite" for real symmetric matrices, but what does it mean for numbers!?
David Monniaux
CC BY-SA 3.0
2012-06-21T11:38:54.017Z
It means zero or greater (a number viewed as a 1x1 matrix).
John Sidles
CC BY-SA 3.0
2012-06-21T15:46:05.533Z
Mainly for fun, I have posted to Dick Lipton and Ken Regan's fine weblog *Gödel's Lost Letter and P=NP* a [brief account](http://rjlipton.wordpress.com/2012/06/20/can-you-hear-the-shape-of-a-quantum-computer/#comment-21081) of the  relevance of the above open questions in complexity theory to certain computation-related open questions in fundamental physics, that arise in the (wonderfully interesting) quantum physics debate between Gil Kalai and Aram Harrow that *Gödel's Lost Letter* is hosting.  In particular, Russell Impagliazzo’s *Five Worlds* of complexity theory are mentioned.
John Sidles
CC BY-SA 3.0
2012-06-22T14:07:45.230Z
Stimulated by [Timothy Chow's usage of the word "opaque"](http://cstheory.stackexchange.com/a/11707/1519), one wonders whether a better nomenclature than *gnostic* ↔ *transcendental*  might be *lucid* ↔ *opaque* ? The association is that PA or ZFC are powerful enough to "see" the runtime of TMs that efficiently accept *lucid* languages, but cannot "see" the runtimes of TMs that efficiently accept *opaque* languages.  This allows conjecture **C0** to be stated crisply as *"The complexity class P contains at least one opaque language."*  Is this alternative nomenclature better?
John Sidles
CC BY-SA 3.0
2012-06-24T15:08:50.983Z
With a view toward next week's conversion of this question to a wiki, the question of best nomenclature still is open. Reasonable names for the conjectured partition of languages in *P* (and thus *NP* ) include  *comprehensible* | *incomprehensible* languages (the original nomenclature), *gnostic* | *transcendental* languages (this question's nomenclature), *lucid* | *opaque* languages (stimulated by Timothy Chow's answer), or even *gnostic* | *cryptic* languages, such that **CO** would be "The complexity class P contains at least one cryptic language." Comments & suggestions are very welcome.
John Sidles
CC BY-SA 3.0
2012-06-25T22:15:16.190Z
Well, only three days are left before *some* answer receives the open bounty. Answers are sparser than I hoped and even comments are nearly absent. In hopes of stimulating  responses, I have posted on *Gödel’s Lost Letter and P=NP* a quote from the medieval physician/physicist [Muhammad ibn Zakariya al-Razi](http://rjlipton.wordpress.com/2012/06/24/happy-unbirthday-to-turing/#comment-21172), which explains why even modern-day practical-minded medical researchers take an interest in these issues. Even a short didactic answer (from an expert) would be welcome. And, thanks to all who contribute.
John Sidles
CC BY-SA 3.0
2012-06-28T11:00:15.520Z
The bounty period has closed; Timothy Chow's answer received the bounty.  The question has been flagged for conversion to community wiki.  Thanks are given to all who have contributed.
John Sidles
CC BY-SA 3.0
2012-06-29T16:49:49.407Z
Stimulated by a [comment posted by Scott Aaronson on his weblog *Shtetl Optimized*](http://www.scottaaronson.com/blog/?p=1064#comment-47961), a brief section titled **Zeilberger-type considerations** has been added.
John Sidles
CC BY-SA 3.0
2012-06-29T18:36:12.800Z
interesting line of investigation. have long thought that [blums speedup thm](http://en.wikipedia.org/wiki/Blum%27s_speedup_theorem) may have some connection to questions like this and/or P=?NP but havent seen that nailed down or explored anywhere. in particular, havent seen a very strict/rigorous proof that there is no language in P that is also in the class identified by blum such that the program "has no fastest algorithm"
vzn
CC BY-SA 3.0
2012-07-07T19:20:25.210Z
Edited to extent (with hyperlinks) the phrase: "In particular, **D3(a)** and **D3(b)** obstruct the *polylimiter* reduction strategies that were outlined in comments by **Peter Shor**, and by **Sasho Nikolov**, and independently by **Luca Trevisan**, and obstructs too the *polynomially clocked* reduction strategy of **Timothy Chow**."  The four now-hyperlinked commentaries are individually interesting, and in aggregate they comprise an informal survey of varying attitudes and strategies associated to natural computational reductions, both oracle-assisted and otherwise.
John Sidles
CC BY-SA 3.0
2012-09-18T15:41:48.953Z
@JohnSidles I do not think that there exists any gnostic language within P, even if NP is contained in P. We can perhaps separate them as the ones we can solve by searching and the others by a different method then searching.
Tayfun Pay
CC BY-SA 3.0
2014-03-14T13:54:07.063Z
Lance Fortnow's weblog *Computational Complexity*, in an essay "[Why do we think P NE NP?](http://blog.computationalcomplexity.org/2014/03/why-do-we-think-p-ne-np-inspired-by.html#comment-form)" has posted a discussion that touches upon these issues (it includes further links).
John Sidles
CC BY-SA 3.0
2014-04-12T09:06:38.170Z
**Remark** This wiki (as of Mar 16 '13) anticipated by more than one year, and addressed fully in its definitional framework, [**Scott Aaronson's weblog remark**](http://www.scottaaronson.com/blog/?p=1781#comment-104123) "Independence from ZFC is not a property of the language L itself, but only a property of how I described L to you!  … something like 'the subclass of P consisting of all languages that ZFC can prove are in P' doesn’t even make sense: we can only consider the set of all descriptions of languages such that ZFC can prove that the so-described language is in P!"
John Sidles
<cc.complexity-theory><polynomial-time><undecidability><independence>
Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)
John Sidles
# Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)

(Asked by: username_0 on 2012-06-11)

### Answer: not known.

The questions asked are natural, open, and apparently difficult; the question now is a community wiki.

### Overview

The question seeks to divide languages belonging to the complexity class $P$  — together with the decision Turing machines (TMs) that accept these languages — into two complementary subclasses:

* *gnostic* languages and TMs (that are feasible to validate/understand), versus
* *cryptic* languages and TMs (that are infeasible to validate/understand).

### Definitions: *gnostic* vs *cryptic* numbers, TMs, and languages

Within the axiom frameworks [PA](https://en.wikipedia.org/wiki/Peano_axioms) and [ZFC](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory), we distinguish gnostic from cryptic Turing machines and languages as follows:

> **D0**  We say that a [computable real number](https://en.wikipedia.org/wiki/Computable_number#Formal_definition) $r$ is *gnostic* iff it is associated to a non-empty set of TMs, with each TM specified in PA as an explicit list of numbers comprising valid code upon a universal TM, such that for any accuracy $\epsilon\gt0$ supplied as an input, each TM provably (in ZFC) halts with an output number $o$ that provably (in ZFC) satisfies $r-\epsilon\lt o\lt r+\epsilon$.

**Remark**  It is known that some computable reals are not gnostic (for a concrete example see [Raphael Reitzig's answer](https://cstheory.stackexchange.com/a/12168/1519) to jkff's question "[Are there non-constructive algorithm existence proofs?](https://cstheory.stackexchange.com/q/12162/1519)"). To avoid grappling with these computable-yet-awkward numbers, the restriction is imposed that runtime exponents be computable by TMs that are explicitly enumerated in PA (as contrasted with TMs implicitly specified in ZFC). For further discussion see the section **Definitional considerations** (below).

Now we seek definitions that capture the intuition that the complexity class $P$ includes a subset of *cryptic* languages to which no (gnostic) runtime exponent lower-bound can provably be assigned.

To look ahead, the concluding definition (**D5**) specifies the idea of a *canonically cryptic decision TM*, whose definition is crafted with a view toward obviating reductions that (trivially) mask cryptic computations by overlaying computationally superfluous epi-computations. The rationale and sources of this key definition are discussed later on — under the heading **Definitional Considerations** — and the contributions of comments by Timothy Chow, Peter Shor, Sasho Nikolov, and Luca Trevisan are gratefully acknowledged.

> **D1**  Given a Turing machine M that halts for all input strings, M is called *cryptic* iff the following statement is neither provable nor refutable for at least one gnostic real number $r \ge 0$:
>
> > **Statement:** M's runtime is ${O}(n^r)$ with respect to input length $n$
>
> Turing machines that are not cryptic we say are gnostic TMs.
>
> **D2**  We say that a decision Turing machine M is *efficient* iff it has a gnostic runtime exponent $r$ such that the language L that M accepts is accepted by no other TM having a gnostic runtime exponent smaller than $r$.
>
> **D3**  We say that a language L is *cryptic* iff it is accepted by **(a)** at least one Turing machine M is that is both efficient and cryptic, and moreover **(b)** no TM that is both efficient and gnostic provably accepts L.

To express **D3** another way, a language is cryptic iff the TMs that accept that language most efficiently are themselves cryptic.

> Languages that are not cryptic we say are *gnostic* languages.
>
> **D4**  We say that a cryptic TM is *strongly cryptic* iff the language it accepts is cryptic.
>
> **D5**  We say that a strongly cryptic TM is *canonically cryptic* iff it is efficient.

To express **D5** another way, every cryptic language is accepted by a set of canonically cryptic decision TMs, which are the most efficient decision TMs that accept that language.

### The questions asked

The following conjecture **C0** is natural and (apparently) open:

> **C0**  The complexity class P contains at least one cryptic language.

Three questions are asked, **Q1**–**Q3**, of which the first is:

> **Q1**  Is the **C0** conjecture independent of PA or ZFC?

Under the assumption that **C0** is true — either provably in ZFC, or as an independent axiom that is supplemental to ZFC — two further questions are natural:

> **Q2**  Can at least one cryptic language in *P* be presented concretely, that is, exhibited as a dictionary of explicit words in a finite alphabet that includes all words up to any specified length? If so, exhibit such a dictionary.
>
> **Q3**  Can at least one canonically cryptic decision TM be presented concretely, that is, as an enabling description for building a physical Turing machine that decides (in polynomial time) all the words of the dictionary of **Q2**? If so, construct such a Turing machine and by computing with it, exhibit the cryptic language dictionary of **Q2**.

### Definitional considerations

Definition **D0** implies that every gnostic real number is computable, but it is known that some computable real numbers are *not* gnostic. For examples, see answers on *MathOverflow* by [Michaël Cadilhac](https://cstheory.stackexchange.com/a/1979/1519) and [Ryan Williams](https://cstheory.stackexchange.com/a/1991/1519) and on *TCS StackExchange* by [Raphael Reitzig](https://cstheory.stackexchange.com/a/12168/1519). More generally, definitions **D0–D5** are crafted to exclude references to non-gnostic runtime exponents.

As discussed in the TCS wiki "[Does P contain incomprehensible languages?](https://cstheory.stackexchange.com/q/11570/1519)," definitions **D0–D5** ensure that every cryptic language is accepted by at least one TM that is canonically cryptic. (Note also that in the present question the word "cryptic" replaces the less descriptive word "incomprehensible" used in the wiki).

Moreover — in view of **D3(a)** and **D3(b)** — there exists no computationally trivial reduction of a canonically cryptic TM to a gnostic TM that provably recognizes the same language. In particular, **D3(a)** and **D3(b)** obstruct the *polylimiter* reduction strategies that were outlined in comments by [Peter Shor](https://cstheory.stackexchange.com/questions/11570/does-p-contain-incomprehensible-languages-tcs-community-wiki#comment31657_11570), and by [Sasho Nikolov](https://cstheory.stackexchange.com/questions/11570/does-p-contain-incomprehensible-languages-tcs-community-wiki/11575#11575), and independently by [Luca Trevisan](https://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962), and obstructs too the *polynomially clocked* reduction strategy of [Timothy Chow](https://cstheory.stackexchange.com/a/11707/1519), all of which similarly mask cryptic computations by overlaying a computationally superfluous [epi-computation](https://cstheory.stackexchange.com/questions/11570/does-p-contain-incomprehensible-languages-tcs-community-wiki#comment31708_11592).

In general, the definitions of "gnostic" and "cryptic" are deliberately tuned so as to be robust with respect to mathematically trivial reductions (and it is entirely possible that further tuning of these definitions may be desirable).

### Methodological considerations

Lance Fortnow's review "[The status of the P versus NP problem](https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/abstract)" surveys methods for establishing the independence (or otherwise) of conjectures in complexity theory; particularly desired are suggestions as to how the methods that Lance reviews might help (or not) to answer **Q1**.

It is clear that many further questions are natural. E.g., the [Hartmanis-Stearns Conjecture](https://rjlipton.wpcomstaging.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/) inspires us to ask "Do cryptic real-time multitape Turing machines exist? Is their existence (or not) independent of PA or ZFC?"

### Zeilberger-type considerations

In the event that **Q1** is answered by "yes", then oracles that decide membership in $P$ exist outside of PA or ZFC, and therefore, an essential element of modern complexity theory is (at present) not known to reside within any formal system of logic.

In this respect complexity theory stands apart from most mathematical disciplines, such that the apprehensions that Doron Zeilberger expresses in his recent "[Opinion 125: Now that Alan Turing turned 100-years-old, it is time to have a Fresh Look at His Seminal Contributions, that did lots of Good But Also Lots of Harm](https://sites.math.rutgers.edu/%7Ezeilberg/Opinion125.html)" arguably are well-founded.

Zeilberger's concerns take explicit form as the criterion **Z0** $\equiv $ ( !**Q1** ) && ( !**C0** ), which is equivalent to the following criterion:

> **Z0:**  **Zeilberger's sensibility criterion**  Definitions of the complexity class *P*  are called *Zeilberger-sensible* iff all languages in *P* are provably gnostic.

At present it is not known whether [Stephen Cook's definition of the complexity class *P*](https://web.archive.org/web/20130314011936/http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf)  is Zeilberger-sensible.

### Motivational considerations

The definitions of "gnostic" and "cryptic" are crafted with a view toward (eventually) deciding conjectures like the following:

> **C1**  Let $P'$ and $NP'$ be the gnostic restrictions of $P$ and $NP$ resp. Then $P' \ne NP'$ is either provable or refutable in PA or ZFC.
>
> **C2**  $P' \ne NP'$ (as explicitly proved in PA or ZFC)

Clearly **C2** $\to$ **C1**, and conversely it is conceivable that a proof of the (meta) theorem **C1** might provide guidance toward a proof of the (stronger) theorem **C2**.

The overall motivation is the expectation/intuition/hope that for some well-tuned distinction between gnostic and cryptic TMs and languages, a proof of **C1** and possibly even **C2** might illuminate — and even have comparable practical implications to — a presumably far harder and deeper proof that $P\ne NP$.

Juris Hartmanis was among the first complexity theorists to seriously pursue this line of investigation; see Hartmanis' monograph *[Feasible Computations and Provable Complexity Properties](https://books.google.com/books?id=DTMrTZJH1NYC&pg=PA1)* (1978), for example.

### Nomenclatural considerations

From the Oxford English Dictionary (OED) we have:

* **gnostic** (adj)  *Relating to knowledge; cognitive; intellectual*  "They [the numbers] exist in a vital, gnostic, and speculative, but not in an operative manner."
* **cryptic** (adj)  *Not immediately understandable; mysterious, enigmatic*  "Instead of plain Rules useful to Mankind, they [philosophers] obtrude cruptick and dark Sentences."

Apparently no Mathematical Review has previously used the word "gnostic" in any sense whatsoever. However, attention is drawn to Marcus Kracht’s recent article “[Gnosis](https://doi.org/10.1007/s10992-010-9156-0)” (*Journal of Philosophical Logic*, MR2802332), which uses the OED sense.

Apparently no Mathematical Review has used the word "cryptic" — in its technical sense — with relation to complexity theory. However, attention is drawn to Charles H. Bennett's article "[Logical Depth and Physical Complexity](https://dl.acm.org/doi/10.5555/57249.57257)" (in *The Universal Turing Machine: A Half-Century Survey*, 1988) which contains the passage

> Another kind of complexity associated with an object would be the difficulty,
> given the object, of finding a plausible hypothesis to explain it. Objects
> having this kind of complexity might be called *"cryptic"*: to find a
> plausible origin for the object is like solving a cryptogram.

### Considerations of naturality, openness, and difficulty

The naturality of these questions illustrates the thesis of Juris Hartmanis' monograph *[Feasible Computations and Provable Complexity Properties](https://books.google.com/books?id=DTMrTZJH1NYC&pg=PA1)* (1978) that:

> "Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally."

The openness and difficulty of these questions are broadly consonant with the conclusion of Lance Fortnow's review "[The Status of the P Versus NP Problem](https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/abstract)" (2009) that:

> "None of us truly understands the P versus NP problem, we have only begun to peel the layers around this increasingly complex question."

### Wiki guidance

Particularly sought are definitional adjustments and proof strategies specifically relating to the questions **Q1–Q3** and broadly illuminating the Hartmanis-type conjectures **C1–C2**.

**Tags:** cc.complexity-theory, polynomial-time, undecidability, independence
> **Comments:**
> **username_1**: What is a positive semidefinite real number? I understand "positive semidefinite" for real symmetric matrices, but what does it mean for numbers!?  
> **username_0**: It means zero or greater (a number viewed as a 1x1 matrix).  
> **username_0**: Mainly for fun, I have posted to Dick Lipton and Ken Regan's fine weblog *Gödel's Lost Letter and P=NP* a [brief account](http://rjlipton.wordpress.com/2012/06/20/can-you-hear-the-shape-of-a-quantum-computer/#comment-21081) of the  relevance of the above open questions in complexity theory to certain computation-related open questions in fundamental physics, that arise in the (wonderfully interesting) quantum physics debate between Gil Kalai and Aram Harrow that *Gödel's Lost Letter* is hosting.  In particular, Russell Impagliazzo’s *Five Worlds* of complexity theory are mentioned.  
> **username_0**: Stimulated by [Timothy Chow's usage of the word "opaque"](http://cstheory.stackexchange.com/a/11707/1519), one wonders whether a better nomenclature than *gnostic* ↔ *transcendental*  might be *lucid* ↔ *opaque* ? The association is that PA or ZFC are powerful enough to "see" the runtime of TMs that efficiently accept *lucid* languages, but cannot "see" the runtimes of TMs that efficiently accept *opaque* languages.  This allows conjecture **C0** to be stated crisply as *"The complexity class P contains at least one opaque language."*  Is this alternative nomenclature better?  
> **username_0**: With a view toward next week's conversion of this question to a wiki, the question of best nomenclature still is open. Reasonable names for the conjectured partition of languages in *P* (and thus *NP* ) include  *comprehensible* | *incomprehensible* languages (the original nomenclature), *gnostic* | *transcendental* languages (this question's nomenclature), *lucid* | *opaque* languages (stimulated by Timothy Chow's answer), or even *gnostic* | *cryptic* languages, such that **CO** would be "The complexity class P contains at least one cryptic language." Comments & suggestions are very welcome.  
> **username_0**: Well, only three days are left before *some* answer receives the open bounty. Answers are sparser than I hoped and even comments are nearly absent. In hopes of stimulating  responses, I have posted on *Gödel’s Lost Letter and P=NP* a quote from the medieval physician/physicist [Muhammad ibn Zakariya al-Razi](http://rjlipton.wordpress.com/2012/06/24/happy-unbirthday-to-turing/#comment-21172), which explains why even modern-day practical-minded medical researchers take an interest in these issues. Even a short didactic answer (from an expert) would be welcome. And, thanks to all who contribute.  
> **username_0**: The bounty period has closed; Timothy Chow's answer received the bounty.  The question has been flagged for conversion to community wiki.  Thanks are given to all who have contributed.  
> **username_0**: Stimulated by a [comment posted by Scott Aaronson on his weblog *Shtetl Optimized*](http://www.scottaaronson.com/blog/?p=1064#comment-47961), a brief section titled **Zeilberger-type considerations** has been added.  
> **username_2**: interesting line of investigation. have long thought that [blums speedup thm](http://en.wikipedia.org/wiki/Blum%27s_speedup_theorem) may have some connection to questions like this and/or P=?NP but havent seen that nailed down or explored anywhere. in particular, havent seen a very strict/rigorous proof that there is no language in P that is also in the class identified by blum such that the program "has no fastest algorithm"  
> **username_0**: Edited to extent (with hyperlinks) the phrase: "In particular, **D3(a)** and **D3(b)** obstruct the *polylimiter* reduction strategies that were outlined in comments by **Peter Shor**, and by **Sasho Nikolov**, and independently by **Luca Trevisan**, and obstructs too the *polynomially clocked* reduction strategy of **Timothy Chow**."  The four now-hyperlinked commentaries are individually interesting, and in aggregate they comprise an informal survey of varying attitudes and strategies associated to natural computational reductions, both oracle-assisted and otherwise.  
> **username_3**: @JohnSidles I do not think that there exists any gnostic language within P, even if NP is contained in P. We can perhaps separate them as the ones we can solve by searching and the others by a different method then searching.  
> **username_0**: Lance Fortnow's weblog *Computational Complexity*, in an essay "[Why do we think P NE NP?](http://blog.computationalcomplexity.org/2014/03/why-do-we-think-p-ne-np-inspired-by.html#comment-form)" has posted a discussion that touches upon these issues (it includes further links).  
> **username_0**: **Remark** This wiki (as of Mar 16 '13) anticipated by more than one year, and addressed fully in its definitional framework, [**Scott Aaronson's weblog remark**](http://www.scottaaronson.com/blog/?p=1781#comment-104123) "Independence from ZFC is not a property of the language L itself, but only a property of how I described L to you!  … something like 'the subclass of P consisting of all languages that ZFC can prove are in P' doesn’t even make sense: we can only consider the set of all descriptions of languages such that ZFC can prove that the so-described language is in P!"  

---

## 2 answers

### Answer by username_4 on 2012-06-12. Score: 27

I think that there is a fundamental underlying difficulty with the question you are asking here (and that you asked in your related question about incomprehensible languages).

Roughly speaking, it seems you're seeking a language $L$ such that

> $L\in P$ but ZFC doesn't know that $L\in P$.

To understand the difficulties with your question, I think you must first appreciate that there's a fundamental difference between *intensional* and *extensional* definitions of a language $L$. Extensionally, $L$ is determined by what words are or are not members of $L$. That is, two languages $L$ and $L'$ are extensionally equal if and only if they contain exactly the same words as members. In contrast, an *intensional* definition of $L$ describes some *conditions* for a word to be in $L$. A Turing machine that accepts $L$, or a first-order formula $\phi(x)$ that holds if and only if $x\in L$, can be thought of as an intensional definition of $L$.

The point is that every $L$ that is (extensionally) in $P$ admits a description that is extremely straightforward, because $P$ is a so-called "syntactic" complexity class. Namely, just take a *polynomially clocked* Turing machine, that terminates in exactly the amount of time desired. Any "reasonable" system for doing mathematics, such as PA or ZFC, is going to be able to prove that $L\in P$ if you use this straightforward description of $L$.

So if you want to confuse ZFC, you're going to have to come up with some (intensional) description of $L$ that is "too complicated" for ZFC to recognize as being equivalent to the straightforward description of $L$. This is possible, but in some sense it's too easy to be interesting. All you have to do is to take something that we know that ZFC doesn't understand (e.g., its own consistency) and mix it up with the definition of $L$ somehow. For example, here's a description of a set of integers:

> $x$ is even and $x$ doesn't encode a proof that ZFC is inconsistent.

Assuming ZFC is consistent, the above formula defines the set of even integers, but ZFC doesn't know it. With a bit more tinkering, we can easily get a description of the set of even integers that ZFC won't be able to prove is in $P$.

The upshot is that if you're hoping that the reason it's hard to prove that $P\ne NP$ is that there are languages in $P$ that are "too complicated" for us to reason about, then I think you're barking up the wrong tree. Extensionally, every language in $P$ is in $P$ for trivial reasons. You can muddy the waters by playing around with impossibly opaque descriptions of languages in $P$, but this is a general trick that has nothing to do with $P$ in particular, so I don't think it yields much insight.

> **Comments:**
> **username_0**: Timothy, thank you for this fine essay. Do I appreciate correctly, though, that the standard definition of *P* — per Arora & Barak *Computational Complexity: a Modern Approach* and/or Hartmanis *Feasible Computations and Provable Complexity Properties*, or the Millenium Prize statement — is *NOT* extensional? Yet perhaps some problems would be more tractable if the definition of *P* were suitably amended, on grounds that (per Hartmanis) "We need to explore further how our `world view' of the complexity of algorithms has to be changed if we consider only provable properties of algorithms."  
> **username_5**: @JohnSidles the standard definition of P is "the set of all languages that can be decided by some polytime TM". how a language is defined (intensionally or extensionally) does not enter the picture at all: it only enters the picture once we need to prove that some particular machine accepts some particular language.  
> **username_0**: Sasho, the thrust of Timothy Chow's answer (as I read it) is  "If we define *P* *extensionally*, then deciding membership in *P* is trivial."  The thrust of your comment (as I read it) is that by present-day convention, "*P* is defined *intensionally*." Combining these two observations leads us to appreciate Hartmanis' remark: "Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally."  And so we naturally wonder, how the definition of *P* might be varied, so as to more readily prove good theorems.  
> **username_4**: @John: I introduced the terms "intensional" and "extensional" for expository purposes. The terms aren't formally used in mathematics. In particular, I'm not sure that it helps to apply these adjectives to "the standard definition of $P$." However, your other point, that exploring different ways of defining $P$ might be fruitful, is one I would agree with.  
> **username_0**: Yes, the definitions of *gnostic* and *transcendental* are purposed with a view toward (eventually) proving statements like the following:     **Theorem**  Let *P'* and *NP'* be the gnostic restrictions of *P* and *NP* resp.  Then *P' ≠ NP'*.      For a suitably broad-yet-natural definition of "gnostic", such a proof might be comparably illuminating, and have comparable practical implications, to a (presumably far harder?) proof that *P ≠ NP*.  AFAICT, Juris Hartmanis was among the first complexity theorists to seriously pursue this line of investigation.  
> **username_0**: Thank you @TimothyChow. After reflecting on both your answer and Ricky Demer's (below), **D1** has been amended by the substitution *real* -> [*computable real*](http://en.wikipedia.org/wiki/Computable_number), to close the loophole that Ricky identified, and also to mitigate your concern that *P*'s definition is "impossibly opaque*. However, the latter concern cannot be wholly mitigated, because the the question's motivation is the Hartmanis-style intuition that even the [standard complexity-theoretic definitions of *P*](http://www.claymath.org/millennium/P_vs_NP/) are "impossibly opaque."  
> **username_0**: In preparation for conversion to community Wiki, and with due regard to Timothy Chow's distinction between *intensional* and *extensional*, and with regard also to closing Ricky Demer's loophole, a definition **DO** has been added which restricts  run-time exponents to the set of computable numbers *r* that are defined intensionally, that is, by "a Turing machine finitely given that provably halts and provably converges to a real number that is r by definition."  Thanks are given for these suggestions!  
> **username_0**: Thank you, Timothy Chow.  Because you have the highest-rated answer, I have awarded you the bounty.  In particular, your answer greatly influenced both the starting definition **DO** and final nomenclature of *gnostic* verus *cryptic*.  I have flagged the question for conversion to community wiki.  

---

### Answer by username_6 on 2012-09-02. Score: 1

Definition 1: Let $x\_n := 2 + \sum\_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$. Clearly, we can build a Turing machine which, given $n$, will compute $x\_n$. Also the $x\_n$ converge to $x := 2 + \sum\_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$.

So $x$ is a gnostic real, which is equal to 2 if and only if $\bf{ZF}$ is consistent.

Definition 2: For any gnostic real $x > 1$, let $M'\_x$ be a Turing machine which takes an index $n$ of a Turing machine $N$ and an input $s$, simulates $N$ on $s$ for $|s|^x/\log(|s|)$ steps (this function is time-constructible, because $x$ is gnostic), and inverts the result. By the Recursion Theorem, we may choose $M\_x$ to be $M'\_x$ with a fixed index of $M\_x$ as its first input. Then a standard argument (the Time Hierarchy Theorem) shows that $M\_x$ has runtime $\mathcal O(|s|^y)$ precisely when $y\ge x$, and that $M\_x$ is efficient for its language.

Therefore, for $x$ as in Definition 1, $M\_x$ will run in time $\mathcal O(|s|^2)$ precisely if $x = 2$, ie if $\bf{ZF}$ is consistent; moreover this fact will itself be provable in $\bf ZF$. So [if $\bf ZF$ is consistent], $M\_x$ is a [strongly and canonically] cryptic machine, and this fact will be provable in $\bf ZF + Con(\bf ZF)$.

However, $\bf ZF + \not Con(\bf ZF)$ proves that all languages in $\bf P$ are gnostic, since it proves that $\bf ZF$ proves that every language has runtime $\mathcal O(|s|^z)$ for every $z$. So it is undecidable in $\bf ZF$ whether any cryptic language exists.

To answer your second and third questions, the definition I gave above for $M\_x$ is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.

> **Comments:**
> **username_0**: Ben, thank you for this carefully reasoned and thoughtfully phrased answer.  It will take a few days to digest it ... I hope to comment in a week or so!  

---

