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^{\htmlData{term=P}{\mathrm{P}}}
Σ
i
P
Completo
Nelle tracce
→
27
co-QSAT
i
Π
i
P
\Pi_i^{\htmlData{term=P}{\mathrm{P}}}
Π
i
P
Completo
Nelle tracce
→
28
STRATEGIC COMPANIES
Σ
2
P
\htmlData{term=Σ2}{\Sigma_{2}^{\mathrm{P}}}
Σ
2
P
Completo
Nelle tracce
→
29
co-STRATEGIC COMPANIES
Π
2
P
\htmlData{term=Π2}{\Pi_{2}^{\mathrm{P}}}
Π
2
P
Completo
→
30
CIRC SAT
Σ
2
P
\htmlData{term=Σ2}{\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
\htmlData{term=RE}{\mathrm{RE}} \setminus \htmlData{term=R}{\mathrm{R}}
RE
∖
R
Nelle tracce
→
36
Soddisfacibilità del primo ordine
c
o
R
E
∖
R
\htmlData{term=coRE}{\mathrm{coRE}} \setminus \htmlData{term=R}{\mathrm{R}}
coRE
∖
R
Nelle tracce
→
Home
Classi
Problemi
Teoremi
Confronta
Gerarchia PH
Quantistico
Esercitati
Tracce
MdT