. . . . "Proof complexity"@en . . . . . . . "1362"^^ . "11621328"^^ . . . "Complexit\u00E9 des preuves"@fr . . . "182046388"^^ . . . . . "En informatique th\u00E9orique, la complexit\u00E9 des preuves ou complexit\u00E9 des d\u00E9monstrations est le domaine qui \u00E9tudie les ressources n\u00E9cessaires pour prouver ou r\u00E9futer un \u00E9nonc\u00E9 math\u00E9matique. Le d\u00E9marche classique du domaine est de fixer une sorte de preuve, puis de montrer des bornes sur la longueur des preuves pour certains \u00E9nonc\u00E9s. La sorte de preuve peut \u00EAtre d'origine logique, comme la d\u00E9duction naturelle, le calcul des s\u00E9quents, des syst\u00E8mes bas\u00E9s sur la r\u00E8gle de r\u00E9solution, ou plus combinatoire, comme l'algorithme DPLL et la m\u00E9thode des plans s\u00E9cants. Pour chacun il faut d\u00E9finir une notion de longueur pertinente."@fr . . . . . "En informatique th\u00E9orique, la complexit\u00E9 des preuves ou complexit\u00E9 des d\u00E9monstrations est le domaine qui \u00E9tudie les ressources n\u00E9cessaires pour prouver ou r\u00E9futer un \u00E9nonc\u00E9 math\u00E9matique. Le d\u00E9marche classique du domaine est de fixer une sorte de preuve, puis de montrer des bornes sur la longueur des preuves pour certains \u00E9nonc\u00E9s. La sorte de preuve peut \u00EAtre d'origine logique, comme la d\u00E9duction naturelle, le calcul des s\u00E9quents, des syst\u00E8mes bas\u00E9s sur la r\u00E8gle de r\u00E9solution, ou plus combinatoire, comme l'algorithme DPLL et la m\u00E9thode des plans s\u00E9cants. Pour chacun il faut d\u00E9finir une notion de longueur pertinente. Le domaine est li\u00E9 \u00E0 la th\u00E9orie de la complexit\u00E9 et aux assistants de preuve. Il a aussi de fortes relations avec les circuits bool\u00E9ens."@fr .