up vote 12 down vote favorite
9

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 and ZFC, we distinguish gnostic from cryptic Turing machines and languages as follows:

D0  We say that a computable real number $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 to jkff's question "Are there non-constructive algorithm existence proofs?"). 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 and Ryan Williams and on TCS StackExchange by Raphael Reitzig. 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?," 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, and by Sasho Nikolov, and independently by Luca Trevisan, and obstructs too the polynomially clocked reduction strategy of Timothy Chow, all of which similarly mask cryptic computations by overlaying a computationally superfluous epi-computation.

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" 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 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" 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  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 (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” (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" (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 (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" (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.

share|cite|improve this question
    
I'm not sure what you mean in Q3; it seems like the input representation would heavily influence exactly what TMs work. – Ricky Demer Jun 11 '12 at 3:57
2  
What is a positive semidefinite real number? I understand "positive semidefinite" for real symmetric matrices, but what does it mean for numbers!? – David Monniaux Jun 15 '12 at 18:35
    
It means zero or greater (a number viewed as a 1x1 matrix). – John Sidles Jun 21 '12 at 11:38
1  
interesting line of investigation. have long thought that blums speedup thm 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 Jun 29 '12 at 18:36
1  
@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 Sep 18 '12 at 15:41
up vote 26 down vote
+250

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.

share|cite|improve this answer
    
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 Jun 12 '12 at 15:53
2  
@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 Jun 12 '12 at 17:28
1  
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 Jun 12 '12 at 17:47
1  
@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 Jun 12 '12 at 18:14
    
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 Jun 12 '12 at 18:38
up vote 8 down vote

Q1: $\:$ No
Q2: $\:$ Yes, at-least-two-1s-in-binary


Lemma: $\:$ Every TM with a computable runtime exponent that is at least 1 is transcendental.

Proof:
Let A and B be recursively inseparable sets. $\:$ Let $M_0$ be a Turing machine that enumerates A. $\:$ Let $M_1$ be a Turing machine that enumerates B. $\;\;$ For any Turing machine with computable runtime exponent r, when $\langle r_0,r_1,r_2,r_3,...\rangle$ is defined as [if $M_0$ accepts m in exactly s steps then r+(1/t), if $M_1$ accepts m in exactly s steps then r-(1/t), otherwise r], every $r_m$ is non-negative and computable and one always has [if $\:m\in A\:$ then D1's statement is true] and [if $\:m\in B\:$ then D1's statement is false]. $\;\;$ For any Turing machine with computable runtime exponent r, when $\langle r_0,r_1,r_2,r_3,...\rangle$ is defined as above, since A and B are recursively inseparable, there is at least one m for which D1's statement with $r_m$ is neither provable nor refutable. $\:$ Therefore the Turing machine is transcendental.


Definition:
at-least-two-1s-in-binary is the set of non-negative integers whose binary
representation has at least two 1s. $\:$ (bet you never would have guessed ^_^)

Definition:
M is the Turing machine that scans the binary representation of
its input, accepts if it finds at least two 1s, and rejects otherwise.

Obviously, M decides at-least-two-1s-in-binary and has runtime exponent 1, and no other Turing machine with a smaller runtime exponent also decides at-least-two-1s-in-binary.
Trivially, $\: 1\leq 1 \:$ and $1$ is computable. $\;\;$ By the Lemma, M is efficient and transcendental.
These mean at-least-two-1s-in-binary is also transcendental.

Therefore TPCCC is a theorem of PA (and ZFC), and
at-least-two-1s-in-binary is a concrete transcendental language.

share|cite|improve this answer
    
Ricky, thank you very much! It will take a couple of days to contemplate your ingenious "at-least-two-1s-in-binary" (ALT1siB) language and the TM that accepts it ... there are considerations of naturality that D1-5 are (hopefully) tuned to ensure, and that (hopefully) ALT1siB respects. Especially sought are intuitions regarding "What does ALT1siB teach us about complexity?" If you care to offer remarks in this regard, they would be gratefully appreciated. – John Sidles Jun 11 '12 at 12:37
3  
(You hopefully realize this, but) The only thing I'm using about ALT1siB is that it has exactly linear complexity, so it doesn't teach us anything about complexity. $\:$ What the lemma teaches us is that most natural Turing machines are transcendental. $\;\;$ – Ricky Demer Jun 11 '12 at 18:18
    
Ricky, I agree narrowly with your ingenious construction ... to the extent that we are pursuing Hartmanis-style naturality, the construction points to a loophole that requires definition-tuning. So what I'm thinking about is the most natural repair --- possibly (for example) requiring the runtime exponent $r$ to be neither provable nor refutable within a finite interval. This would correspond more closely to practical problems that arise naturally in engineering, and amounts to wondering "Does there exist a natural definition of transcendental languages?" which is a tough question. – John Sidles Jun 11 '12 at 20:17
    
Hmmm ... to put it another way, since our definition of transcendental is so broad that (per your lemma) even TM's that we (think we) understand OK -- that is, TM's that we regard as gnostic -- are in fact transcendental, then the definition of "transcendental" needs to be (hopefully minimally) restricted. Example: we wish to respect our common-sense intuition that TMs that decide primality via the AKS primality test be gnostic not transcendental. Your answer shows that a (hopefully minor) definitional tuning is needed ... but what? – John Sidles Jun 11 '12 at 22:23
1  
Ricky, I wonder whether you would mind editing your answer to give explicit definitions for m, s, and t. As it stands, the definitions of these numbers have to be guessed, and I am by no means confident that I have guessed correctly. In particular, do I understand correctly that changing "real" to "rational" in D1 would close the loophole that your post (AFAICT) points out, such that under the amended D1 at least some TMs are gnostic? – John Sidles Jun 19 '12 at 23:59
up vote 1 down vote

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.

share|cite|improve this answer
    
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 Sep 6 '12 at 15:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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