Temps de calcul pseudo-polynomial

Résumé

En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée). Exemples Test de primalité Considérons le problème du test de primalité. On peut vérifier qu'un entier naturel donné n est premier en testant qu'il n'est divisible par aucun des entiers {2,3,\dots,\surd n}. Cela exige \surd n -1 divisions, de sorte que le temps pris par cet algorithme naïf est linéaire en la valeur n . Néanmoins, cet algorithme n'est pas efficace, comme on pourrait le penser d'un algorithme dit linéaire, puisqu’il demande déjà des milliards d'opérations sur une donnée de neuf chiffres décimaux. De fait, en théorie de la complexité, la complexité d'un algorithme est calculée en fonction de la longueur de l'entrée (et non pas de sa valeur), et cette longueur est généra

Source officielle

https://fr.wikipedia.org/wiki/Temps_de_calcul_pseudo-polynomial

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (37)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (4)

Personnes associées

Chargement

Unités associées (3)

Unités associées

Chargement

Concepts associés (5)

Concepts associés

Chargement

Cours associés (9)

Cours associés

Chargement

Séances de cours associées (17)

Séances de cours associées

Chargement

Publications associées (37)

On the Application of Pseudo-Dynamic Tests

Andreas Galmarini

2002

Chargement

Induced Matchings In Graphs Of Degree At Most 4

Viet Hang Nguyen

For a graph G, let nu(s)(G) be the strong matching number of G. We prove the sharp bound nu(s)(G) >= n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This result implies a strengthening of a consequence, namely, nu(s)(G) >= m(G)/18 for such graphs and nu(s)(G) >= m(G)/20 for a graph of maximum degree 4, of the well-known conjecture of Erdos and Nesetril, which says that the strong chromatic index chi(s)'(G) of a graph G is at most 5/4 Delta(G)(2), since nu(s)(G) >= m(G)/chi(s)'(G) and n(G) >= 2m(G)/Delta(G). This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size.

Siam Publications2016

Chargement

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes infeasible. In this work, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in binary linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between edges to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.

2009

Chargement

Afficher plus