> Last time I looked, copyright had expired on that particular piece of music several hundred years ago. Sigh.
On that particular piece of music sure, but was the rendition of that piece several hundred years old? No? I didn't think so....
According to dingman's description, his daughter holds copyright on the performance.
I think we fall into a design trap here, assuming that there is a fixed entity, called "Domain Name System," that must be preserved as a special entity, but can be modified.
Leave DNS as it is alone. Explore other services that may provide some or all of the utility that we now get from DNS.
DNS was designed to provide at least 2 different utilities:
1. Names, permanently assigned to particular agents, that can be redirected to different IP numbers over time.
2. Mnemonic names resolving to IP numbers.
The bundling of these two utilities in one system was controversial at the time, but it was easy to implement, and the problems with the bundling did not emerge until much later.
The first utility is important because IP numbers need to be assigned for efficient routing tables, and may be changed due to changes in network topology. Also, agents associated with particular names may need to move to different hosts. Domain names provide long-lived identifiers that can be reassigned to different IP numbers as needed. This use of DNS requires some global co-ordination, since the provider of the identifier->IP number binding is a different agent from the one who needs to look up the binding.
The second utility is important for efficient interaction with human users. It has lots of variations, some of which may be addressed on individual users' hosts, others of which are more global. The obvious use for a global co-ordination is to allow different agents to communicate the mnemonics. Bookmarks, local DNS servers, and search services (Google, Yahoo,...) provide variations of this service.
A large part of the trouble with DNS today is a conflict between the two uses. Competition for global mnemonic names raises the cost of permanent identifiers, and degrades their permanence when different agents win the competition at different times.
So, without doing anything to dismantle the current DNS, we should experiment with separate services that might provide some or all of the utility of DNS in other ways: particularly with different bundling. For mnemonic reference in Web browsing, Google has already essentially replaced DNS for me (yes, I know that most Google searches resolve to domain names, but they can also resolve to IP numbers, and a few do so; and in any case I do not depend on the mnemonic quality of the domain name). For mnemonic reference in email, my private address book has essentially replaced DNS (again, it usually resolves to domain names, but it doesn't have to).
The obvious missing element is a service providing permanent identifiers without the competition for particular mnemonics. A natural thing to try (suggested in a previous post, and in other forums over the years) is hashed public keys, since they prevent fishing for mnemonic identifiers. A system of identifiers based on hashed public keys, resolving to IP numbers, could also be part of the infrastructure for public key cryptography, suggesting a different bundling from the one in current DNS. There could be a quick and relatively easy implementation resolving hashed public keys using the current DNS software (but separate servers), with some additional scripting to allow automated registration. The registrant/resolver would make no effort whatsoever to vet the identity of the registrant, leaving that service to others when it is desired.
I am running a LAMP server (only the LA part active) with a few Web pages on my obsolete home desktop, with a slow ADSL connection. I don't have anything of serious value on the machine, so presumably an attacker would only benefit by using me as a bot. The system logs show regular access by the indexing services: Google, Yahoo,... and lots of what looks like simple-minded dictionary attacks, and some probes for SQL/PHP features that are not available. None of the login attacks appears to have found my user name, much less hit the password. I use a long password, generated by a random generator. That seems to be enough.
There is some chance that I am owned by someone I can't detect. But I never notice much activity on the CPU nor on the network, and my ISP doesn't complain that any bad behavior comes from my connection. If I suspected a problem, I would power off while considering my response.
I have tripwire installed, but every time I try to check it I get confused by the pass-phrase management and put it off.
This is where I buy music today: http://magnatune.com/
I bought their entire list, past present and future, in a lifetime subscription. I listen to everything, whether it's something I think I like or not. I like lots of it, and the rest expands my listening capacity.
your job is to not go to federal prison. good luck.
Actually, my job in the message that I posted was to discuss rational evidence, rather than what particular authorities will do in particular circumstances. I am very aware that inadequate evidence often works in practice.
To the point: your "test" doesn't test what I was talking about at all, but something quite different, though unfortunately connected in practice.
I just am not likely to have any sympathy for them if they end up having to defend themselves against accusations that are based from an IP address that they are supposedly responsible for.
You seem to have some strong, and questionable, assumptions about the responsibility of particular people for activities marked by particular IP addresses (or for particular Internet access points that they run---perhaps that's what you meant by "IP address"). This is a new sort of responsibility, and hasn't been mapped out carefully. I don't usually take responsibility for the behavior of people who walk down the sidewalk on my property, although I have responsibility to clear it of snow and ice. On the other hand, I would take greater responsibility for controlling access to a swimming pool in my yard. The right sort of responsibility for Internet access through a particular wire or wireless transceiver is not really obvious, and needs some careful thought. Many people, including myself, favor something closer to the sidewalk level of responsibility than the swimming pool level. Bruce Schneier is a much greater expert than I am, and I encourage you strongly to read his essay favoring unprotected wireless access (http://www.schneier.com/blog/archives/2008/01/my_open_wireles.html).
Apologies in advance: I can't resist a bit of silliness. In the famous monologue about Albert and the Lion (written by Marriott Edgar, most famous performance by Stan Holloway, who also portrayed Mr. Dolittle in My Fair Lady), a lion at the Blackpool zoo ate young Albert Ramsbottom. Mr. and Mrs. Ramsbottom went in front of the magistrate, "told 'im what happened to Albert, and proved it by showing his cap."
So we can go in front of a judge, claim that someone has violated a copyright, and prove it by showing his IP number?
the logic of “IP address = person” — which was once reasonably valid
That logic was never vaguely reasonable if the equation is taken to be a reliable identification for any legal purpose.
If someone comes into court with an IP number, one needs to know a whole lot about how that number was discovered in order to consider giving them any credibility in associating some misbehavior with a person who is supposedly associated with that number. Mere knowledge of my name, or my car's license plate number, or my US mail address, or even an envelope with my US mail address on it, doesn't associate me reliably with any particular behavior. I couldn't find any mention in TFA of the evidence that the IP numbers quoted in court were used by any particular person to violate any particular law. I haven't found such information in other articles on this topic, nor in some court documents that I read. There could be such evidence (with different required strengths for different sorts of legal actions), but it is not a simple thing and it needs a thorough explanation.
What sort of packet was collected with the allegedly offending IP number? Was that number the destination or the return address? Was the collection itself legitimate, or was it an illegal act of eavesdropping? What evidence (not neccessarily strong evidence, maybe just prima facie) indicates that the IP number was written into that packet due to some illegal action by a person associated through an ISP with that number? Until I see some serious explanations of these points, I can't develop much sympathy for the demand that an ISP identify a customer, much less for an accusation against that customer.
for people who run unlocked wireless routers and let anybody in the neighborhood utilize their bandwidth, I have zero sympathy.
Before showing contempt for those who run open wireless nodes, please read
what Bruce Schneier writes about the courtesy of sharing network access.
I'm just a hard-ass who follows the rules
Perhaps you follow some set of rules that you picked up somewhere, but there is no compelling foundation in law or ethics for requiring restricted access on network nodes.
The detailed technicalities get tricky here. Some things that we say in conversation (including the trained specialists) aren't quite right based on the official definitions, but we correct them automatically in our heads.
i think you can always transform the optimization problem into the decision problem, by asking if there is an solution less than an arbitrary n.
Every optimization problem (such as my TSP 1) can be turned into a decision yes/no problem (such as my TSP 2) as you describe. The optimization problem is always at least as hard as the decision problem. But in principle the decision problem may be much easier. I don't have an example in mind, and the optimization problems that we tend to think of naturally are usually tightly linked to the corresponding decision problems, so that both have essentially the same complexity. But this depends on the detailed structure of the optimization problem.
In the case of TSP, if we are given a function to solve the decision problem, we can first do a binary search to discover the exact cost of the optimal path. Then, we can remove an edge from the graph, and ask whether there is still a path of that cost. If so, we can forget about that edge. If not, that edge is a part of every optimal path. Repeating the process, we eventually get a set of edges (not always unique, but that doesn't matter) that are all involved in one particular optimal path. Then, it's easy to construct one optimal path.
Not every optimization problem allows a solution to be found efficiently using a function call to test the existence of a solution. This is a sort of "self-reducibility" that needs to be proved in each individual case.
The real question for a NP-hard problem is: Can it be solved by a non-deterministic turing-machine in polynomial time?
Technically, the answer for an optimization problem is always "no," because NDTMs only solve decision problems. The output mechanism only allows a single bit. In the language of the Wikipedia article cited above, the corresponding question for a general problem (not a decision problem) is whether it is "NP-Easy": that is, can it be solved by a deterministic TM in polynomial time, using free function calls to decision procedures implemented by NDTMs. This is such a natural extension of "solved by a NDTM" that we all neglect the difference in some cases, but it can be confusing. And notice that the NP-Easiness of an optimization problem does not automatically follow from the NPness of the corresponding decision problem---it requires the sort of self-reducibility that I illustrated with TSP above.
There are many Problems, which can not be solved in P, but cannot even be solved in NP, so you need to show it CAN be solved in NP, then its NP-complete.
Right, that's the crux of the remaining issue, modulo the quibbles about terminology. Someone sketched a proof above, which can probably be completed into a correct proof, that Euclidean TSP decision problem reduces to PTSP decision problem, which would make PTSP decision problem and optimization problem NP-Hard (along with TSP). I suggested a reduction in the other direction, using a natural Hilbert space for the PTSP map, which might show that PTSP decision problem is in NP, and which would almost surely be extendible by a self-reduction to show that PTSP optimization is NP-easy. But there are enough gaps in my suggestion, and even ambiguities in the definition of PTSP (regarding the treatment of real numbers) that I don't regard the question as settled yet.
We've spoken at cross purposes a bit. There are two things commonly referred to as TSP:
Given a graph, find the shortest path visiting every node precisely once;
Given a graph and a number n, determine whether it is possible to visit every node on a path of length at most n.
Both of these are NP-Hard. The definition of NP-Complete refers only to yes/no problems, so it can't be applied to number 1. But people commonly say that TSP version 1 is NP-Complete since version 2 is NP-Complete, and a solution to version 2, used as a subroutine, gives a polynomial solution to version 1.
Using the naming conventions of the Wikipedia article (http://en.wikipedia.org/wiki/Np-hard#NP-naming_convention), TSP version 1 is NP-Hard and NP-Easy, therefore NP-Equivalent. NP-Equivalent yes/no problems are called "NP-Complete." Even the most specialized of specialists in Complexity Theory find it hard not to say "NP-Complete" when they mean "NP-Equivalent."
First, the "PTSP" (somewhat misleadingly named, since it uses video game physicsrather than realistic physics) appears to rely on a planar Euclidean map, so it might best be compared to the Euclidean Travelling Salemsan Problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP), which is NP-complete but susceptible to polynomial time approximations (and pretty good ones in practice, I think).
The right sort of graph for a TSP corresponding to a given PTSP map is probably based on a Hilbert space with 5 or 6 dimensions: the 2 planar dimensions of the PTSP map, the 2 dimensions of the velocity vector, and 1 or 2 dimensions to represent the orientation (there's 1 degree of freedom, but it might be better to use the sin-cos vector).
The precise status of "PTSP" probably depends on the exact treatment of the real number calculations. As noted by dperez above, solving the obviously corresponding TSP (Euclidean distances on the same planar map) doesn't yield the optimum solution for the PTST. But you'd get a pretty bad grade in your algorithms/complexity class if you did it that obviously wrong way. An interesting algorithms question is whether there is another graph, derivable from the PTSP map, whose TSP solution yields an optimal play for the PTSP.
If we assume exact real number calculations, and the ability to use any real number value for a rotational angle, then I am pretty sure that each PTSP yields a TSP based on a Hilbert space and the solution to the TSP gives an optimal play for the PTSP. The basic idea is to precompute several paths for each pair of nodes, each one optimal for video game physics given a certain starting velocity. Each node of the original PTSP map corresponds to a set of nodes for the corresponding TSP, each with a different starting velocity. To knit things perfectly, there are some additional nodes with low-cost connections so that a visit to any one of the copies of the PTSP node allows a cheap visit to all of the copies. Notice that this derived TSP is not Euclidean, but the underlying Euclidean space probably leads to some good approximations.
There are lots of details to work out there, and they might be difficult. The precomputation might be easy or hard to approximate, depending on exactly what sort of optimization it amounts to. If it can be done with some sort of least squares problem, then it can probably be approximated well enough to win.
What if we assume exact real number calculations, and ask for an algorithm that uses them? This changes the computing model underlying NP-completeness, but it's probably been done somewhere. (Can anyone find a citation? I didn't see anything relevant in the Wikipedia article on TSP.) In that case, the difficulty probably hinges on the finite solvability of the "precomputation" mentioned above, and it might be anything from quick (e.g. least squares) to infinite (requiring iterative approximation).
If we take the floating point approximations in the video game physics seriously, then the PTSP almost certainly corresponds to a TSP on a larger graph. The larger graph might have to be as large as the full grid of Hilbert-space points with floating point co-ordinates, but I'm betting that it can be cut down a lot in most or all cases. This derived TSP probably has good approximations due to the underlying grid, but it doesn't appear to satisfy the well-known metric approaches, such as Manhattan metric, exactly. It appears to be polynomially related to the PTSP map, but possibly with a practically huge increase in size.
In any case, dperez's claim:
This makes the problem harder than just applying one of the very well known techniques to solve the TSP.
("This" being the fact that the TSP solution on the same graph is not optimal for PTSP) is nonsense. The PTSP as given could be easier, harder, or equivalent to TSP. Being charitable, dperez probably just means that it isn't obvious how to win the PTSP challenge using a known TSP approximation. Sure. But w
If they had thought they owed you money you would not have heard a word.
But you are right that I still haven't heard from the IRS regarding the large refund to my deceased father's account that they goofed up in direct deposit (while the state refund using the same information succeeded) for tax year 2009 (when he was still alive). The paid accountant, whom I will not name because they are about as good as others in the business, has done nothing effective to get the refund from the return which they filed for pay.
They thought you owed them money so they went for your ass.
No, they knew that they owed me money. They made it very clear that the penalty had nothing to do with the fact that they had cashed my check months ago. They credited my refund against the penalty.
I paid for the TaxAct Ultimate Bundle, followed their instructions for getting an extension to the filing deadline, overpaid my taxes with the extension request, did everything that any of the software or correspondence directed, and got a huge fine from IRS. TaxAct declined to help in any way.
I still use TaxAct for lack of something better, but I don't trust their instructions completely.
I filed my 2010 taxes through TaxAct Online Ultimate Bundle (the version you pay a bit for and it includes a state return). I requested an extension, following the instructions associated with the software. The electronic extension request bounced for unclear reasons, and I was notified of the failure after the filing deadline passed. I resorted to a paper request for extension. I paid an overestimate of the tax I might owe along with the extension request. I relied on written instructions from TaxAct that the recorded attempt at an electronically authorized extension satisfied the filing deadline, and that the subsequent written request was proper even though mailed a day after the deadline.
I heard nothing from IRS for months. I filed my final return well in advance of the extended deadline, and asked for a refund of my overpayment. I was assessed a huge fine, based on the total amount of tax that I had already paid on time, multiplied by the time between the deadline and the final filing.
I appealed to TaxAct for help and they just referred me back to IRS. IRS had no comment regarding the instructions from TaxAct, although they had made special arrangements with TaxAct to receive electronic filings. IRS eventually forgave the penalties, with a letter saying that I was in the wrong, but they would let it go this time, and I shouldn't expect such leniency again for myself or anyone else.
I still use TaxAct because the alternatives that I have tried are worse. I make sure that I have acknowledgment of filing before the deadline, and I have a backup plan to send paper copies on the deadline if I have not received acknowledgment.
Thanks for the advice, but I studied the issue quite a bit, and read the careful insights from Bruce Schneier (http://www.schneier.com/blog/archives/2008/01/my_open_wireles.html), and I decided that I don't want to treat any portion of the world-connected IP network as my personal domain. I carefully chose an ISP (Speakeasy) who allows, and even caters to, sharing.
I have no interest in convincing you to take my attitude. But you should be aware that it isn't necessarily a matter of naivety.
I posted a comment below regarding Meraki wireless boxes that did this in 2007. I never experienced an actual deployment, but there must have been some.
I can't tell if you are joking or being sarcastic here. I'm pretty sure that you have just described a business model in actual use. It seemed to be promoted by Meraki as a way to make money with their wireless boxes.
I also believe that there was a dispute some years ago regarding television broadcasts inserting advertisements as if they were posted on the fences at baseball stadiums.
I would greatly appreciate reliable pointers that anyone could provide to these behaviors. I will try to find some later. For now, this is what I remember, and I think it's right, but it hasn't been checked.
In November 2007, I bought a wireless box from Meraki (http://www.meraki.com/). I intended to use it to provide a free wireless hotspot for my neighborhood, and to be ready to peer with any neighbor who chose to work on the grassroots network. These were primarily symbolic acts, since neither service is likely to get much use in my neighborhood.
In most respects, the Meraki box appeared to do a good job of exactly what I wanted. But I noticed a little blank stripe at the top of Web pages. I found that Meraki hacked HTTP packets to add that stripe. As owner, I was able to set the contents of the stripe (e.g., to advertise myself as the provider of the free hotspot, or to ask for payment if it's not free). But, I was not able to eliminate the stripe. I called support, and they confirmed that the stripe is not optional, but its contents are owner controlled. I sent the box back for a refund. I understand why Meraki provided the feature (I don't like it, but I understand). I don't understand why they made it impossible to turn it off. They were very good about delivery, support, and refund in all other respects.
I think that Open Mesh (http://www.open-mesh.com/) provides something like the Meraki box, but cheaper and transparent to all Internet traffice. I have not tried their products yet.
For the time being, I just leave my Tomato (http://www.polarcloud.com/tomato) box unprotected, and I think that people occasionally park in front of my house to use the network. But there's no chance of peering to help avoid the last-mile bottleneck.
What analogy? I don't think I used one. I argued against the license plate analogy.
On the internet you need packets to come back to your machine.
Depends on what you're doing. And, your needs may not be met. You seem to be arguing that it is unlikely that someone would want to put in my IP number on a packet sent to a file sharing service. That's probably right. But that doesn't make the presence of my IP number evidence that I put it there. Positive evidence that I am violating copyright shouldn't depend on assumptions about the intentions and competence of all other producers of packets. Errors, by myself and by other people, are possible, as well as deliberate use of the wrong IP number.
As long as it is easy for anyone to put any IP number on any packet and send it anywhere, which is a clear fact resulting from the simplicity of IP and the lack of authentication in IP, then the mere presence of an IP number in a packet is not positive evidence that any particular person caused that packet to be generated. The difficulty of imagining other reasons for the IP number to be there doesn't turn it into positive evidence.
In fact, I think that it is probably possible to present substantial evidence that particular file sharing is properly attributed to the host using a particular IP number. But nothing in this article, nor in other articles that I've read on similar cases, suggests that such evidence has been presented. On the contrary, they suggest that the plaintiff's claim that she has a copy of a packet with a certain IP number and that that packet was found in certain traffic with a file sharing service is the whole evidence. It isn't enough.
The writer of a false IP number doesn't need to be performing any file sharing. In fact, whatever anyone thinks or doesn't think, it is very easy to put any IP number on any packet and send it anywhere. I am expressing definite knowledge here, not idle opinion.
The plaintiffs may have evidence of actual participation in actual sharing of actual material for which they hold copyright and have not authorized sharing. But nothing in the article indicates what that evidence is.
The court appears to have accepted the likelihood that there is evidence of infringement, but they don't explain what that evidence is.
Slashdot Mirror
> Last time I looked, copyright had expired on that particular piece of music several hundred years ago. Sigh. On that particular piece of music sure, but was the rendition of that piece several hundred years old? No? I didn't think so....
According to dingman's description, his daughter holds copyright on the performance.
Large bucket full of cold water. Insert bare feet.
I think we fall into a design trap here, assuming that there is a fixed entity, called "Domain Name System," that must be preserved as a special entity, but can be modified.
Leave DNS as it is alone. Explore other services that may provide some or all of the utility that we now get from DNS.
DNS was designed to provide at least 2 different utilities:
The bundling of these two utilities in one system was controversial at the time, but it was easy to implement, and the problems with the bundling did not emerge until much later.
The first utility is important because IP numbers need to be assigned for efficient routing tables, and may be changed due to changes in network topology. Also, agents associated with particular names may need to move to different hosts. Domain names provide long-lived identifiers that can be reassigned to different IP numbers as needed. This use of DNS requires some global co-ordination, since the provider of the identifier->IP number binding is a different agent from the one who needs to look up the binding.
The second utility is important for efficient interaction with human users. It has lots of variations, some of which may be addressed on individual users' hosts, others of which are more global. The obvious use for a global co-ordination is to allow different agents to communicate the mnemonics. Bookmarks, local DNS servers, and search services (Google, Yahoo, ...) provide variations of this service.
A large part of the trouble with DNS today is a conflict between the two uses. Competition for global mnemonic names raises the cost of permanent identifiers, and degrades their permanence when different agents win the competition at different times.
So, without doing anything to dismantle the current DNS, we should experiment with separate services that might provide some or all of the utility of DNS in other ways: particularly with different bundling. For mnemonic reference in Web browsing, Google has already essentially replaced DNS for me (yes, I know that most Google searches resolve to domain names, but they can also resolve to IP numbers, and a few do so; and in any case I do not depend on the mnemonic quality of the domain name). For mnemonic reference in email, my private address book has essentially replaced DNS (again, it usually resolves to domain names, but it doesn't have to).
The obvious missing element is a service providing permanent identifiers without the competition for particular mnemonics. A natural thing to try (suggested in a previous post, and in other forums over the years) is hashed public keys, since they prevent fishing for mnemonic identifiers. A system of identifiers based on hashed public keys, resolving to IP numbers, could also be part of the infrastructure for public key cryptography, suggesting a different bundling from the one in current DNS. There could be a quick and relatively easy implementation resolving hashed public keys using the current DNS software (but separate servers), with some additional scripting to allow automated registration. The registrant/resolver would make no effort whatsoever to vet the identity of the registrant, leaving that service to others when it is desired.
I am running a LAMP server (only the LA part active) with a few Web pages on my obsolete home desktop, with a slow ADSL connection. I don't have anything of serious value on the machine, so presumably an attacker would only benefit by using me as a bot. The system logs show regular access by the indexing services: Google, Yahoo, ... and lots of what looks like simple-minded dictionary attacks, and some probes for SQL/PHP features that are not available. None of the login attacks appears to have found my user name, much less hit the password. I use a long password, generated by a random generator. That seems to be enough.
There is some chance that I am owned by someone I can't detect. But I never notice much activity on the CPU nor on the network, and my ISP doesn't complain that any bad behavior comes from my connection. If I suspected a problem, I would power off while considering my response.
I have tripwire installed, but every time I try to check it I get confused by the pass-phrase management and put it off.
Check it out in Cory Doctorow's Someone Comes to Town, Someone Leaves Town .
Sure, it's only fiction. But my home wireless, which I invite you to use whenever you're within range, is called ParasiteNet.
This is where I buy music today: http://magnatune.com/ I bought their entire list, past present and future, in a lifetime subscription. I listen to everything, whether it's something I think I like or not. I like lots of it, and the rest expands my listening capacity.
your job is to not go to federal prison. good luck.
Actually, my job in the message that I posted was to discuss rational evidence, rather than what particular authorities will do in particular circumstances. I am very aware that inadequate evidence often works in practice.
To the point: your "test" doesn't test what I was talking about at all, but something quite different, though unfortunately connected in practice.
I just am not likely to have any sympathy for them if they end up having to defend themselves against accusations that are based from an IP address that they are supposedly responsible for.
You seem to have some strong, and questionable, assumptions about the responsibility of particular people for activities marked by particular IP addresses (or for particular Internet access points that they run---perhaps that's what you meant by "IP address"). This is a new sort of responsibility, and hasn't been mapped out carefully. I don't usually take responsibility for the behavior of people who walk down the sidewalk on my property, although I have responsibility to clear it of snow and ice. On the other hand, I would take greater responsibility for controlling access to a swimming pool in my yard. The right sort of responsibility for Internet access through a particular wire or wireless transceiver is not really obvious, and needs some careful thought. Many people, including myself, favor something closer to the sidewalk level of responsibility than the swimming pool level. Bruce Schneier is a much greater expert than I am, and I encourage you strongly to read his essay favoring unprotected wireless access (http://www.schneier.com/blog/archives/2008/01/my_open_wireles.html).
Apologies in advance: I can't resist a bit of silliness. In the famous monologue about Albert and the Lion (written by Marriott Edgar, most famous performance by Stan Holloway, who also portrayed Mr. Dolittle in My Fair Lady), a lion at the Blackpool zoo ate young Albert Ramsbottom. Mr. and Mrs. Ramsbottom went in front of the magistrate, "told 'im what happened to Albert, and proved it by showing his cap."
So we can go in front of a judge, claim that someone has violated a copyright, and prove it by showing his IP number?
From TFA:
the logic of “IP address = person” — which was once reasonably valid
That logic was never vaguely reasonable if the equation is taken to be a reliable identification for any legal purpose.
If someone comes into court with an IP number, one needs to know a whole lot about how that number was discovered in order to consider giving them any credibility in associating some misbehavior with a person who is supposedly associated with that number. Mere knowledge of my name, or my car's license plate number, or my US mail address, or even an envelope with my US mail address on it, doesn't associate me reliably with any particular behavior. I couldn't find any mention in TFA of the evidence that the IP numbers quoted in court were used by any particular person to violate any particular law. I haven't found such information in other articles on this topic, nor in some court documents that I read. There could be such evidence (with different required strengths for different sorts of legal actions), but it is not a simple thing and it needs a thorough explanation.
What sort of packet was collected with the allegedly offending IP number? Was that number the destination or the return address? Was the collection itself legitimate, or was it an illegal act of eavesdropping? What evidence (not neccessarily strong evidence, maybe just prima facie) indicates that the IP number was written into that packet due to some illegal action by a person associated through an ISP with that number? Until I see some serious explanations of these points, I can't develop much sympathy for the demand that an ISP identify a customer, much less for an accusation against that customer.
for people who run unlocked wireless routers and let anybody in the neighborhood utilize their bandwidth, I have zero sympathy.
Before showing contempt for those who run open wireless nodes, please read what Bruce Schneier writes about the courtesy of sharing network access.
I'm just a hard-ass who follows the rules
Perhaps you follow some set of rules that you picked up somewhere, but there is no compelling foundation in law or ethics for requiring restricted access on network nodes.
The detailed technicalities get tricky here. Some things that we say in conversation (including the trained specialists) aren't quite right based on the official definitions, but we correct them automatically in our heads.
i think you can always transform the optimization problem into the decision problem, by asking if there is an solution less than an arbitrary n.
Every optimization problem (such as my TSP 1) can be turned into a decision yes/no problem (such as my TSP 2) as you describe. The optimization problem is always at least as hard as the decision problem. But in principle the decision problem may be much easier. I don't have an example in mind, and the optimization problems that we tend to think of naturally are usually tightly linked to the corresponding decision problems, so that both have essentially the same complexity. But this depends on the detailed structure of the optimization problem.
In the case of TSP, if we are given a function to solve the decision problem, we can first do a binary search to discover the exact cost of the optimal path. Then, we can remove an edge from the graph, and ask whether there is still a path of that cost. If so, we can forget about that edge. If not, that edge is a part of every optimal path. Repeating the process, we eventually get a set of edges (not always unique, but that doesn't matter) that are all involved in one particular optimal path. Then, it's easy to construct one optimal path.
Not every optimization problem allows a solution to be found efficiently using a function call to test the existence of a solution. This is a sort of "self-reducibility" that needs to be proved in each individual case.
The real question for a NP-hard problem is: Can it be solved by a non-deterministic turing-machine in polynomial time?
Technically, the answer for an optimization problem is always "no," because NDTMs only solve decision problems. The output mechanism only allows a single bit. In the language of the Wikipedia article cited above, the corresponding question for a general problem (not a decision problem) is whether it is "NP-Easy": that is, can it be solved by a deterministic TM in polynomial time, using free function calls to decision procedures implemented by NDTMs. This is such a natural extension of "solved by a NDTM" that we all neglect the difference in some cases, but it can be confusing. And notice that the NP-Easiness of an optimization problem does not automatically follow from the NPness of the corresponding decision problem---it requires the sort of self-reducibility that I illustrated with TSP above.
There are many Problems, which can not be solved in P, but cannot even be solved in NP, so you need to show it CAN be solved in NP, then its NP-complete.
Right, that's the crux of the remaining issue, modulo the quibbles about terminology. Someone sketched a proof above, which can probably be completed into a correct proof, that Euclidean TSP decision problem reduces to PTSP decision problem, which would make PTSP decision problem and optimization problem NP-Hard (along with TSP). I suggested a reduction in the other direction, using a natural Hilbert space for the PTSP map, which might show that PTSP decision problem is in NP, and which would almost surely be extendible by a self-reduction to show that PTSP optimization is NP-easy. But there are enough gaps in my suggestion, and even ambiguities in the definition of PTSP (regarding the treatment of real numbers) that I don't regard the question as settled yet.
We've spoken at cross purposes a bit. There are two things commonly referred to as TSP:
Both of these are NP-Hard. The definition of NP-Complete refers only to yes/no problems, so it can't be applied to number 1. But people commonly say that TSP version 1 is NP-Complete since version 2 is NP-Complete, and a solution to version 2, used as a subroutine, gives a polynomial solution to version 1.
Using the naming conventions of the Wikipedia article (http://en.wikipedia.org/wiki/Np-hard#NP-naming_convention), TSP version 1 is NP-Hard and NP-Easy, therefore NP-Equivalent. NP-Equivalent yes/no problems are called "NP-Complete." Even the most specialized of specialists in Complexity Theory find it hard not to say "NP-Complete" when they mean "NP-Equivalent."
TSP is NP-Complete, which means that it is NP-Hard and it is in NP. The definitions are a bit confusing in casual use.
First, the "PTSP" (somewhat misleadingly named, since it uses video game physicsrather than realistic physics) appears to rely on a planar Euclidean map, so it might best be compared to the Euclidean Travelling Salemsan Problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP), which is NP-complete but susceptible to polynomial time approximations (and pretty good ones in practice, I think).
The right sort of graph for a TSP corresponding to a given PTSP map is probably based on a Hilbert space with 5 or 6 dimensions: the 2 planar dimensions of the PTSP map, the 2 dimensions of the velocity vector, and 1 or 2 dimensions to represent the orientation (there's 1 degree of freedom, but it might be better to use the sin-cos vector).
The precise status of "PTSP" probably depends on the exact treatment of the real number calculations. As noted by dperez above, solving the obviously corresponding TSP (Euclidean distances on the same planar map) doesn't yield the optimum solution for the PTST. But you'd get a pretty bad grade in your algorithms/complexity class if you did it that obviously wrong way. An interesting algorithms question is whether there is another graph, derivable from the PTSP map, whose TSP solution yields an optimal play for the PTSP.
If we assume exact real number calculations, and the ability to use any real number value for a rotational angle, then I am pretty sure that each PTSP yields a TSP based on a Hilbert space and the solution to the TSP gives an optimal play for the PTSP. The basic idea is to precompute several paths for each pair of nodes, each one optimal for video game physics given a certain starting velocity. Each node of the original PTSP map corresponds to a set of nodes for the corresponding TSP, each with a different starting velocity. To knit things perfectly, there are some additional nodes with low-cost connections so that a visit to any one of the copies of the PTSP node allows a cheap visit to all of the copies. Notice that this derived TSP is not Euclidean, but the underlying Euclidean space probably leads to some good approximations.
There are lots of details to work out there, and they might be difficult. The precomputation might be easy or hard to approximate, depending on exactly what sort of optimization it amounts to. If it can be done with some sort of least squares problem, then it can probably be approximated well enough to win.
What if we assume exact real number calculations, and ask for an algorithm that uses them? This changes the computing model underlying NP-completeness, but it's probably been done somewhere. (Can anyone find a citation? I didn't see anything relevant in the Wikipedia article on TSP.) In that case, the difficulty probably hinges on the finite solvability of the "precomputation" mentioned above, and it might be anything from quick (e.g. least squares) to infinite (requiring iterative approximation).
If we take the floating point approximations in the video game physics seriously, then the PTSP almost certainly corresponds to a TSP on a larger graph. The larger graph might have to be as large as the full grid of Hilbert-space points with floating point co-ordinates, but I'm betting that it can be cut down a lot in most or all cases. This derived TSP probably has good approximations due to the underlying grid, but it doesn't appear to satisfy the well-known metric approaches, such as Manhattan metric, exactly. It appears to be polynomially related to the PTSP map, but possibly with a practically huge increase in size.
In any case, dperez's claim:
This makes the problem harder than just applying one of the very well known techniques to solve the TSP.
("This" being the fact that the TSP solution on the same graph is not optimal for PTSP) is nonsense. The PTSP as given could be easier, harder, or equivalent to TSP. Being charitable, dperez probably just means that it isn't obvious how to win the PTSP challenge using a known TSP approximation. Sure. But w
If they had thought they owed you money you would not have heard a word.
But you are right that I still haven't heard from the IRS regarding the large refund to my deceased father's account that they goofed up in direct deposit (while the state refund using the same information succeeded) for tax year 2009 (when he was still alive). The paid accountant, whom I will not name because they are about as good as others in the business, has done nothing effective to get the refund from the return which they filed for pay.
They thought you owed them money so they went for your ass.
No, they knew that they owed me money. They made it very clear that the penalty had nothing to do with the fact that they had cashed my check months ago. They credited my refund against the penalty.
I paid for the TaxAct Ultimate Bundle, followed their instructions for getting an extension to the filing deadline, overpaid my taxes with the extension request, did everything that any of the software or correspondence directed, and got a huge fine from IRS. TaxAct declined to help in any way.
I still use TaxAct for lack of something better, but I don't trust their instructions completely.
This is personal experience, not speculation.
I filed my 2010 taxes through TaxAct Online Ultimate Bundle (the version you pay a bit for and it includes a state return). I requested an extension, following the instructions associated with the software. The electronic extension request bounced for unclear reasons, and I was notified of the failure after the filing deadline passed. I resorted to a paper request for extension. I paid an overestimate of the tax I might owe along with the extension request. I relied on written instructions from TaxAct that the recorded attempt at an electronically authorized extension satisfied the filing deadline, and that the subsequent written request was proper even though mailed a day after the deadline.
I heard nothing from IRS for months. I filed my final return well in advance of the extended deadline, and asked for a refund of my overpayment. I was assessed a huge fine, based on the total amount of tax that I had already paid on time, multiplied by the time between the deadline and the final filing.
I appealed to TaxAct for help and they just referred me back to IRS. IRS had no comment regarding the instructions from TaxAct, although they had made special arrangements with TaxAct to receive electronic filings. IRS eventually forgave the penalties, with a letter saying that I was in the wrong, but they would let it go this time, and I shouldn't expect such leniency again for myself or anyone else.
I still use TaxAct because the alternatives that I have tried are worse. I make sure that I have acknowledgment of filing before the deadline, and I have a backup plan to send paper copies on the deadline if I have not received acknowledgment.
Thanks for the advice, but I studied the issue quite a bit, and read the careful insights from Bruce Schneier (http://www.schneier.com/blog/archives/2008/01/my_open_wireles.html), and I decided that I don't want to treat any portion of the world-connected IP network as my personal domain. I carefully chose an ISP (Speakeasy) who allows, and even caters to, sharing.
I have no interest in convincing you to take my attitude. But you should be aware that it isn't necessarily a matter of naivety.
I posted a comment below regarding Meraki wireless boxes that did this in 2007. I never experienced an actual deployment, but there must have been some.
I can't tell if you are joking or being sarcastic here. I'm pretty sure that you have just described a business model in actual use. It seemed to be promoted by Meraki as a way to make money with their wireless boxes.
I also believe that there was a dispute some years ago regarding television broadcasts inserting advertisements as if they were posted on the fences at baseball stadiums.
I would greatly appreciate reliable pointers that anyone could provide to these behaviors. I will try to find some later. For now, this is what I remember, and I think it's right, but it hasn't been checked.
In November 2007, I bought a wireless box from Meraki (http://www.meraki.com/). I intended to use it to provide a free wireless hotspot for my neighborhood, and to be ready to peer with any neighbor who chose to work on the grassroots network. These were primarily symbolic acts, since neither service is likely to get much use in my neighborhood.
In most respects, the Meraki box appeared to do a good job of exactly what I wanted. But I noticed a little blank stripe at the top of Web pages. I found that Meraki hacked HTTP packets to add that stripe. As owner, I was able to set the contents of the stripe (e.g., to advertise myself as the provider of the free hotspot, or to ask for payment if it's not free). But, I was not able to eliminate the stripe. I called support, and they confirmed that the stripe is not optional, but its contents are owner controlled. I sent the box back for a refund. I understand why Meraki provided the feature (I don't like it, but I understand). I don't understand why they made it impossible to turn it off. They were very good about delivery, support, and refund in all other respects.
I think that Open Mesh (http://www.open-mesh.com/) provides something like the Meraki box, but cheaper and transparent to all Internet traffice. I have not tried their products yet.
For the time being, I just leave my Tomato (http://www.polarcloud.com/tomato) box unprotected, and I think that people occasionally park in front of my house to use the network. But there's no chance of peering to help avoid the last-mile bottleneck.
You have taken the analogy way to far.
What analogy? I don't think I used one. I argued against the license plate analogy.
On the internet you need packets to come back to your machine.
Depends on what you're doing. And, your needs may not be met. You seem to be arguing that it is unlikely that someone would want to put in my IP number on a packet sent to a file sharing service. That's probably right. But that doesn't make the presence of my IP number evidence that I put it there. Positive evidence that I am violating copyright shouldn't depend on assumptions about the intentions and competence of all other producers of packets. Errors, by myself and by other people, are possible, as well as deliberate use of the wrong IP number.
As long as it is easy for anyone to put any IP number on any packet and send it anywhere, which is a clear fact resulting from the simplicity of IP and the lack of authentication in IP, then the mere presence of an IP number in a packet is not positive evidence that any particular person caused that packet to be generated. The difficulty of imagining other reasons for the IP number to be there doesn't turn it into positive evidence.
In fact, I think that it is probably possible to present substantial evidence that particular file sharing is properly attributed to the host using a particular IP number. But nothing in this article, nor in other articles that I've read on similar cases, suggests that such evidence has been presented. On the contrary, they suggest that the plaintiff's claim that she has a copy of a packet with a certain IP number and that that packet was found in certain traffic with a file sharing service is the whole evidence. It isn't enough.
The writer of a false IP number doesn't need to be performing any file sharing. In fact, whatever anyone thinks or doesn't think, it is very easy to put any IP number on any packet and send it anywhere. I am expressing definite knowledge here, not idle opinion.
The plaintiffs may have evidence of actual participation in actual sharing of actual material for which they hold copyright and have not authorized sharing. But nothing in the article indicates what that evidence is.
The court appears to have accepted the likelihood that there is evidence of infringement, but they don't explain what that evidence is.