Soit un graphe incrusté sur une surface compacte orientable du genre g pour que l'incorporation soit cellulaire. Considérons le dual du graphe G ∗ . Soit C 1 et C 2 des cycles disjoints dans G ∗ homotopiques l'un avec l'autre et soit E 1 et E 2 leurs ensembles de bords correspondants dans G...
Je recherche la dimension VC du système d'ensemble suivant. Univers tel que . Dans le système d'ensemble chaque ensemble correspond à une sphère dans sorte que l'ensemble contient un élément dans si et seulement si la sphère correspondante le contient dans
Dans une question précédente, Algorithme paramétré pour trouver des bicliques , je me suis demandé s'il y avait des algorithmes paramétrés rapides pour trouver un -biclique dans un graphe de sommets n et j'ai appris qu'il était ouvert s'il était FPT par rapport à k . Est-ce la même chose pour le...
Je voudrais m'excuser auprès de tous les articles ci-dessous. Vous avez choisi le mauvais forum pour publier cela à l'origine. Cependant, plutôt que d'en faire un gaspillage complet, j'ai retravaillé la question pour qu'elle soit un véritable problème "d'informatique théorique". Problème: Créez un...
Soit un carré unitaire. En fonction de , quel est le nombre maximum de -gras régions disjointes par paires de diamètre au moins 1 qui peuvent recouper ?SSSββ\betaββ\betaSSS Ci-dessous, nous donnons un chiffre montrant que pour , le nombre maximum est 7. Qu'en est-il de ?β= 1β=1\beta=1β= 2 , 3 , … ,...
Il existe certains problèmes NP-Complete ( , S U B S E T S U M , etc.) connus pour être dans D S P A C E ( n ) . Et les espaces sub-linéaires?SATSAT \mathsf{SAT} SUBSETSUMSUBSETSUM \mathsf{SUBSETSUM} DSPACE(n)DSPACE(n) \mathsf{DSPACE(n)} Existe-t-il un problème NP-complet (ou NP-intermédiaire)...
Par le titre, outre l'utilisation d'un solveur LP à usage général, existe-t-il une approche pour résoudre les systèmes d'inégalités sur les variables où les inégalités ont la forme ? Qu'en est-il du cas particulier des inégalités qui forment un ordre total sur les sommes des membres de l'ensemble...
C'est une question que j'ai posée dans le forum Mathématiques SE, et j'ai été référé ici. Voici donc la question- Je suis un débutant en mathématiques formelles et en informatique théorique, alors soyez indulgent avec vous si vous trouvez que ma question n'est pas bien formulée. La modélisation...
Supposons que nous ayons un graphe sur nnn nœuds. Nous aimerions attribuer à chaque nœud soit un +1+1+1 soit un −1−1−1 . Appelons cela une configuration σ∈{+1,−1}nσ∈{+1,−1}n\sigma \in \{+1,−1\}^n . Le nombre de +1+1+1 s que nous devons attribuer est exactement sss (d'où le nombre de −1−1−1 s est...
Je cherche un théorème qui dit quelque chose comme ceci: si le temps de couverture d'une chaîne de Markov réversible est petit, alors l'écart spectral est grand. Ici, l'écart spectral signifie c'est-à-dire que nous ignorons la plus petite valeur propre de la chaîne.1 - | λ2|1−|λ2|1-|\lambda_2| Le...
Modifier: il y a maintenant une question de suivi liée à ce message. Définitions Soit et entiers. Nous utilisons la notation .k [ i ] = { 1 , 2 , . . . , i }ccckkk[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\} Une matrice est dite matrice de coloration to- si les conditions suivantes sont...
J'ai posé ce problème dans MathOverflow , sans aucune réponse satisfaisante. Considérez le jeu à deux joueurs suivant, qui est une simplification du jeu de cartes appelé Winner . (La formulation suivante est tirée d'un commentaire de Guillaume Brunerie sur MathOverflow.) Il y a deux joueurs A et B....
Je recherche un algorithme pour dessiner un graphe mixte de circonscription / dépendance (pour une application linguistique). Un tel graphique aurait deux types de sommets différents (jetons, nœuds) et deux types d'arêtes différents (hiérarchique, non hiérarchique). Je suis nouveau dans la théorie...
J'ai eu du mal avec les détails techniques d'une preuve concernant la théorie des enchères dans cet article: http://users.eecs.northwestern.edu/~hartline/omd.pdf Plus précisément, le théorème 2.5: les conditions nécessaires et suffisantes pour un mécanisme véridique. Plus précisément, dans le sens...
Je travaille dans le domaine de l'ingénierie structurale et je voudrais trouver un algorithme efficace pour construire une approximation (dans la métrique de Hausdorff) d'un corps convexe par la coque convexe de n ellipsoïdes, pour certains n fixes . Actuellement je ne travaille que dans les...
Background––––––––––––––Background_\underline{\bf Background} En 2005, Regev [1] a introduit le problème d'apprentissage avec erreurs (LWE), une généralisation du problème de parité d'apprentissage avec erreur. L'hypothèse de la dureté de ce problème pour certains choix de paramètres sous-tend...
Ma question concerne la théorie des modèles finis / la complexité descriptive, donc signifiera "premier ordre sur des mots binaires finis, en utilisant des prédicats Rs et un prédicat unaire P vrai sur la position du 1 dans le mot".FO ( R )FO(R)FO(R) Je voudrais savoir, existe-t-il une...
Il s'agit d'une question douce visant à établir ce que les gens pensent être la meilleure pratique professionnelle pour soumettre des travaux non originaux sur l'arXiv. Il existe une ébauche d'un article [1] de Robert Szelepcsényi, dans son espace Web à l'Université de Chicago, apparemment écrit il...
Je sais que le temps d'exécution le plus défavorable attendu de l'algorithme de triangulation incrémentielle delaunay randomisé (tel que donné dans Computational Geometry ) est . Il y a un exercice qui implique que le pire temps d'exécution est Ω ( n 2 ) . J'ai essayé de construire un exemple où...
Soit une variable aléatoire prenant des valeurs dans (pour un grand alphabet ), qui a une entropie très élevée - disons,pour une constante arbitrairement petite . Soit un événement dans le support de tel que , où \ varepsilon est une constante arbitrairement