Problemi del corso

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

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 34 di 36

SUCCINCT CIRCUIT SAT

Un circuito piccolo descrive un circuito enorme: dato il numero di una porta, ne restituisce il tipo e gli ingressi. Il circuito enorme è soddisfacibile?

NEXPNEXP-completo

Un esempio, passo dopo passo

1 / 3

Leggi la descrizione compatta. Una descrizione indicizzata specifica tre porte: input x, NOT(x), OR(x,NOT(x)). — 1. Leggi la descrizione compatta
Una descrizione indicizzata specifica tre porte: input $x$ , $\mathrm{NOT}(x)$ , $\mathrm{OR}(x, \mathrm{NOT}(x))$ .

Scorri l'immagine o usa Avanti.

Un circuito piccolo descrive porte e collegamenti di un circuito molto più grande, attraverso i loro indici. L’assegnamento e il circuito descritto possono avere dimensione esponenziale rispetto all’input. Indovinare l’assegnamento e valutare tutte le porte richiede tempo esponenziale nondeterministico.

Complemento e collegamenti

Nessun complemento associato.

la versione succinta sale da NP a NEXP
entrambi NEXP-completi

Problemi NEXP-completi

Domande e trappole d'esame

Il prefisso "succinct" fa salire di un esponenziale: CIRCUIT SAT è NP-completo, SUCCINCT CIRCUIT SAT è NEXP-completo.

Problemi del corso

1. Leggi la descrizione compatta

2. Ricostruisci le porte dell’esempio

3. Valuta un input