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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 13/05/24 12:33, 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?

Depending on f, it could be NP with respect to the size of the input.
Sometimes it won't be (e.g. when f always returns true or f(0) always
returns true).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 13/05/24 23:49, immibis wrote:

On 13/05/24 12:33, 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?

Depending on f, it could be NP with respect to the size of the input. Sometimes it won't be (e.g. when f always returns true or f(0) always
returns true).

(this means the problem is NP if f is unknown, even though it's not NP
for some values of f, like how checking if a number is a square is in P
(I think) if the number is unknown, even though checking if 4 is a
square is even better - it's constant time)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

T24gNS8xMS8yMDI0IDEyOjAwIEFNLCB3aWogd3JvdGU6DQo+ICAgdHlwZWRlZiB1bnNpZ25l ZCBpbnQgVUludDsNCj4gICB0eXBlZGVmIGJvb2wgKCpGdW5jKShVSW50KTsNCj4gDQo+ICAg Ly8gW1JldF0gdHJ1ZSwgaWYg4oiDYywgMDw9Yzw9biwgZihjKT09MSBhbmQgZiBpcyBhIFAt dGltZSBmdW5jdGlvbi4NCj4gICAvLyAgICAgICBmYWxzZSwgb3RoZXJ3aXNlLg0KPiAgIC8v DQo+ICAgYm9vbCBzYXQoRnVuYyBmLCBVSW50IG4pIHsNCj4gICAgIGZvcihVaW50IGM9MDsg Yzw9bjsgKytjKSB7DQo+ICAgICAgIGlmKGYoYykpIHJldHVybiB0cnVlOw0KPiAgICAgfQ0K PiAgICAgcmV0dXJuIGZhbHNlOw0KPiAgIH0NCj4gDQo+ICAgUTogSWYgaXQgaXMgTlBDLCB3 aGF0IGlzIHRoZSBwcm9vZj8gSWYgaXQgaXQgbm90LCB3aGF0IGlzIHRoZSBjb21wbGV4aXR5 DQo+ICAgICAgY2xhc3NpZmljYXRpb24gb2Ygc2F0KC4uKT8NCg0KSW4gbm9ybWFsIENTIFNw ZWFrOg0KDQpQcm9ibGVtcyBoYXZlIGNvbXBsZXhpdHk6IGVzc2VudGlhbGx5IGRlZmluZWQg YXMgdGhlIHdvcnN0IGNhc2UgYmVoYXZpb3IgDQphcyBwcm9ibGVtIHNpemUgZ3Jvd3MuIE9u ZSB0aGVuIG1pbmltaXplcyB0aGlzIG92ZXIgYWxsIGFsZ29yaXRobXMgdGhhdCANCiJzb2x2 ZSIgdGhlIHByb2JsZW0gYXMgc3BlY2lmaWVkLg0KDQpBbiBBbGdvcml0aG0gaGFzIHJ1bnRp bWU6IGVzc2VudGlhbGx5IHdoYXQgaXMgdGhlIHdvcnN0IGNhc2UgcnVudGltZSBmb3IgDQpl YWNoIHByb2JsZW0gc2l6ZS4NCg0KWW91IHNlZW0gdG8gYmUgYXNraW5nIGZvciBjb21wbGV4 aXR5IG9mIGFuIGFsZ29yaXRobS4gSXQncyBlYXN5IHRvIHNlZSANCnRoYXQgdGhlIGFib3Zl IGFsZ29yaXRobSBpcyBleHBvbmVudGlhbCAob3Igd29yc2UgZGVwZW5kaW5nIG9uIGYpLiBP bmUgDQpjYW4gYXNzdW1lIHRoYXQgZiwgaW4gd29yc3QgY2FzZSwgaGFzIHJ1bnRpbWUgdGhh dCBpcyBhIHBvbHlub21pYWwgaW4gDQp0aGUgbGVuZ3RoIG9mIG4uIEhvd2V2ZXIsIHRoZXNl IG9ic2VydmF0aW9ucyBzYXkgYWJzb2x1dGVseSBub3RoaW5nIA0KYWJvdXQgdGhlIGNvbXBs ZXhpdHkgb2YgdGhlIFNBVCBwcm9ibGVtLg0KLS0gDQpKZWZmIEJhcm5ldHQNCg0K

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)