Path: ...!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: Mon, 13 May 2024 18:33:18 +0800
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <1fee0cb3908ed2d540818bc90b13acda765c683d.camel@gmail.com>
References: <75e1b41e7f0205e6cafea3057cd6331e39536449.camel@gmail.com>
	 <v1s6p3$39bgn$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 13 May 2024 12:33:19 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="bac6dc8ec4ad419340789fa6030430d0";
	logging-data="3587991"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19TX/Ib42/SYOnVSmqh8uRM"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:OwG68zlWBa8Ml7Jfn1CO7ljJ32Y=
In-Reply-To: <v1s6p3$39bgn$1@dont-email.me>
Bytes: 2377

On Mon, 2024-05-13 at 07:00 +0200, immibis wrote:
> On 11/05/24 08:00, 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
> >=20
>=20
> If UInt is a variable length integer, the amount of time that 'sat'=20
> takes to run is usually proportional to 2 to the power of the size of=20
> 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 wh=
ether
           or not there exists a value c such that 0<=3Dc<=3Dn, f(c)=3D=3D1=
..

 Q: Is [Problem] a NP(or NPC) problem? If not, what the classification is i=
t?