Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 11 di 36

CIRCUIT SAT

Dato un circuito booleano con porte AND, OR e NOT: esiste un input che dà uscita 1?

NPNP-completo

Un esempio, passo dopo passo

1 / 3

Segui le porte. Circuito: (x ∨ y) ∧ ¬y. Due ingressi, una porta OR, una NOT e una AND finale. — 1. Segui le porte
Circuito: $(x \lor y) \land \neg y$ . Due ingressi, una porta OR, una NOT e una AND finale.

Scorri l'immagine o usa Avanti.

Il certificato è un assegnamento agli ingressi. Si valuta il circuito in ordine topologico, una porta alla volta, e si controlla l’uscita. Una formula SAT può essere rappresentata da un circuito di dimensione polinomiale.

Complemento e collegamenti

Nessun complemento associato.

stesso problema, scritto come circuito
nomi simili, classi diverse: NP contro $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$
la versione succinta sale da NP a NEXP

Problemi NEXP-completi

Domande e trappole d'esame

Non confonderlo con CIRC SAT (circoscrizione), che è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completo. Compare in F03#5, G20v3#1 e G20v4#2.

Problemi del corso

1. Segui le porte

2. Propaga i bit

3. Leggi l’uscita