hi,

checking a guess in proving SAT takes o(mn) where m is the number of clauses and n is the number of literals.

my questions:

1. converting from <fi> to fi takes o(1) time? can we assume that?

2. proving L in NP means we need to prove each "branch" takes polynomial time at most - but polynomial at what?

formulas - number of literals?

graphs - number of vertexes?

knapsack - ?

i'm having a little trouble understanding what does it mean polynomial at each type of a question.

thanks!