Re: Problems in NP with infinite number of possibiltiies to check?

In article <d4bmoj$7cr$1@xxxxxxxxxxxxxxxxxxxx>,
Richard Hayden <rah03@xxxxxxxxxxxxxxxxxxx> wrote:
>Are problems where you are trying to find if a possibility for something
>exists out of a infinite number of possibilites in NP if checking
>whether or not they are a possibility is in P?

I'm not sure exactly what your question is, but under most construals that I
can think of, the answer is no.

For example, suppose I ask whether a given diophantine equation has a
solution. If you give me a candidate solution, then I can rapidly check
whether it's a solution. However, the original problem is undecidable.
--
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: Wave Function of the Universe?
    ... Much of brain processing is indeed concerned with producing simple continuous models of a messy reality. ... The line needs no infinite limit to be grasped, though the mathematical definition might need it. ... all the mathematical problems of infinities dissappear ... all differential equations basic to all sciences, the calculus that made Newton famous and physics the 'hard' science it is today. ...
    (sci.physics.research)
  • Re: abundance of irrationals!)
    ... because N is said to be infinite. ... Please repeat your proof ... Regards, WM ... Prev by Date: ...
    (sci.math)
  • Re: question about categoricity
    ... constant symbols. ... let our theory be the consequences of the infinite ... does Chris's trick work in this case? ... Prev by Date: ...
    (sci.logic)
  • Re: Least primes in arithmetic progressions
    ... Dirichlet's theorem states that the series a*n+b contains an infinite number ... The above may not represent the opinions of my employer. ... Prev by Date: ...
    (sci.math)
  • Re: Prolife Question
    ... of the Galileo Case," address to the Pontifical Academy of Sciences, ... I would guess the Holy Father explained that in his Lessons. ... if it's infinite, a center doesn't have any particular meaning. ... including the idea that the universe was infinite. ...
    (alt.religion.christian.roman-catholic)