COMPUTABILITA' E COMPLESSITA'

Module COMPLESSITA'

Knowledge and understanding: Students will acquire the fundamental notions related to time complexity classes, with particular focus on the class NP and the concept of NP-completeness. The propositional satisfiability problem (SAT) and Cook’s Theorem will also be studied in depth. Finally, computational issues associated with several classical problems will be examined, including 3-SAT, n-SAT, Vertex Cover, Clique, Independent Set, Hitting Set, Set Cover, Subset Sum, and Knapsack.

Making judgements: Students will be able to rigorously evaluate the computational class of an algorithmic problem.

Communication skills: Students will acquire the necessary communication skills and an appropriate expressive ability to present and discuss topics related to computational complexity, including with non-expert audiences.

Learning skills: Students will be able to apply and adapt the knowledge acquired to new contexts, as well as independently update their expertise through the consultation of specialist sources in the field of computational complexity.

Classroom-taught lessons

Should teaching be delivered in mixed mode or remotely, some adjustments may be required compared to the above, in accordance with the organization and contents set out in the syllabus.

- Elements of discrete mathematics and continuous mathematics

- Intuitive concept of an algorithm 

- Elements of mathematical logic

Asymptotic notations (overview), Time complexity classes.
The class NP and NP-completeness.
The Boolean satisfiability problem (SAT).
Cook’s Theorem.
Catalog of NP-complete problems (indicative): 3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet, HamiltonianPath, HamiltonianCircuit, LongestSimplePath, SetCover, HittingSet, SubgraphIsomorphism, TravelingSalesman, 3-DimensionalMatching, Partition, SubsetSum, Knapsack.
This list is illustrative rather than exhaustive: some problems may be only briefly covered, and additional ones not explicitly mentioned may also be included during the course.
Space complexity of Turing machines.

1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge, UK, 1986. [Main textbook]

2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Recommended reading]

The final exam is essentially written. The recording of the grade may be preceded by a brief discussion of the written work and, in doubtful cases, by a short oral examination.

The following criteria are generally applied for the assignment of the final grade:

Not approved: the student has not yet acquired the basic concepts and is unable to adequately solve the exercises.

18–23: the student demonstrates an essential knowledge of the basic concepts; exposition and ability to connect topics are limited, but the student manages to solve simple exercises.

24–27: the student demonstrates a good knowledge of the course contents, presents them clearly and connects them appropriately; exercises are solved with few errors.

28–30 with honors: the student has acquired a complete knowledge of the contents, presents them with clarity and critical insight, and solves the exercises accurately and without errors.

Students with disabilities and/or specific learning disorders (DSA) must contact the instructor, the CInAP representative of the DMI (Prof. Daniele), and CInAP sufficiently in advance of the exam date to notify their intention to take the exam with the appropriate compensatory measures.

For illustrative purposes only, here are some examples of exam questions:

1. Determine and justify the computational complexity of the following algorithm.

2. Describe the reduction of the following problem to 3-SAT.

3. Provide an example of an NP-hard problem that does not belong to NP, explaining why.

4. Prove that the CLIQUE problem is NP-complete.

5. Compare the complexity classes P, NP, and co-NP, discussing their main differences.