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

On Mon, 2024-05-13 at 18:33 +0800, wij wrote:

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?
 
 

The answer of the problem may be looked 'obvious' but not. The answer other
than NP may also prove the P-NP problem! But, even so, I still would like to
see the proof for the easier answer NP. Sadly, no one STILL can do this so far.
Is that (lots of excuses or playing smart) all the people in comp.theory can do?