The EFF thinks Google is surrendering on allowing users to use Google+ without having their name and address tattooed on their foreheads wherever they go. JWZ is more suspicious, observing that whatever they're doing can't be the obvious solution (stop kicking people off for using pseudonyms), because that wouldn't take them so long to do, so it must be "some new and exciting way" of getting it wrong.

Me? I'm looking hard at this earlier post on mashable that this all seems based on, and not seeing any difference from past statements of Google nor any clear statement that they will actually support pseudonyms. I'll go back to posting on Google+ only when I actually see a policy and enforcement of that policy that I can agree with.




Comments:

ru_linux_geek:
2011-10-20T13:51:15Z
Wow, it's only after reading this post that I realize your nick moves from completely arbitrary byte sequence to kind geekily written initials.
11011110:
2011-10-20T15:08:39Z
Yep. So it's a variant of my real name.
itman:
2011-10-21T02:04:25Z
Nice! BTW, thank you for the references. Garey and Johnson indeed list this problem as a polynomial one. Unfortunately, they reference Lawler, which apparently does not consider this specific problem (but solves it among other of the same class). This is why, I still cannot verify this one (until I get much more free time). Well, anyway, it looks like Hopcroft et al have an error.
11011110:
2011-10-21T02:24:37Z
You mean the edge cover problem, right? What error? Garey and Johnson say that it's polynomial, Lawler says that it's polynomial, discuss the general technique, and leave the details for an exercise, and it is polynomial.
itman:
2011-10-21T03:03:14Z
Correct. I was confused, because Hopcroft et al (Introduction to Automata Theory, Languages, and Computation) claim that: "The problem of deciding whether a graph has an edge covering with k edges is NP-complete". Now I see now that it is not, indeed, a problem of finding a minimal edge covering. The optimization problem seems to be polynomial, but a yes-no problem seems to be NP-complete. Quite amazing.
11011110:
2011-10-24T23:00:06Z
Where do they say this? Because I'm looking at the vertex cover section (pages 331–332) but I don't see the edge cover problem there, nor anywhere else. But maybe you have a different edition (mine is Hopcroft and Ullman, 1979).
itman:
2011-10-25T00:09:20Z

Sorry, I should have mentioned that it's the second edition, Section 10.4.3: The Node Cover Problem, p 452:

For instance, an edge covering is a set of edges such that every node in the graph is an end of at least one edge in the set. ... The problem of deciding whether a graph has an edge covering with k-edges is NP-complete, although we shall not prove it here.

11011110:
2011-10-25T00:17:31Z
Ok, I think it's just a mistake then.
itman:
2011-10-25T00:26:39Z
O good! Thanks a lot for the clarification!
itman:
2011-10-21T14:07:08Z

Sorry for bothering you again. I am just trying to figure it out for myself and, perhaps, other people as well. On a second thought: if we know that a minimal edge covering requires k edges, and the graph has n edges, then we also know the following:

  1. no covering with l < k edges exist.
  2. any covering with k <= l <= n edges do exist, because we can just add some edges to the minimal edge cover!

Now the main question: does it mean that the problem: "if deciding whether a graph has an edge covering with k edges" cannot be NP-complete?

If the previous sentence is true, then the book Hopcroft et al has an error, which is worth fixing (adding to their errata).