Proof complexity can be a tool for studying the efficiency of algorithms. By proving a single lower bound on the length of certain proofs, we can get running time lower bounds for a wide category of algorithms. We survey the proof complexity literature that adopts this approach relative to two NP-problems: k-clique and 3-coloring.
Algorithm analysis through proof complexity / Lauria, Massimo. - 10936:(2018), pp. 254-263. (Intervento presentato al convegno 14th Conference on Computability in Europe, CiE 2018 tenutosi a Kiel (Germany)) [10.1007/978-3-319-94418-0_26].
Algorithm analysis through proof complexity
Lauria, Massimo
2018
Abstract
Proof complexity can be a tool for studying the efficiency of algorithms. By proving a single lower bound on the length of certain proofs, we can get running time lower bounds for a wide category of algorithms. We survey the proof complexity literature that adopts this approach relative to two NP-problems: k-clique and 3-coloring.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
Lauria_indice_Algorithm-analysis_2018.pdf
solo gestori archivio
Tipologia:
Altro materiale allegato
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
34.53 kB
Formato
Adobe PDF
|
34.53 kB | Adobe PDF | Contatta l'autore |
|
Lauria_Algorithm-analysis_2018.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
297.73 kB
Formato
Adobe PDF
|
297.73 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
