Cook Levin theorem is important because says that in 1971 if S A T ∈ P then N P = P . We will start with this idea to define the concept of NP-completeness . Let's start with the basics. Poly-reduction # Def: poly-reduction # We say that two languages L and L ′ defines over…
Introduzione # Note filosofiche (non impo) # Bisogna in primo momento cercare di definire cosa è la computazione e cosa è un computer. Aristotele faceva la distinzione fra proprietà essenziali e accidentali . Quelle essenziali sono proprie dell'oggetto. Una sedia può essere…
Sono variazioni possibili equivalenti: • Nastri addizionali • Testine addizionali • Nastri infiniti su entrambi i lati • Non-determinismo • Scelta probabilistica • Scelta quantistica Si può dire che la definizione di TM è stata robusta nella storia perché tantissimi formalismi…
Halting theorem # Questo è un problema fondamentale, che abbiamo trattato anche in Fondamenti teorica#Halting problem , ma qui lo ritrattiamo, perché così lo rifacciamo per bene. In parte è stato trattato anche al corso di Logica. Enunciato Halting theorem # Questo è molto…
This note is useful to gather in a single place the description of some common problems in CS and their theoretical implications explained in other notes. The Clique problem # Description of the problem # This problem is in NP, find all sub-graphs where all nodes are connected…
Introduction to the Rice Theorem # Ci sono molti teoremi che non possono essere decisi, vedere Halting Theorem and Reducibility . Qui andiamo a chiederci quale sia l'insieme dei problemi decidibili. Proprietà dei linguaggi TM # Data una macchina M definiamo il suo linguaggio…
In this note we explore a theme of time and space complexity. Those are cardinal themes in Theoretical CS. Time -> execution step bounds on algorithms Space -> the cells visited by a Turing Machine when executed. Introduction to Time Complexity # This note will build upon know…
Most of times the pattern of proving and verifying it is like this p r o v e → v er i f y , that is: there is an entity that generates the solution, andPo then another that tries to verify it. But more expressive algorithms could be possible if there is interaction between the…
Introduction to the probabilistic Turing Machine # Most of real phenomena are better comprehended by a probabilistic view. This pushes to build a formal model that takes probability into account Def: Probabilistic TM # Take a non deterministic TM La macchina di Turing . At each…
Intractable problems are solvable in principle, but in reality they require so much time or space that there no physical computers that can solve them in reasonable time. We would like to define a clear hierarchy of these set of problems. Space Hierarchies # Def: Space…