Re: Problems in NP with infinite number of possibiltiies to check?
- From: "jarfo" <jarfo@xxxxxxxxx>
- Date: 23 Apr 2005 08:31:46 -0700
No.
The additional input to the P verifier (certificate or proof) is
(polynomially) bounded, so you can have only a finite number of
different 'certificates' to explore. In other words, the verifier can
only read a finite number of bits in its time bound.
If for the P verifier time-bounded by n^k the the number of
possibilities to check is bounded by 2^(n^k)
.
- Follow-Ups:
- Re: Problems in NP with infinite number of possibiltiies to check?
- From: Patricia Shanahan
- Re: Problems in NP with infinite number of possibiltiies to check?
- References:
- Problems in NP with infinite number of possibiltiies to check?
- From: Richard Hayden
- Problems in NP with infinite number of possibiltiies to check?
- Prev by Date: Problems in NP with infinite number of possibiltiies to check?
- Next by Date: Re: Problems in NP with infinite number of possibiltiies to check?
- Previous by thread: Problems in NP with infinite number of possibiltiies to check?
- Next by thread: Re: Problems in NP with infinite number of possibiltiies to check?
- Index(es):