Talk:St-connectivity

From Wikipedia, the free encyclopedia

"In particular, the problem of st-connectivity is actually NL-complete, that is, every problem in the class NL is reducible to connectivity under a log-space reduction. This remains true for the stronger case of first-order reductions (Immerman 1999, p. 51)."

This contradicts the article on First-order reduction which says that log-space reductions are stronger than first-order reductions. I've seen this a lot, I am not sure what the proper definitions of "weak" and "strong" reductions should be, but many articles are confused on this. --74.194.27.5 (talk) 13:44, 16 December 2007 (UTC)

No, they are both correct. First-order reduction is weaker than log-space, so saying something holds under first-order reductions is a stronger statement than saying the same thing holds under log space reductions. Suppose that A is a weaker assumption than B. This means that proving A -> C is a stronger statement than proving B -> C. The idea is that it's 'easy' to prove something with a powerful tool, so the statement is weaker. —Preceding unsigned comment added by 66.90.167.14 (talk) 07:25, 10 April 2008 (UTC)