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

wij <wyniijj5@gmail.com> writes:

On Thu, 2024-05-16 at 00:23 -0600, Jeff Barnett wrote:

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

>
You said "...the above algorithm is exponential". But, it is just an
assertion.

Yes, it is "just" an assertion, but it has the merit of being correct.

Some observations...  First, "complexity" is asymptotic so it can't
apply to your apparent C (or C++) code, but we can imagine an unbounded
version not in C.  Second, complexity requires a measure.  In your
example, a good measure would be "the number of calls to f".  Then we
don't have to keep qualifying everything with "depending on the cost of
f".  Third, complexity is a function of some quantity and I think it is
this that has got you confused by Jeff's answer.

The algorithm that satisfies some function by trying all values from 0
to n is linear in n and therefore exponential /in the length/ of n.

I won't prove either assertion since I can't imagine what you would
consider to be a proof.  A typical undergraduate would be able to prove
this in a matter of minutes, so the fact that you can't suggests that
there is a fundamental problem with your knowledge and understanding
(but see below if you really want to proof).

The question Q asks for the complexity of the problem sat(..) tries to solve
and its supporting proof.

As Jeff explained, that question is muddled.  There is no explicit
problem (in the CS meaning of the term) given in your example.  However,
the asymptotic run-time of the algorithm implied by your code sketch can
be discussed (as I have done).

[If you insist on a proof, I will too: give me your own proof of the
asymptotic run-time of any algorithm you like (your choice) and I'll
give a matching one for you your trivial algorithm.  I need to see what
sort of argument you consider to be "a proof" before I spend any time on
something you can turn round and reject as not being "a proof".]

--
Ben.