Le problème généralisé du sudoku est-il dans P ?

questionneur

Et quelle serait la taille de l'entrée du problème? (de l'input en anglais)

Je ne savais pas trop où poster. Je me suis permis de le faire ici. Il y a peut-être un meilleur endroit.
Une introduction au sudoku pour ceux qui ne connaîtraient pas: https://fr.wikipedia.org/wiki/Sudoku 
L'objectif est de montrer par l'absurde que le problème généralisé du Sudoku (c'est-à-dire pour une longueur de côté égale à un carré parfait $n^2$ pour $n$ plus grand ou égal à $1$) n'est pas dans $P$, comme cela est souvent suggéré. On sait déjà que ce problème est dans $NP$ (https://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html, les problèmes $NP$-complets sont dans $NP$).

$P$ et $NP$ sont des ensembles de langages définis ici:
https://fr.wikipedia.org/wiki/P_(complexité)
https://fr.wikipedia.org/wiki/NP_(complexité)
Mais je trouve la définition "officielle" plus claire (pages 1 et 2) : https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf

Tentative de formulation du problème.
On considère une grille de départ non vide, partiellement remplie, de côté de longueur $n^2$, où $n \in \mathbb{N}^*$.
$m$ est le nombre de cases non vides initialement. On choisit $m$ dans $\mathbb{N}^*$. On choisit d'étudier le cas $m=0$ dans un deuxième temps.
$f$ est la fonction qui place aléatoirement les entiers dans les cases de départ de la grille.
Pour $i$ dans $[\![1;m]\!]$, les $(𝑥_𝑖,𝑦_𝑖)$ sont les coordonnées dans la grille des cases non vides de départ, et les $p_i$ sont les entiers correspondant.

"Le problème généralisé du Sudoku est dans P" équivaut à dire :
"Si $∀𝑛 \in \mathbb{N}^*, ~~ ∃𝑚∈[\![1;𝑛^2×𝑛^2]\!] ,~~ ∃((𝑥_1,𝑦_1),(𝑥_2,𝑦_2),\dots,𝑥_𝑚,𝑦_𝑚))∈([\![1;𝑛^2]\!]^2)^𝑚 , ~~ ∃(𝑝_1,𝑝_2,\dots,𝑝_𝑚)∈[\![1;𝑛^2]\!]^𝑚$
\begin{align*}
\exists f : [\![1;n^2]\!]^2 &\longrightarrow [\![1;n^2]\!] \\
(𝑥,𝑦) & \longmapsto 𝑝_𝑖   ~~&\text{ si } ~ ∃𝑖∈[\![1;𝑚]\!] ,\ (𝑥,𝑦)=(𝑥_𝑖,𝑦_𝑖)\\
(𝑥,𝑦)  &\longmapsto \varnothing   ~~&\text{ si  }  ~∀𝑖∈[\![1;𝑚]\!],\  (𝑥,𝑦)≠(𝑥_𝑖,𝑦_𝑖)
\end{align*}alors il existe une machine de Turing fonctionnant en temps polynomial remplissant toutes les cases vides en suivant ces 3 règles:

1. Chaque ligne contient tous les entiers de $1$ à $n^2$.
2. Chaque colonne contient tous les entiers de $1$ à $n^2$
3. Chaque bloc, aux coordonnées suivantes, possédant $n^2$ cases, contient tous les entiers de $1$ à $n^2$:

Pour $(p,q) \in [\![0;n-1]\!]^2$ :
3.1 Coordonnées des coins de bloc en bas à gauche : $(𝑝𝑛+1,𝑞𝑛+1)$
3.2 Coordonnées des coins de bloc en haut à gauche : $(𝑝𝑛+1,(𝑞+1)𝑛)$
3.3 Coordonnées des coins de bloc en haut à droite: $((𝑝+1)𝑛,(𝑞+1)𝑛)$
3.4 Coordonnées des coins de bloc en bas à droite: $((𝑝+1)𝑛,𝑞𝑛+1)$"

Est-ce une formulation correcte? N'y a-t-il pas mieux ?
Quelle serait la taille de l'entrée avec cette formulation ? Car il y a trois entrées: $𝑛,𝑚$, et $𝑓$. Est-il possible de réduire le nombre d'entrées à $1$ ?
Le cas d'une grille de départ vide est aussi à étudier.
Merci d'avance pour toute aide.

AlainLyon

La formulation est incomplète car une fois la grille remplie les entiers choisis doivent respecter des égalités de sommes!

Georges Abitbol

Le site dit que le problème est $NP$-complet, pas juste $NP$… Donc le problème ne doit pas être très facile 

questionneur

AlainLyon. "Le jeu du sudoku consiste à compléter une grille carrée divisée en N régions de N cases, en partie remplie avec des chiffres, de façon que dans chaque ligne, chaque colonne et chaque région les chiffres de 1 à N apparaissent une et une seule fois." Je ne vois pas où l'on parle d'égalités de sommes... extrait de https://fr.wikipedia.org/wiki/Mathématiques_du_sudoku
Georges Abitbol : oui, ce serait trop facile ...
Svp, plus de pertinence ?

Bibix

Si le problème est NP-complet alors soyons réaliste, on ne pourra probablement pas montrer qu'il est dans P. Une preuve du fait qu'il soit dans P donnerait un algorithme de résolution des clés RSA et du problème du voyageur de commerce (transport optimal) en temps polynomial ce qui serait vraiment surprenant. Des milliers de mathématiciens y ont réfléchi toute leur vie, ça m'étonnerait qu'on réponde à la question ici. Si le but est de montrer que l'algorithme n'est pas dans P, c'est la même chose.

Alesha

Bonjour
@questionneur. "On considère une grille de départ non vide, partiellement remplie, de côté de longueur $𝑛^2$, où $𝑛 \in \mathbb{N}^\ast$". Je trouve bizarre que tu ne veuilles pas considérer des grilles de longueur qui ne soit pas un carré. Pourquoi pas plutôt : "On considère une grille de départ non vide, partiellement remplie, de côté de longueur $𝑛$, où $𝑛 \in \mathbb{N}^\ast$" ? Avec ma formulation, la taille serait tout simplement $n^2$ (la taille est indépendante de $m$ et de $f$). 
J'attends de voir comment tu comptes t'y prendre pour montrer que P /= NP...

questionneur

Bibix:4e ligne du post initial: "L'objectif est de montrer par l'absurde que le problème généralisé du Sudoku (c'est-à-dire pour une longueur de côté égale à un carré parfait $n^2$ pour $n$ plus grand ou égal à 1, n'est pas dans $𝑃$, comme cela est souvent suggéré."

Les "mathématiciens" se chercheraient-ils constamment des noises?

questionneur

Bonjour Alesha,

on enlèverait alors la règle de remplissage des sous-blocs. Pourquoi pas, je ne sais pas si c'est la formulation officielle, dont ils parlent ici, inspirée du Sudoku 9x9: https://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html

Math Coss

Cela ne répond pas à la question d'@Alesha, du moins c'était la partie de la réponse évidente. La difficulté est de montrer qu'aucun algorithme de résolution ne peut être polynomial. Il est plus difficile de distinguer des classes de complexité que de les identifier parce qu'il est plus difficile de montrer une propriété sur tous les algorithmes – ceux auxquels on pense et ceux auxquels on ne pense pas – que d'en exhiber un – si astucieux, inspiré, complexe soit-il.

questionneur

Math Coss, merci pour ton commentaire. Je suis d'accord avec " Il est plus difficile de distinguer des classes de complexité que de les identifier parce qu'il est plus difficile de montrer une propriété sur tous les algorithmes – ceux auxquels on pense et ceux auxquels on ne pense pas – que d'en exhiber un – si astucieux, inspiré, complexe soit-il."

Sans offense, je crois avoir posé une question claire, dont on dévierait... Mais chacun fait ce qu'il veut hein... Le but n'est pas de démontrer que $P \ne NP$ en une heure hein... mais d'y songer, éventuellement, doucement...?

Alesha

Si tu tiens à ne considérer que des longueurs qui soient des carrés $n^2$ (pour une raison qui m'est obscure - dans le lien que tu donnes, ils donnent en exemple une longueur $4$, mais je crois que le fait que $4$ soit un carré est un hasard), alors la taille du problème sera $n^4$ (de toute façon, pour montrer que le problème n'est pas dans P, ça ne change rien, mais c'est plus naturel ainsi). 

questionneur

@Alesha: je pense que cela pourrait changer beaucoup de choses à la manière de voir les algorithmes que de voir toutes les grilles $n$ x $n$, plutôt que de se restreindre aux $n^2$ x $n^2$ en fait. Et c'est aussi se rajouter du travail, celui concernant les grilles $n$ x $n$, qui ne sont pas $n^2$ x $n^2$.

questionneur

Après m'être renseigné, la taille de l'entrée, dans le post initial, serait tout simplement, la somme en bits, des tailles que prennent $n,m$ et $f$, ie $\displaystyle \vert n \vert + \vert m \vert + \sum_{i=1}^m \vert x_i \vert + \vert y_i \vert + \vert p_i \vert$, où $\vert x \vert$ est la taille de $x$ en bits.

lourrran

@Alesha
Dans le sudoku, il y a des lignes, des colonnes, et des blocs.
Dans le sudoku classique 9x9, les blocs sont des carrés 3x3

Si j'ai une grille 12x12, on peut  envisager des blocs rectangulaires, 3x4 ou 2x6, ok, admettons.
Si j'ai une grille 13x13, on peut  envisager des blocs biscornus, ok, admettons. Mais déjà, ça ne s'appelle plus Sudoku mais Suguru.
Et tout ça devient vite bordélique.

Questionneur s'intéresse aux grilles 'classiques, où les blocs sont des carrés. Les grilles sont donc de la forme $n^2 \times n^2$.

denise chemla

Bonsoir,

Je poste les sudoku qui nous avaient été donnés à l'IHES, lors d'une journée portes ouvertes, il y a quelques années.

Cordialement,

Denise Vella-Chemla