Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: What is the complexity classification of sat(..) ?
Date: Thu, 16 May 2024 15:10:55 +0800
Organization: A noiseless patient Spider
Lines: 49
Message-ID: <6e5dd99246a10aa8c04f05512441c3de49071976.camel@gmail.com>
References: <75e1b41e7f0205e6cafea3057cd6331e39536449.camel@gmail.com>
	 <v248of$1dplu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Thu, 16 May 2024 09:10:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9c38fad8ce4af038990136c28b60a104";
	logging-data="1509720"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/zJZZE4vG3ir2uklv4pdCW"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:ffLHCCRFSgwNoZP8ub9ZXGRIEJg=
In-Reply-To: <v248of$1dplu$1@dont-email.me>
Bytes: 2750

On Thu, 2024-05-16 at 00:23 -0600, Jeff Barnett wrote:
> On 5/11/2024 12:00 AM, wij wrote:
> > =C2=A0 typedef unsigned int UInt;
> > =C2=A0 typedef bool (*Func)(UInt);
> >=20
> > =C2=A0 // [Ret] true, if =E2=88=83c, 0<=3Dc<=3Dn, f(c)=3D=3D1 and f is =
a P-time function.
> > =C2=A0 //=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 false, otherwise.
> > =C2=A0 //
> > =C2=A0 bool sat(Func f, UInt n) {
> > =C2=A0=C2=A0=C2=A0 for(Uint c=3D0; c<=3Dn; ++c) {
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if(f(c)) return true;
> > =C2=A0=C2=A0=C2=A0 }
> > =C2=A0=C2=A0=C2=A0 return false;
> > =C2=A0 }
> >=20
> > =C2=A0 Q: If it is NPC, what is the proof? If it it not, what is the co=
mplexity
> > =C2=A0=C2=A0=C2=A0=C2=A0 classification of sat(..)?
>=20
> In normal CS Speak:
>=20
> Problems have complexity: essentially defined as the worst case behavior=
=20
> as problem size grows. One then minimizes this over all algorithms that=
=20
> "solve" the problem as specified.
>=20
> An Algorithm has runtime: essentially what is the worst case runtime for=
=20
> each problem size.
>=20
> You seem to be asking for complexity of an algorithm. It's easy to see=
=20
> that the above algorithm is exponential (or worse depending on f). One=
=20
> can assume that f, in worst case, has runtime that is a polynomial in=20
> the length of n. However, these observations say absolutely nothing=20
> about the complexity of the SAT problem.
> --=20
> Jeff Barnett

You said "...the above algorithm is exponential". But, it is just an assert=
ion.
The question Q asks for the complexity of the problem sat(..) tries to solv=
e=20
and its supporting proof.