New answers tagged

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 ...
Steven's user avatar
  • 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.'s user avatar
  • 156k

Top 50 recent answers are included