Theoretical-Computer-Science

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 constructible We say that a function $f: \mathbb{N} \to \mathbb{N}$ such that $f(n) \geq O(\log n)$ is space constructible if there exists a function from $1^{n} \to \langle f(n) \rangle$ is $O(f(n))$ space complexity....

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 (this set of nodes forms a complete graph). We can prove that the problem is in NP because there is an easy non-deterministic algorithm that computes it....

Most of times the pattern of proving and verifying it is like this $prove \to verify$, 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 two entities, ones that try to prove it, and others try to verify it. From some point of view, this is similar from what AlphaGo does when searching, there is a part that guides the search, another that actually searches for it....

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 simile a quanto presente sul (Sipser 2012). Ossia consideriamo il linguaggio $$ HALT = \left\{ \langle x, y \rangle \in \Sigma^{*} \times \Sigma^{*}: x = code(M),M \text{ si ferma su } x\right\} $$ Dimostrazione Halting theorem🟩 La parte del sì è facile perché basta eseguirlo e vedere che si ferma (quindi abbiamo una La macchina di Turing#La macchina di Turing universale....

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 che intuitivamente sembrano essere molto diversi rispetto alla TM alla fine possono essere dimostrate essere equivalenti. Turing con nastri addizionali Questo è presente in modo abbastanza facile sul Sipser....