Un schéma de propriétés logiques, sémantiques ou computationnelles dont la validité ou les bornes en ressources dépendent de paramètres, d’instances ou d’encodages particuliers plutôt que d’une seule borne ou démonstration uniforme valable pour toute la classe.

Principe

Une propriété est non uniforme lorsqu’elle repose sur des informations spécifiques à l’instance ou sur des paramètres (par exemple chaînes de conseil, encodages d’instance, constructions au cas par cas) au lieu d’un algorithme, d’un schéma ou d’une borne unique applicable uniformément à la classe entière.

Démonstration

En complexité, les circuits non uniformes autorisent un circuit différent pour chaque longueur d’entrée ; une famille de tels circuits donne un pouvoir de décision qui n’est pas capturé par un seul programme de machine de Turing uniforme sauf si l’on impose des contraintes de uniformité.

Mauvaise application

Prendre pour acquis qu’une preuve portant sur un nombre fini de représentants se prolonge uniformément à toutes les instances ; ou confondre l’existence de constructions instance-par-instance avec un algorithme uniforme sans vérifier l’existence d’une procédure uniforme de génération.

Conséquence

La reconnaissance du caractère non uniforme conduit à des classifications raffinées (par ex. classes de complexité uniformes vs non uniformes), à des analyses dépendantes des paramètres et à l’exigence de conditions d’uniformité pour des résultats de complétude ou de transfert.

Inversion

Comportement uniforme : une même règle effective, borne ou démonstration s’applique à chaque instance de la classe sans dépendre de paramètres propres à l’instance.

Limite

Concerné par les phénomènes où des ressources ou encodages spécifiques à l’instance modifient les résultats ; exclut les situations où une procédure constructive ou une borne uniforme couvre déjà toutes les instances. Ce n’est pas une simple variabilité numérique lorsque la borne uniforme existe.

Tension sémantique

La tension vient de la confusion entre considérer une construction instance-par-instance comme une preuve d’une propriété de la classe (affirmation uniforme) et la voir comme un artefact de ressources non uniformes qui ne se généralise pas.

Synthèse

Le comportement non uniforme distingue les constructions dépendantes des instances des explications uniformes à l’échelle d’une classe : il signale quand des éléments dépendants de paramètres sont essentiels et quand il faut imposer l’uniformité pour obtenir un compte rendu cohérent.