Pseudo-polynomial time

Summary

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless . The strong/weak kinds of NP-hardness are defined analogously. Examples Primality testing Consider the problem of testing whether a number n is prime, by naively checking whether no number

Official source

https://en.wikipedia.org/wiki/Pseudo-polynomial_time

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (37)

Related publications

Related people (4)

Related people

Related units (3)

Related units

Related concepts (5)

Related concepts

Related courses (9)

Related courses

Related lectures (17)

Related lectures

On the Application of Pseudo-Dynamic Tests

Andreas Galmarini

2002

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

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