# Questions tagged [polynomial-time]

Use for algorithms, algorithm-analysis and complexity-theory questions that aim for polynomial running time resp. time complexity. Such questions often are are reference-requests or about runtime-analysis or time-complexity.

254 questions
Filter by
Sorted by
Tagged with
321 views

### Polynomially related lengths under two different encodings

I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this ...
249 views

### Find small superset of at least k of n given sets

Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets. Lets assume that $m$ is less than some ...
In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$ "Accepted in polynomial-time" is defined by:...
I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$. I'd like to know ...