Pour deux graphes non isomorphes , existe-t-il une formule de premier ordre de profondeur de quantificateur polysize et polylog qui en témoigne?
Je veux être très précis. Quelqu'un connaît-il un rejet ou une preuve de la proposition suivante: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...