Recognizing proof of membership easier than recognizing

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 02/15/05 

Date: Tue, 15 Feb 2005 19:29:36 +0000 (UTC)

The theory of NP-completeness gives us reason to believe there are
problems where the complexity of solving the problem directly is greater
than the complexity of recognizing a correct answer. Here complexity =
worst-case running time.

Is there any language-theoretic analogue, where (say) complexity = height
in the Chomsky hierarchy? For example, is there any language L that comes
with a proof of membership that can be checked by a finite-state machine,
but where L cannot itself be recognized by a finite-state machine?

Perhaps I should be more precise. Let S,T be alphabets, with S subset T.
Let erase:T^* -> S^* denote the mapping that erases all symbols not in
S from its input. Say that the language L subseteq S^* is checkable by
FSAs if there exists a computable function f:S^* -> T^* and a finite-state
machine M such that:
  (Soundness:) For all y in T^*, if M accepts on input y, then
    erase(y) in L.
  (Completeness:) For all x in L, M accepts on input f(x), and
    moreover erase(f(x)) = x. For all x in S^* \ L, M rejects on
    input f(x).
Does there exist any language L that is checkable by FSAs but is not
recognizable by FSAs (i.e., is not regular)?

This is just one example of what it might mean for there to be some
language where the complexity of recognizing is greater than the
complexity of checking proofs of membership. Of course, there are
natural generalizations of the above precise problem statement that would
also quality. For instance, we could replace erase by any rational map
(i.e., anything computable by a finite-state transducer). Or, we could
use any other class of machines in place of FSAs. For instance, we could
ask whether there are languages checkable by PDAs but not recognizable
by PDAs.

Does anyone know of any results or relevant work in this area?

Relevant Pages

  • Re: Recognizing proof of membership easier than recognizing
    ... > language where the complexity of recognizing is greater than the ... > complexity of checking proofs of membership. ... computation history is valid, they can in essence verify any language ...
    (comp.theory)
  • Berlinski paper presented 1985 at Applied systems analysis
    ... Complexity, Language and Life: Mathematical Approaches, ... This paper explores the idea that life comprises a language-like ...
    (talk.origins)
  • Re: Programmers unpaid overtime.
    ... The cache solution's execution time formula is a function of the total ... The campaign is part of what I consider the deprivation of language by ... You can't, in other words, document, and management wonders why ... >> complexity with a few benchmarks. ...
    (comp.programming)
  • Re: Kolmogorov complexity and logical languages
    ... I have looked into the Kolmogorov thingie a bit. ... it is hard to say that one language is more complex than another. ... with linguistics. ... instead of the more abstract notion of complexity. ...
    (sci.lang)
  • Re: Responding to a challenge
    ... > Why do you think such complexity actually exists? ... I would think it noncontroversial that language itself serves the ... were to create an artificial dialect of English in which all verbs ... one an artificial dialect of English with regular pluralization. ...
    (sci.lang)