Re: What is the complexity classification of sat(..) ?

On Mon, 2024-05-13 at 07:00 +0200, immibis wrote:

On 11/05/24 08:00, wij wrote:

  typedef unsigned int UInt;
  typedef bool (*Func)(UInt);
 
  // [Ret] true, if ∃c, 0<=c<=n, f(c)==1 and f is a P-time function.
  //       false, otherwise.
  //
  bool sat(Func f, UInt n) {
    for(Uint c=0; c<=n; ++c) {
      if(f(c)) return true;
    }
    return false;
  }
 
  Q: If it is NPC, what is the proof? If it it not, what is the complexity
     classification of sat(..)?
 
 

 
If UInt is a variable length integer, the amount of time that 'sat'
takes to run is usually proportional to 2 to the power of the size of
its input.

Sorry, there is ambiguity. The problem should be:

 typedef unsigned int UInt;    // arbitrary precision
 typedef bool (*Func)(UInt);

 [Problem] Given a P-time function Func f and a UInt variable n, compute whether
           or not there exists a value c such that 0<=c<=n, f(c)==1..

 Q: Is [Problem] a NP(or NPC) problem? If not, what the classification is it?