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

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.