Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 30 di 36

CIRC SAT

Data una base di conoscenza KB e una formula $\varphi$ : $\varphi$ è vera in almeno un modello di KB minimale rispetto all'inclusione degli atomi da minimizzare?

\Sigma_2^{\mathrm{P}}

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-completo

Nelle tracce · 3 domande

F03, domanda 5 G20v3, domanda 1 G20v4, domanda 2

Un esempio, passo dopo passo

1 / 3

Leggi conoscenza e query. La base di conoscenza è KB = p ∨ q; minimizziamo p e q e chiediamo se p è vera in almeno un modello minimale. I riquadri sono i quattro assegnamenti, con in verde gli atomi veri: p, q, p, q e quello senza atomi veri, barrato perché non soddisfa p ∨ q. — 1. Leggi conoscenza e query
La base di conoscenza è $\mathit{KB} = p \lor q$ ; minimizziamo $p$ e $q$ e chiediamo se $p$ è vera in almeno un modello minimale. I riquadri sono i quattro assegnamenti, con in verde gli atomi veri: $\{p\}$ , $\{q\}$ , $\{p, q\}$ e quello senza atomi veri, barrato perché non soddisfa $p \lor q$ .

Scorri l'immagine o usa Avanti.

Un modello proposizionale indica quali atomi sono veri. Nella circoscrizione si minimizzano alcuni atomi: si scarta un modello se ne esiste uno ammissibile con un insieme strettamente più piccolo di atomi minimizzati veri, rispettando gli eventuali atomi fissati.

Per esempio, con $\mathit{KB} = p \lor q$ minimizziamo entrambi gli atomi. I modelli sono $\{p\}$ , $\{q\}$ e $\{p, q\}$ : i primi due sono minimali, l'ultimo no, perché contiene un modello più piccolo. Alla domanda se $p$ sia vera in almeno un modello minimale la risposta è sì, grazie a $\{p\}$ ; alla domanda se sia vera in tutti la risposta è no, per $\{q\}$ .

CIRC SAT usa la prima domanda: $\exists$ un modello che soddisfa KB e $\varphi$ , e $\forall$ candidati strettamente minori nessuno soddisfa i vincoli. La minimalità riguarda l'inclusione degli atomi minimizzati, non semplicemente il loro numero.

Complemento e collegamenti

Nessun complemento associato.

nomi simili, classi diverse: NP contro $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$
CIRC SAT e $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ sono entrambi $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completi

Teorema (CIRC SAT e CIRC VALIDITY)

Domande e trappole d'esame

G20v3#1
Assumiamo $\htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=PH}{\mathrm{PH}}$ . CIRC SAT è $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ -hard?
SÌ $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ : PH collassa al livello 2, quindi $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ e CIRC SAT è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo.
G20v4#2
È vero che CIRC SAT non è 4-EXP-completo?
SÌ $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 4\text{-}\mathrm{EXP}$ .
F03#5
CIRC SAT è riducibile a $\mathrm{co\text{-}QSAT}_3$ ?
SÌ $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=Δ3}{\Delta_3^{\mathrm{P}}} \subseteq \htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ .
CIRC SAT è la circoscrizione, non CIRCUIT SAT (NP-completo).

Problemi del corso

1. Leggi conoscenza e query

2. Elimina il modello non minimale

3. Controlla la query