Font size: Αα Αα Αα hide gadgets
You are here: Courses » 2012-2013 » χειμερινό εξάμηνο » Λ4. Αλγόριθμοι και πολυπλοκότητα II (2012-2013, χειμερινό εξάμηνο)

Αλγόριθμοι και πολυπλοκότητα II: 2012-2013, χειμερινό εξάμηνο

This is a course that has been given 18 times. For information about this course in general (not just for this specific semester), visit its page: Λ4. Αλγόριθμοι και πολυπλοκότητα II.

Taught by: Aριστείδης Παγουρτζής & Ευστάθιος Ζάχος
Teaching assistant: Αντώνης Αντωνόπουλος
Start date: 08 Οκτωβρίου 2012
End date:

Teaching hours

  • every Δευτέρα, 17:00-19:00, 1.1.29, ΣΗΜΜΥ, ΕΜΠ (παλαιά κτ.)
  • every Πέμπτη, 13:45-15:45, 1.1.29, ΣΗΜΜΥ, ΕΜΠ (παλαιά κτ.)

Course information

Ώρες γραφείου: Παρασκευή 12:00-16:00, στο Eργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλιά Κτίρια ΗΜΜΥ, ΕΜΠ.

Φυλλάδιο Μαθήματος-Syllabus

(Εξεταστέα) ύλη μαθήματος

Για τακτικές ενημερώσεις και πληροφορίες σχετικά με το μάθημα, παρακαλώ δείτε την σελίδα του μαθήματος εδώ. Το παρακάτω προφίλ του μαθήματος θα συγχρονίζεται με την σελίδα περιοδικά.

Enrolled students



Δευτέρα, 08 Οκτ 2012 Ζάχος

Εισαγωγή - Διαδικαστικά Hierarchies of Complexity Classes

Πέμπτη, 11 Οκτ 2012 Ζάχος

Computational Models, Hierarchies, History

Δευτέρα, 15 Οκτ 2012 Ζάχος

Computational Model-Turing Machines: Equivalence of Computational Models, Turing Machines, Time and Space bounds, multiple strings, linear speedup, nondeterminism.

Πέμπτη, 18 Οκτ 2012 Ζάχος

Computability and Undecidability: The Universal Turing Machine, Simulation, Diagonalization, The Halting Problem, Recursive and Recursive Enumerable Sets.

Δευτέρα, 22 Οκτ 2012 Αντωνόπουλος

Complexity Classes: Complexity measures, Time and Space Classes Hierarchy Theorems, Gap Theorem, Basic inclusions between complexity classes, Quantifier Notation and characterization of NP (Theorem 9.1 [1]).

Δευτέρα, 29 Οκτ 2012 Ζάχος

Space Computation: The classes L and NL, Savitch’s Theorem, Immerman-Szelepscényi Theorem (NL=coNL), Reingold’s Theorem: L=SL (without proof) & Undirected REACHABILITY.

Πέμπτη, 01 Νοέ 2012 Ζάχος

Second-Order Logic, Incompleteness, Fagin's Theorem

Δευτέρα, 05 Νοέ 2012 Ζάχος

Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd)

Πέμπτη, 08 Νοέ 2012 Ζάχος

Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd). The Arithmetical Hierarchy.

Δευτέρα, 12 Νοέ 2012 Ζάχος

Diagonalization & Hierarchies, Case-Study: DTIME(n)⊂DTIME(n^1.5) Reductions: Reductions between problems, P-completeness, NP-completeness.

Δευτέρα, 19 Νοέ 2012 Ζάχος

Reductions: Different types of reductions (Karp, Cook, Cook[1], tt), and relations among them. NP-Complete Problems: - Cook’s Theorem, SAT and satisfiability variants - IS,CLIQUE, MAX-CUT

Πέμπτη, 22 Νοέ 2012 Ζάχος

NP-Complete Problems: - HP, TSP, 3COL, 0/1 IP - 3DM, KNAPSACK, Pseudopolynomial Algorithms and Strong NP-Completeness

Δευτέρα, 26 Νοέ 2012 Ζάχος

Ladner’s Theorem, Density, Sparse sets The “Berman-Hartmanis” conjecture, NP-isomorphism, padding.

Πέμπτη, 29 Νοέ 2012 Ζάχος

Function Problems: The classes coNP and ∆NP, Function classes (FL, FP, FNP, FPSPACE etc) and reductions, the classes PLS and PPAD.

Δευτέρα, 03 Δεκ 2012 Ζάχος

Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP classes.

Πέμπτη, 06 Δεκ 2012 Ζάχος

Oracles & The Polynomial Hierarchy: Oracles and oracle classes, the Polynomial-Time Hierarchy.

Πέμπτη, 13 Δεκ 2012 Ζάχος

Quantifier notation (∃+) and related results, semantic and syntactic classes, the “P vs BPP” question.

Δευτέρα, 17 Δεκ 2012 Ζάχος

2o Quiz σε Reductions & Randomized Complexity Classes. The equivalence between Oracle and Quantifier Polynomial Hierarchy

Πέμπτη, 20 Δεκ 2012 Ζάχος

The Polynomial-Time Hierarchy and related theorems, The BPP Theorem, Swapping quantifiers, Operator-defined classes.

Πέμπτη, 10 Ιαν 2013 Ζάχος

Non-Uniform Complexity: Boolean circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs.

Δευτέρα, 14 Ιαν 2013 Ζάχος

Parallel computation (classes NC, RNC, AC, TC)

Interactive Proof Systems:

-Interactive Proofs (IP)

Πέμπτη, 17 Ιαν 2013 Ζάχος

Interactive Proof Systems:

-Arthur-Merlin Games (AM)

Δευτέρα, 21 Ιαν 2013 Ζάχος

Interactive Proof Systems:

-Shamir’s Theorem: IP=PSPACE

-Zero Knowledge Proofs

Πέμπτη, 24 Ιαν 2013 Ζάχος

Quantifier Notation and Arthur-Merlin Games

An introduction to Pseudorandomness and Derandomization

Introduction to PCPs

Δευτέρα, 28 Ιαν 2013 Ζάχος

Interactive Proof Systems:

-Probabilistically Checkable Proofs (PCP)

-Dinur's Proof of the PCP Theorem

Πέμπτη, 31 Ιαν 2013 Ζάχος

Counting Complexity: #P, #P-completeness, Toda's Theorem, Gaps

Approximability and Approximation Schemes

Δευτέρα, 04 Φεβ 2013 Ζάχος

Reingold's Theorem: L=SL

Quantum Computation

Πέμπτη, 07 Φεβ 2013 Ζάχος


Interactive Proof Systems: -Hardness of Approximations

Pseudorandomness & Combinatorial Constructions

The Unique Games Conjecture

Δευτέρα, 11 Φεβ 2013 Ζάχος

Algebraic Computation

The Bright Side of Hardness


# handout given on deadline solutions
1 1η Σειρά Ασκήσεων Δευτέρα, 29 Οκτ 2012 2012-11-29
2 2η Σειρά Ασκήσεων Κυριακή, 30 Δεκ 2012 2013-01-24
3 3η Σειρά Ασκήσεων Παρασκευή, 08 Φεβ 2013 2013-03-10


You must be logged in to comment.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.