Graphs and hypergraphs : algorithmic and algebraic complexities
type: Dataset
description: Beware, this abstract comports irony and humor. In this dissertation, we defend the idea that, for any reasonnable model of computation, this is not the model that is important to caracterize important complexity classes. Instead, what matters is the complexity of the underlying combinatorial structure and, at the end, the underlying graph. If we take the example of boolean or algebraic circuits as models, all that matters is the complexity of the underlying digraph. By a reasonnable model of computation, we mean, as is requested, a model that when studied on a standard class of graphs will give the standard complexity class we expect, in order to statisfy the elementary rules of tautologies. One could also choose as reasonnable models the Turing-complete models (or another notion of completeness more suited to the computed objects), that can be formalized in a simple logic (in order to avoid "cheats" and models designed specialy to falsify this beautiful claim). Nevertheless, since this second option may be risky, we only propose it. The defended thesis is a more formalized and more mathematically precise version of this idea with hollow limits (and hence a little false as it is).
issued: 2026-05-08T05:29:16.337514
language: fr
modified: 2026-05-08T05:29:16.337519
contact point: Organization
  fn: CCSD
keyword: algebraic-formulas
keyword: cliquewidth
keyword: complexite
keyword: complexity
keyword: determinant
keyword: formules-algebriques
keyword: graphes
keyword: graphs
keyword: hypergraphes
keyword: hypergraphs
keyword: infoeu-reposemanticsdoctoralthesis
keyword: infoinfo-cccomputer-science-cscomputational-complexity-cscc
keyword: infoinfo-dmcomputer-science-csdiscrete-mathematics-csdm
keyword: infoinfo-dscomputer-science-csdata-structures-and-algorithms-csds
keyword: infoinfo-locomputer-science-cslogic-in-computer-science-cslo
keyword: largeur-arborescente
keyword: largeur-de-chemin
keyword: largeur-de-clique
keyword: logic
keyword: logique
keyword: mathmath-comathematics-mathcombinatorics-mathco
keyword: modele-de-valiant
keyword: mso
keyword: np-complet
keyword: np-complete
keyword: partitioning
keyword: partitionnement
keyword: pathwidth
keyword: permanent
keyword: pfaffian
keyword: pfaffien
keyword: theses
keyword: treewidth
keyword: valiants-model
keyword: vnp-complet
keyword: vnp-complete
landing page: https://theses.hal.science/tel-00905137

Graphs and hypergraphs : algorithmic and algebraic complexities
type: Distribution
format: HTML
issued: 2026-05-08T05:29:16.343486
modified: 2026-05-08T05:29:16.302965
access URL: https://theses.hal.science/tel-00905137

test_moissonnage_selune
type: Agent