New answers tagged polynomial-time
2
votes
Pseudopolynomials and $NP$ problems like $CLIQUE$
The number $K$ of iterations of the loop is exponential in the size of the representation of $K$ (which is $\log K$) but it is polynomial in the size of the input of the problem.
The input of the ...
- 28.4k
1
vote
Accepted
Enumerating proper intersections
Yes. If there is any $C$ that works, then taking $C = c(i)$ works [*]. It is easy to compute $c(i)$ and then check if it satisfies your definition.
Better yet, the following is a simpler ...
D.W.♦
- 156k
Top 50 recent answers are included