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

On 5/11/2024 12:00 AM, 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(..)?

 
In normal CS Speak:
 
Problems have complexity: essentially defined as the worst case behavior
as problem size grows. One then minimizes this over all algorithms that
"solve" the problem as specified.
 
An Algorithm has runtime: essentially what is the worst case runtime for
each problem size.
 
You seem to be asking for complexity of an algorithm. It's easy to see
that the above algorithm is exponential (or worse depending on f). One
can assume that f, in worst case, has runtime that is a polynomial in
the length of n. However, these observations say absolutely nothing
about the complexity of the SAT problem.
--
Jeff Barnett