Vai al contenuto
Home
Classi
Problemi
Teoremi
Confronta
Gerarchia PH
Quantistico
Esercitati
Tracce
MdT
Problemi del corso
Scegli un problema, segui l'esempio illustrato e passa al prossimo.
⌕
Classe
Tutte le classi
L
NL
P
NP
coNP
DP
Σᵢᴾ
Πᵢᴾ
PSPACE
NEXP
RE ∖ R
coRE ∖ R
Solo completi
Solo nelle tracce
36 problemi
01
REACHABILITY
NL
Completo
02
2-SAT
NL
Completo
Nelle tracce
03
2-COL
P
Nelle tracce
04
MAX FLOW
P
Completo
Nelle tracce
05
LINEAR PROGRAMMING
P
Completo
06
PRIMES
P
Nelle tracce
07
HORNSAT
P
Completo
08
SAT
NP
Completo
Nelle tracce
09
3-SAT
NP
Completo
Nelle tracce
10
MAX2SAT
NP
Completo
11
CIRCUIT SAT
NP
Completo
12
CLIQUE
NP
Completo
Nelle tracce
13
INDEPENDENT SET
NP
Completo
Nelle tracce
14
NODE COVER
NP
Completo
15
HAMILTON PATH
NP
Completo
Nelle tracce
16
TSP(D)
NP
Completo
Nelle tracce
17
3-COL
NP
Completo
Nelle tracce
18
INTEGER PROGRAMMING
NP
Completo
19
KNAPSACK
NP
Completo
20
VALIDITY
coNP
Completo
Nelle tracce
21
co-SAT
coNP
Completo
22
co-HAMILTON PATH
coNP
Completo
23
co-TSP(D)
coNP
Completo
24
SAT-UNSAT
DP
Completo
Nelle tracce
25
EXACT TSP
DP
Completo
Nelle tracce
26
QSAT
i
Σ
i
P
\Sigma_i^{\mathrm{P}}
Σ
i
P
Completo
Nelle tracce
27
co-QSAT
i
Π
i
P
\Pi_i^{\mathrm{P}}
Π
i
P
Completo
Nelle tracce
28
STRATEGIC COMPANIES
Σ
2
P
\Sigma_2^{\mathrm{P}}
Σ
2
P
Completo
Nelle tracce
29
co-STRATEGIC COMPANIES
Π
2
P
\Pi_2^{\mathrm{P}}
Π
2
P
Completo
30
CIRC SAT
Σ
2
P
\Sigma_2^{\mathrm{P}}
Σ
2
P
Completo
Nelle tracce
31
QSAT
PSPACE
Completo
Nelle tracce
32
GEOGRAPHY
PSPACE
Completo
Nelle tracce
33
SCHÖNFINKEL-BERNAYS SAT
NEXP
Completo
Nelle tracce
34
SUCCINCT CIRCUIT SAT
NEXP
Completo
35
Validità del primo ordine
R
E
∖
R
\mathrm{RE} \setminus \mathrm{R}
RE
∖
R
Nelle tracce
36
Soddisfacibilità del primo ordine
c
o
R
E
∖
R
\mathrm{coRE} \setminus \mathrm{R}
coRE
∖
R
Nelle tracce
Home
Classi
Problemi
Teoremi
Confronta
Gerarchia PH
Quantistico
Esercitati
Tracce
MdT