Complexity-03 — Plus de temps, plus de problèmes

Navigation : Index | 02 — Vérifier ou trouver | 03b — Hartmanis–Stearns | 03c — Zoo navigable

Public : Licence. La démonstration historique et sa simulation multitête sont conservées dans l’approfondissement 03b.

Ce que ce notebook suppose

Objectifs : distinguer inclusion et séparation stricte de classes, comprendre une diagonale finie et expliquer pourquoi une table n’est pas une preuve de hiérarchie. Durée estimée : 35 minutes.

1. Des budgets imbriqués

Si un programme répond en n pas, il répond aussi dans un budget de n² pas. Cela montre une inclusion des budgets, pas une séparation des classes de problèmes : deux programmes différents sur un même problème ne prouvent pas qu’aucun programme rapide ne peut le résoudre. Comparons les budgets sur cinq tailles.

tailles = (2, 4, 8, 16, 32)
print(f"{'n':>3} | {'n²':>5} | {'2ⁿ':>12}")
for n in tailles:
    print(f"{n:>3} | {n * n:>5} | {2 ** n:>12}")
assert all(n * n <= 2 ** n for n in tailles)
  n |    n² |           2ⁿ
  2 |     4 |            4
  4 |    16 |           16
  8 |    64 |          256
 16 |   256 |        65536
 32 |  1024 |   4294967296

Lecture du résultat. Les coûts s’ordonnent pour les tailles affichées. Pour conclure qu’une classe possède un problème absent de l’autre, il faudrait écarter tous les algorithmes au petit budget. La table numérique ne le fait pas.

2. L’idée de diagonalisation

Énumérons quelques machines candidates. À la ligne i, la construction D choisit l’opposé de la réponse de la machine numéro i sur l’entrée i. D diffère donc de chaque machine listée sur au moins une entrée. La liste ci-dessous n’est qu’une expérience finie : elle ne représente pas toutes les machines possibles.

machines = (
    lambda i: i % 2 == 0,
    lambda i: i < 2,
    lambda i: True,
    lambda i: i % 3 == 0,
)
diagonale = {i: not machine(i) for i, machine in enumerate(machines)}
print(f"{'i':>2} | {'M_i(i)':>6} | {'D(i)':>5} | différents")
for i, machine in enumerate(machines):
    print(f"{i:>2} | {str(machine(i)):>6} | {str(diagonale[i]):>5} | {diagonale[i] != machine(i)}")
assert all(diagonale[i] != machine(i) for i, machine in enumerate(machines))
 i | M_i(i) |  D(i) | différents
 0 |   True | False | True
 1 |   True | False | True
 2 |   True | False | True
 3 |   True | False | True

Lecture du résultat. Chaque ligne porte une opposition vérifiée. Il reste une infinité de machines non listées ; ce tableau ne prouve donc aucune séparation de classes.

3. Le budget de simulation

Une machine qui ne répond pas avant la limite ne peut pas bloquer indéfiniment le constructeur diagonal. Ici les coûts sont déclarés par un modèle fini : ce ne sont pas des pas mesurés par un simulateur universel. Une réponse non observée n’est pas un verdict faux.

candidates = ((True, 1), (False, 3), (True, 12), (False, 40))
def budget(i):
    return 2 * i + 4

print(f"{'i':>2} | {'pas':>3} | {'budget':>6} | {'observé':>7} | {'D(i)':>5}")
for i, (verdict, pas) in enumerate(candidates):
    observe = verdict if pas <= budget(i) else None
    diagonal = not observe if observe is not None else True
    print(f"{i:>2} | {pas:>3} | {budget(i):>6} | {str(observe):>7} | {str(diagonal):>5}")
 i | pas | budget | observé |  D(i)
 0 |   1 |      4 |    True | False
 1 |   3 |      6 |   False |  True
 2 |  12 |      8 |    None |  True
 3 |  40 |     10 |    None |  True

Lecture du résultat. None signifie « non observé dans le budget », jamais « faux ». Une machine dépassant ce budget sur une entrée ne satisfait pas la borne uniforme sur toutes les entrées, mais le tableau ne caractérise aucune classe entière.

4. Le théorème, sans raccourci expérimental

Le théorème de hiérarchie temporelle établit, sous des hypothèses techniques, qu’il existe des problèmes décidables avec un budget suffisamment plus grand mais impossibles avec le plus petit. Il faut énumérer toutes les machines admissibles, construire une horloge et payer le coût de simulation universelle. Les tables finies n’accomplissent aucune de ces preuves. 03b — Hartmanis–Stearns détaille le modèle historique. Ce résultat ne résout pas P contre NP.

Exercices

Exercice 1 — Inclusion ou séparation ?

Comparez n² et n³ pour n = 2, 4, 8, 16. Expliquez pourquoi ces nombres ne prouvent pas qu’un problème devient soluble uniquement avec le second budget.

  • Indice : une table de nombres n’écarte aucun autre algorithme.
  • Etape 1 : produire les quatre couples.
  • Etape 2 : distinguer inclusion et séparation.
comparaison_budgets = None  # TODO etudiant : couples (n², n³)
print('Exercice a completer : inclusion et separation')
Exercice a completer : inclusion et separation

Exercice 2 — Une autre diagonale

Ajoutez une cinquième fonction à machines, puis reconstruisez D et expliquez pourquoi cette table finie n’est toujours pas une preuve générale.

  • Indice : évaluer la nouvelle fonction sur son propre indice.
  • Etape 1 : ajouter une machine.
  • Etape 2 : recalculer les cinq oppositions.
nouvelle_diagonale = None  # TODO etudiant : cinquieme machine et nouvelle diagonale
print('Exercice a completer : nouvelle diagonale')
Exercice a completer : nouvelle diagonale

Exercice 3 — Dépassement de budget

Repérez les lignes dont le coût déclaré dépasse budget(i). Proposez un budget qui couvre les quatre coûts et expliquez pourquoi cela ne construit pas une borne pour toutes les machines.

  • Indice : comparer les deux colonnes numériques.
  • Etape 1 : produire un nouveau budget.
  • Etape 2 : énoncer la limite de ce modèle fini.
budget_etendu = None  # TODO etudiant : couvrir les quatre couts
print('Exercice a completer : budget etendu')
Exercice a completer : budget etendu

Conclusion

Geste Vérifié ici Non démontré ici
Budgets Inclusion numérique Séparation stricte de classes
Diagonale Quatre contradictions finies Toutes les machines admissibles
Simulation Arrêt sur dépassement Horloge et coût universel bornés

Le théorème affirme l’existence de problèmes demandant réellement plus de temps, et non seulement de programmes lents. L’approfondissement 03b travaille le résultat historique.

Référence : Hartmanis, J. et Stearns, R. E. (1965), On the computational complexity of algorithms, Transactions of the American Mathematical Society 117, 285–306.

Retour au sommet