Re: Can EXPTIME and NP be separated via diagonalization?

In article <59180830-935b-495a-b3f4-6b007b117e51@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
If my argument is correct, this means that there is no algorithm that
decides membership of a language in NP.

It's not clear what exactly you mean by the problem of deciding whether a
given language is in NP. A language is (usually) an infinite set, so you
can't provide it directly as input to a computer program. I'm guessing
that you're representing the language via some kind of *finite description*
of the language. But what kind of finite description do you have in mind?
An arbitrary Turing machine? But we know by Rice's theorem that we can't
determine *any* nontrivial property of the language accepted by a given
machine, let alone the property of being in NP. So maybe you have some
other finite description in mind?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: A request for information please.
    ... Could language explain our intelligence? ... with instincts! ... not possible without possessing consciousness or a mind. ... But Pi is not considered random even though it has no pattern because ...
    (comp.ai.philosophy)
  • Re: Josef Fritzl Raped Daughter in Front of Children
    ... learning another language difficult. ... surviving children from the cellar (the oldest isn't expected to ... her father kept her chained in the basement from ... anything running through her mind at the moment came ...
    (alt.true-crime)
  • Re: My favorite haiku:
    ... translatable due to being intrinsic tpo language. ... only acting like you *are* the authority on language, ... It's what my mind does to me, ... believe your feelings rather than your rational mind. ...
    (alt.gathering.rainbow)
  • Re: Against Behaviorism
    ... behaviors, such as running really fast or being able to jump high or holding ... what humans do with language, vision, etc, is very different. ... therefore provide the same functionality. ... I am not a fundamental physicalist, but enough so that the mind ...
    (comp.ai.philosophy)
  • Re: SUR, HOR,DEL,GON,UM...
    ... the sun. ... Later on, I added the other sun god, Hor ... decorated and self-propelled by human or divine power of mind. ... have been part of the language creation process. ...
    (sci.lang)