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 ...
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
Related Tags
polynomial-time × 410complexity-theory × 206
time-complexity × 100
algorithms × 82
np-complete × 49
reductions × 45
graphs × 36
np × 33
np-hard × 29
turing-machines × 27
satisfiability × 21
decision-problem × 17
p-vs-np × 15
computability × 14
algorithm-analysis × 13
approximation × 13
complexity-classes × 13
nondeterminism × 13
optimization × 12
runtime-analysis × 12
subset-sum × 9
terminology × 8
linear-programming × 8
circuits × 8
polynomial-time-reductions × 8