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...
Il s'agit d'une continuation de ma question précédente sur les limites inférieures de communication pour les fonctions booléennes partielles . Quelqu'un peut-il suggérer une référence sur les limites inférieures pour la communication multipartite non déterministe? J'ai examiné les articles sur le...
Dana Angluin ( 1987 ; pdf ) définit un modèle d'apprentissage avec des requêtes d'appartenance et des requêtes théoriques (contre-exemples d'une fonction proposée). Elle montre qu'un langage régulier qui est représenté par un DFA minimal de états peut être appris en temps polynomial (où les...
Ceci fait suite à ma question précédente: Meilleure complexité temporelle déterministe connue borne inférieure pour un problème naturel dans NP Je trouve déconcertant que nous n'ayons pas été en mesure de prouver de limite inférieure de temps déterministe quadratique pour un problème NP intéressant...
En un mot, les théorèmes de la hiérarchie du temps disent qu'une machine de Turing peut résoudre plus de problèmes si elle a plus de temps pour le calcul. En détail pour TM déterministe et fonctions constructibles dans le temps avec c'est et pour TM non déterministe et fonctions constructibles dans...
Dans SODA 1995 , Jeff Erickson a montré des limites inférieures pour la satisfiabilité linéaire (vérifier si un certain ensemble de n nombres réels satisfait une équation linéaire sur r variables). La méthode de preuve utilise des infinitésimales et le principe de transfert de Tarski .rrrnnnrrr...
Soit HA L TnHALTnHALT_n la chaîne de longueur 2n2n2^n correspondant à la table de vérité du problème d'arrêt pour les entrées de longueur nnn . Si la séquence des complexités de Kolmogorov K( HA L Tn)K(HALTn)K(HALT_n) était O ( 1 )O(1)O(1) , alors l'une des chaînes de conseil serait utilisée...
Je voudrais connaître l'état actuel de la transition de phase pour les k-sat aléatoires, étant donné n variables et m clauses, quel est le c = m / n le mieux connu pour les bornes supérieures et
La question suivante est liée à l'optimalité de l' algorithme de programmation dynamique Bellman-Ford - plus court (voir cet article pour une connexion). En outre, une réponse positive impliquerait que la taille minimale d'un programme de branchement non déterministe monotone pour le problème...
Dans la complexité de l'arbre de décision d'une fonction booléenne, une méthode de borne inférieure très connue est de trouver un polynôme (approximatif) qui représente la fonction. Paturi a donné une caractérisation des fonctions booléennes symétriques (partielles et totales) en termes de quantité...
Je crois que les réponses à cette question donnent des classes telles que pour tous les polynômes , il y a un problème dans la classe qui n'a pas de circuits de taille . Cependant, je pose des questions sur la taille du circuit .p ( n ) ωpppp(n)p(n)p(n)ω(n)ω(n)\omega \hspace{.02 in}(n)...
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...
Il est bien connu que la complexité de la requête quantique d'erreur bornée de la fonction est Θ ( √O R ( x1, x2, … , Xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n). Maintenantla question est que si nous voulonsnotre algorithme quantique pour réussir à chaque entrée avecprobabilité1-εplutôt que...
Je suis confus. Je veux prouver que le problème du tri d'une matrice nnn par nnn c'est-à-dire que les lignes et les colonnes sont en ordre croissant est Ω(n2logn)Ω(n2logn)\Omega(n^2\log n) . Je continue en supposant que cela peut être fait plus rapidement que n2Journalnn2lognn^2\log n et j'essaie...
J'ai rencontré la question suivante, qui est un exercice facile (spoiler ci-dessous). On nous donne instances du problème d'arrêt (ie TMs ), et nous devons décider exactement lequel s'arrêtera sur . Autrement dit, nous devons afficher . On nous donne un oracle pour le problème d'arrêt, mais nous...
Deux piles peuvent être mises en œuvre efficacement en utilisant un tableau de taille fixe: la pile # 1 commence à partir de l'extrémité gauche et croît vers la droite, et la pile # 2 commence à partir de l'extrémité droite et croît vers la gauche. Est-ce la même chose possible pour trois piles?...