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

Liste des GroupesRevenir à c theory 
Sujet : What is the complexity classification of sat(..) ?
De : wyniijj5 (at) *nospam* gmail.com (wij)
Groupes : comp.theory
Date : 11. May 2024, 08:00:28
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <75e1b41e7f0205e6cafea3057cd6331e39536449.camel@gmail.com>
User-Agent : Evolution 3.50.2 (3.50.2-1.fc39)
 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(..)?



Date Sujet#  Auteur
11 May 24 * What is the complexity classification of sat(..) ?9wij
13 May 24 +* Re: What is the complexity classification of sat(..) ?5immibis
13 May 24 i`* Re: What is the complexity classification of sat(..) ?4wij
13 May 24 i +* Re: What is the complexity classification of sat(..) ?2immibis
14 May 24 i i`- Re: What is the complexity classification of sat(..) ?1immibis
17 May 24 i `- Re: What is the complexity classification of sat(..) ?1wij
16 May 24 `* Re: What is the complexity classification of sat(..) ?3Jeff Barnett
16 May 24  `* Re: What is the complexity classification of sat(..) ?2wij
16 May 24   `- Re: What is the complexity classification of sat(..) ?1Ben Bacarisse

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal