Quand je pense à un logiciel qui n'est pas sûr, je pense qu'il est "trop utile" et peut être utilisé abusivement par un attaquant. Donc, dans un sens, la sécurisation des logiciels est le processus qui rend les logiciels moins utiles. En informatique théorique, vous ne travaillez pas avec le...
Étant donné tout graphe simple non orienté G, il n'est pas trivial de déterminer si G a des automorphismes non triviaux (sans identité). Mais quels sont les résultats sur les bornes supérieures / inférieures de ce problème de
Barry Jay dans son livre fait des affirmations audacieuses - essentiellement en disant que, au cœur d'un programme, tout est atomique ou composé. Ensuite, les choses peuvent être facilement itérées, filtrées, mises à jour, simplement en parcourant cette relation de composition. Est-ce une nouvelle...
Le lemme de Johnson-Lindenstrauss dit grosso modo que pour toute collection de points dans , il existe une carte où tel que pour tout : Il est connu que des instructions similaires ne sont pas possibles pour la métrique , mais est-il connu s'il existe un moyen de contourner une telle baisse limites...
Je me demande si les classes NPC définies par plusieurs réductions et les réductions de Turing sont égales. Edit: Une autre question, est-ce que les réductions de Turing ne font que réduire les classes C et co-C pour certains C ou existe-t-il une classe telle qu'il existe un problème qui n'est pas...
Il est facile de regarder dans beaucoup de manuels les preuves de réduction de sujet et de forte normalisation pour le système F, aussi, il existe parfois des définitions du système F avec des paires, où (t, r) est un terme, pas seulement un encodage. La question est, quelle serait la référence...
Dans un graphique, un ensemble indépendant est un sous-ensemble de sommets qui ne contient pas d'arête comme sous-graphique induit. Le problème de trouver les plus grands ensembles indépendants dans un graphique est une question algorithmique fondamentale, et difficile à résoudre. Considérons la...
Quelle est la complexité temporelle exacte de l' algorithme d'espace de journalisation st-connectivité non orienté d'Omer
Je viens de commencer (indépendant) à apprendre le calcul quantique en général à partir du livre de Nielsen-Chuang. Je voulais demander si quelqu'un pouvait essayer de trouver du temps pour m'aider avec ce qui se passe avec le postulat de mesure de la mécanique quantique. Je veux dire, je n'essaie...
(X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow Yμμ\muρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}ρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)} \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \} Il existe cependant d'autres...
La motivation de cette question est le fait que la plupart des chaînes de n bits sont incompressibles. Intuitivement, nous pouvons proposer par analogie que la plupart des preuves pour les tautologies sont incompressibles à la taille polynomiale. Fondamentalement, mon intuition est que certaines...
Pendant un premier cycle en EE, j'ai assisté à des conférences qui présentaient une belle caractérisation des circuits booléens en termes de nombre de boucles imbriquées. En termes de complexité, les circuits booléens sont souvent considérés comme des creux, mais dans les cycles matériels réels,...
Je pense que la réponse à cette question est bien connue; mais, malheureusement, je ne sais pas. En informatique quantique, nous savons que les états mixtes sont représentés par des matrices de densité. Et la norme de trace de la différence de deux matrices de densité caractérise la distinction des...
Pour un graphe donné , le problème du séparateur demande s'il existe un ensemble de sommets ou d'arêtes de petite cardinalité (ou poids) dont la suppression divise G en deux graphes disjoints de tailles approximativement égales. C'est ce qu'on appelle le problème du séparateur de sommets lorsque...
J'ai développé une nouvelle technique de dérandomisation qui vise des algorithmes randomisés récursifs (ou) plus généralement des algorithmes randomisés qui utilisent une pile. Malheureusement, je n'ai pas pu trouver d'algorithmes aléatoires naturels pour appliquer mes techniques. Les chaînes de...
Imaginez un langage de programmation fonctionnel dont les seuls types de données sont des scalaires numériques et des imbrications arbitraires de tableaux. La langue ne dispose d'aucun moyen d'itération illimitée, les éléments suivants sont donc interdits: boucles explicites (pas très utiles sans...
Cela peut ressembler davantage à une question de sciences sociales qu'à une question TCS, mais ce n'est pas le cas. En lisant " Algorithmes randomisés " qui décrit le problème du mariage stable, on peut lire ce qui suit (p54) "On peut montrer que pour chaque choix de listes de préférences, il...
Dans la section 2.2 de Cache-Inconscient B-arbres , fortement poids équilibré Les arbres de recherche sont définis comme suit: Pour une constante , chaque nœud à la hauteur a des descendants .v h Θ ( d h )réddvvvhhhΘ ( dh)Θ(dh)\Theta(d^h) Ils affirment: Les arbres de recherche qui satisfont aux...
Je commence mes études de théorie des jeux algorithmiques, et il semble que le concept d'équilibre généralement utilisé est celui d'un point fixe dans un graphe. Cependant, les gens ont-ils envisagé d'autres concepts d'équilibre, tels que les cycles limites? Je peux imaginer qu'un cycle limite...
Je développe un algorithme SAT depuis un certain temps et j'ai atteint un point où j'aimerais le partager. Je ne connais pas beaucoup de gens en informatique et je ne sais pas exactement vers qui me tourner. Je me demande quelles ressources sont disponibles pour quelqu'un avec un algorithme qui...