New answers tagged polynomial-time
0
votes
Accepted
Question about the length of certificate of an polynommial-time verifier
Instead of a variable-length certificate $c$, you can always modify the certificate to have the form $\text{len}(c), c, 00\cdots 0$ where you append enough zeros to pad it out to the max length, thus ...
D.W.♦
- 150k
Top 50 recent answers are included
Related Tags
polynomial-time × 394complexity-theory × 197
time-complexity × 97
algorithms × 81
np-complete × 47
reductions × 43
graphs × 34
np × 30
turing-machines × 28
np-hard × 25
satisfiability × 20
decision-problem × 17
p-vs-np × 15
computability × 14
nondeterminism × 14
algorithm-analysis × 13
approximation × 13
runtime-analysis × 12
complexity-classes × 12
optimization × 11
terminology × 8
linear-programming × 8
circuits × 8
oracle-machines × 7
subset-sum × 7