Lista Possibili Domande

• Halting Problem é indecidibile;
• speed-up theorem per macchine di Turing;
• problemi da sapere in P: 2SAT, HornSAT, renamable Horn, bipartieness, reachability, maximum matching, maximum flow.
• NP-completezza di Node Cover, Hamilton Circuit, 3DM, 3-Colorability, Partitioning, Knapsack;
• Knapsack ammette un algoritmo pseudopolinomiale e persino un FPTAS;
• la nozione di NP-completezza in senso forte ed il suo ruolo;
• teorema di Cook;
• P$\subseteq$ PSC;
• PSP$=$P/poly;
• algoritmo Monte Carlo per determinanti di matrici simboliche e perfect matchings;
• BPP $\subseteq$ PSC;
• se un linguaggio unario é NP-completo allora P$=$NP;
• se P$\neq$NP allora NPI $\neq \emptyset$;
• teorema di Savitch;
• teorema di Immerman-Szelepscényi;
• la tecnica del padding: P$=$NP $\Rightarrow$ EXP$=$ NEXP;
• PSPACE-completeness di QSAT e geography.