I was in Seattle for the Nisqually quake. It's not hard to be calm after a quake, but it is terrifying when it is happening, and that includes the aftershocks.
No, I wouldn't want my torture out there on the net, at least I don't think I would. Photos won't do any more than the testimonies of the hundreds who have been brutalized, should there ever be trials.
I get the feeling that this decision wasn't made by someone high up in the Flickr food chain. Someone higher up would have looked at it and thought "we can benefit from the positive publicity of this like Facebook and Twitter did, or we can quash this and look like cowardly ass-lickers of a regime isn't even in power anymore", and then made the obvious choice.
My own only concern is for the dignity of the torture victims. If I'd been in those chambers, I don't think I would want photos of my agonies being shown the world over.
It's hard to comment without knowing what we're talking about. If those were pictures of people being tortured, then if you were one of those people would you want your suffering and humiliation shown around the world? There are ways of getting the word out without harming the torture victims again.
On the other hand if the faces were blurred, or the photos were just of implements of torture, than I don't see the need to remove them.
I always thought the Terminator displays were evidence of its human origin. The debug statements were still enabled in the code when the humans were wiped out.
Have you tried using a laptop on a plane in coach within the last ten years? When I first started flying in the early 1990's you could still use them, but now getting the keyboard back far enough to type at the same time the screen is tilted back far enough to read requires a non-human physiology.
How does the solving of problems like these really help the world?
A solution to this particular problem would launch us directly into a Star Trek-like universe of easily broken encryption, universal language translators, and inductive learning systems so easy to create that grade school children could create AI. That's week one. Week two would be the wholesale destruction of economies worldwide as all these newly smart systems show us how inefficient everything we do really is. Week three is the last great war as billions of people revolt against the rule of the machines and those who control them. You'll want to have left Earth by then.
... because if it isn't this app it will be one of the 200 other ones that iOS developers are busily writing now that they know there's money in it. People are already willing to have intimate relationship with digital entities, avatars of real persons, and people who exist completely in their own imaginations. Why wouldn't they also be willing to confess to some app that talks soothingly to them on their cellphone? The Church is correct to be afraid and I'm interested to see what happens next.
I'm sure they knew the party would end. But until it did, they made money. Now they corporation will be driven into bankruptcy, but so what? It will be a looted shell by the time the MPAA gets to it.
Solving problems like this (#P problems that is) efficiently always involves counting solutions without actually enumerating them. Results like this might give insight into how to solve other #P problems or maybe even an efficient solution to a #P-complete problem, which would give us P=NP. Heady stuff, actually.
What's important is that if 3-SAT is solvable in polynomial time, all NP problems can be solved in polynomial time. And a pretty big part of complexity theory crumbles to obvious equalities, but that would only be sad for scientists:)
It would likely be sad for all of us, unfortunately. P=NP would be a stupendous and likely world wrecking result. I hope that if anyone ever finds a constructive proof, they'll have the good sense to withhold it until the world seems ready to deal with the repercussions.
Given a graph G and distance D, are all paths that traverse all the nodes at least as long as D?
The NP question has a verifier certificate for the "yes" answer but not the "no" answer. The co-NP question has a verifier certificate for the "no" answer, but not the "yes" answer. To provide an efficient and easily verifiable answer to your optimization question a co-NP-complete solver is needed.
Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.
As far as I know, there's no proof of that. If there was, they would be in the class np-complete rather than np-hard.
It was proven when the first NP-complete problem was shown to be complete for the NP complexity class. An efficient solution to an NP-complete problem is an efficient solution to all NP problems, not just NP-complete ones. You don't have to prove that an NP problem is NP-complete for that solution to apply, you only have to show that a problem is in NP, i.e. that a "yes" answer to the decision version of the problem can be verified in polynomial time. For an encryption problem the decision version is "does the output of this encryption function with ciphertext C and key X produce output that looks like a properly decrypted message?" Once you have that verification method, it can be encoded as a 3-SAT instance that can only be satisfied if the verifier would be satisfied. Since you have an efficient 3-SAT solver (assuming Romanov has the goods), when you feed the verifier 3-SAT instance into it, you are effectively exploring the exponentially large key space in polynomial time.
That's the power of NP-completeness--- just having a polynomial time verifier is all you need to be able to produce a polynomial time solver. It doesn't matter what the computational problem is, if you can verify the solution in polynomial time, you can solve the problem in polynomial time if you have a polynomial time solver for any NP-complete problem.
Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.
It doesn't matter what the encryption algorithm is, it only matters if a valid decryption can be verified in polynomial time. If it can, then the problem is in FNP and you should be able to formulate a decision problem in NP for it. Once you have that decision problem, whatever it is, it can be converted into a 3-SAT instance. That is the terrifying power of NP-completeness.
Since the point of encryption is having a recognizable message after decryption, it's safe to assume that whatever the encryption algorithm, a valid decryption would be recognizable in polynomial time. Thus all useful encryption algorithms would be rendered useless by a tractable universal solution to 3-SAT problems. Fortunately, it is unlikely that the Romanov has such a solution.
Given how easy inductive reasoning systems would be to develop if P=NP (always assuming tractable polynomial degree), I think I would have sat down and developed an AI first and posed the question on how to proceed to IT, rather than post the solution to the world and watch the power-hungry use it to create weapons to kill or enslave us all. I don't think you'd like the world we'd be forced to live in if P=NP and everyone knew it. Google "a personal view of average-case complexity" and read Impagliazzo's paper, particular section 2.1. It would be an algorithmic wonderland, but a nightmare for everything but machines.
No, a poly time 3-SAT solution would be applicable to all NP problems.
The fact that the guy posted the code is proof to me that he doesn't really have the solution. A constructive proof that P=NP is basically a license to print money; a vast array of problems would fall to dust. No one smart enough to find the proof would be stupid enough to give it away.
The decision problem "is there a factor of n larger than m" is clearly in NP because a "yes" answer (the factor) can be checked in polynomial time (using division). However, factoring is not believed to be NP-complete, which is another way of saying that factoring is not considered to be the hardest type of NP problem. Since 3-SAT is NP-complete, a polynomial time solution to it would also be applicable to factoring. I.e. factoring decision problem can be converted into a 3-SAT instance, and then the 3-SAT solver would produce the result.
Hmmm, a big rock would do similar damage, but the nuke was presumably handy and had a built-in guidance system. Finding the right sized rock and doing the math and maneuvering necessary to deliver it on target didn't seem like something Ripley and the gang would have sat around and waited for.
So for those of us who don't live in NYC but occasionally visit, what is the "boulevard of death" ? In most cities it is named after Martin Luther King Jr., but I just want to be sure.
Some rich libertarian should buy one of these machines and a van, and start roving the streets building their own image archive. And then they should link the photos to Google Street View. Fair is fair. No assumption of privacy on the streets, right? Besides, this kind of information can be useful for ordinary citizens. For instance, I can see how many gun/knife/crack-pipe toting people are in a given area and make my own decision as to how safe that neighborhood is. And since I'm not the government, there's no Fourth Amendment concern.
This is like banning box cutters on planes because the 9/11 terrorists used them, as if terrorist can't figure out how to enocde their messages in other ways. Terrorism isn't the reasons for this, repression is.
Slashdot Mirror
I was in Seattle for the Nisqually quake. It's not hard to be calm after a quake, but it is terrifying when it is happening, and that includes the aftershocks.
No, I wouldn't want my torture out there on the net, at least I don't think I would. Photos won't do any more than the testimonies of the hundreds who have been brutalized, should there ever be trials.
I get the feeling that this decision wasn't made by someone high up in the Flickr food chain. Someone higher up would have looked at it and thought "we can benefit from the positive publicity of this like Facebook and Twitter did, or we can quash this and look like cowardly ass-lickers of a regime isn't even in power anymore", and then made the obvious choice.
My own only concern is for the dignity of the torture victims. If I'd been in those chambers, I don't think I would want photos of my agonies being shown the world over.
It's hard to comment without knowing what we're talking about. If those were pictures of people being tortured, then if you were one of those people would you want your suffering and humiliation shown around the world? There are ways of getting the word out without harming the torture victims again.
On the other hand if the faces were blurred, or the photos were just of implements of torture, than I don't see the need to remove them.
I always thought the Terminator displays were evidence of its human origin. The debug statements were still enabled in the code when the humans were wiped out.
Have you tried using a laptop on a plane in coach within the last ten years? When I first started flying in the early 1990's you could still use them, but now getting the keyboard back far enough to type at the same time the screen is tilted back far enough to read requires a non-human physiology.
How does the solving of problems like these really help the world?
A solution to this particular problem would launch us directly into a Star Trek-like universe of easily broken encryption, universal language translators, and inductive learning systems so easy to create that grade school children could create AI. That's week one. Week two would be the wholesale destruction of economies worldwide as all these newly smart systems show us how inefficient everything we do really is. Week three is the last great war as billions of people revolt against the rule of the machines and those who control them. You'll want to have left Earth by then.
... because if it isn't this app it will be one of the 200 other ones that iOS developers are busily writing now that they know there's money in it. People are already willing to have intimate relationship with digital entities, avatars of real persons, and people who exist completely in their own imaginations. Why wouldn't they also be willing to confess to some app that talks soothingly to them on their cellphone? The Church is correct to be afraid and I'm interested to see what happens next.
I'm sure they knew the party would end. But until it did, they made money. Now they corporation will be driven into bankruptcy, but so what? It will be a looted shell by the time the MPAA gets to it.
Solving problems like this (#P problems that is) efficiently always involves counting solutions without actually enumerating them. Results like this might give insight into how to solve other #P problems or maybe even an efficient solution to a #P-complete problem, which would give us P=NP. Heady stuff, actually.
What's important is that if 3-SAT is solvable in polynomial time, all NP problems can be solved in polynomial time. And a pretty big part of complexity theory crumbles to obvious equalities, but that would only be sad for scientists :)
It would likely be sad for all of us, unfortunately. P=NP would be a stupendous and likely world wrecking result. I hope that if anyone ever finds a constructive proof, they'll have the good sense to withhold it until the world seems ready to deal with the repercussions.
So how would you verify that an optimal solution to the travelling salesman problem is in fact optimal in polynomial time?
That question can't be posed as an NP decision problem, so it is out of domain.
The NP traveling salesman decision problem:
Given a graph G and distance D, is there a path that traverses all the nodes that is shorter than D?
The co-NP traveling salesman decision problem:
Given a graph G and distance D, are all paths that traverse all the nodes at least as long as D?
The NP question has a verifier certificate for the "yes" answer but not the "no" answer. The co-NP question has a verifier certificate for the "no" answer, but not the "yes" answer. To provide an efficient and easily verifiable answer to your optimization question a co-NP-complete solver is needed.
Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.
As far as I know, there's no proof of that. If there was, they would be in the class np-complete rather than np-hard.
It was proven when the first NP-complete problem was shown to be complete for the NP complexity class. An efficient solution to an NP-complete problem is an efficient solution to all NP problems, not just NP-complete ones. You don't have to prove that an NP problem is NP-complete for that solution to apply, you only have to show that a problem is in NP, i.e. that a "yes" answer to the decision version of the problem can be verified in polynomial time. For an encryption problem the decision version is "does the output of this encryption function with ciphertext C and key X produce output that looks like a properly decrypted message?" Once you have that verification method, it can be encoded as a 3-SAT instance that can only be satisfied if the verifier would be satisfied. Since you have an efficient 3-SAT solver (assuming Romanov has the goods), when you feed the verifier 3-SAT instance into it, you are effectively exploring the exponentially large key space in polynomial time.
That's the power of NP-completeness--- just having a polynomial time verifier is all you need to be able to produce a polynomial time solver. It doesn't matter what the computational problem is, if you can verify the solution in polynomial time, you can solve the problem in polynomial time if you have a polynomial time solver for any NP-complete problem.
Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.
It doesn't matter what the encryption algorithm is, it only matters if a valid decryption can be verified in polynomial time. If it can, then the problem is in FNP and you should be able to formulate a decision problem in NP for it. Once you have that decision problem, whatever it is, it can be converted into a 3-SAT instance. That is the terrifying power of NP-completeness.
Since the point of encryption is having a recognizable message after decryption, it's safe to assume that whatever the encryption algorithm, a valid decryption would be recognizable in polynomial time. Thus all useful encryption algorithms would be rendered useless by a tractable universal solution to 3-SAT problems. Fortunately, it is unlikely that the Romanov has such a solution.
Given how easy inductive reasoning systems would be to develop if P=NP (always assuming tractable polynomial degree), I think I would have sat down and developed an AI first and posed the question on how to proceed to IT, rather than post the solution to the world and watch the power-hungry use it to create weapons to kill or enslave us all. I don't think you'd like the world we'd be forced to live in if P=NP and everyone knew it. Google "a personal view of average-case complexity" and read Impagliazzo's paper, particular section 2.1. It would be an algorithmic wonderland, but a nightmare for everything but machines.
No, a poly time 3-SAT solution would be applicable to all NP problems.
The fact that the guy posted the code is proof to me that he doesn't really have the solution. A constructive proof that P=NP is basically a license to print money; a vast array of problems would fall to dust. No one smart enough to find the proof would be stupid enough to give it away.
The decision problem "is there a factor of n larger than m" is clearly in NP because a "yes" answer (the factor) can be checked in polynomial time (using division). However, factoring is not believed to be NP-complete, which is another way of saying that factoring is not considered to be the hardest type of NP problem. Since 3-SAT is NP-complete, a polynomial time solution to it would also be applicable to factoring. I.e. factoring decision problem can be converted into a 3-SAT instance, and then the 3-SAT solver would produce the result.
DIA still seems to employ them. http://www.washingtonpost.com/wp-dyn/content/article/2010/11/26/AR2010112605017.html
>> How will anyone, future employer or other, ever actually find out you read something?
Polygraph, fMRI, or whatever they are using as a truth machine these days.
Hmmm, a big rock would do similar damage, but the nuke was presumably handy and had a built-in guidance system. Finding the right sized rock and doing the math and maneuvering necessary to deliver it on target didn't seem like something Ripley and the gang would have sat around and waited for.
So for those of us who don't live in NYC but occasionally visit, what is the "boulevard of death" ? In most cities it is named after Martin Luther King Jr., but I just want to be sure.
an explanation of how atolls rise with sea level.
http://wattsupwiththat.com/2010/01/27/floating-islands/
Some rich libertarian should buy one of these machines and a van, and start roving the streets building their own image archive. And then they should link the photos to Google Street View. Fair is fair. No assumption of privacy on the streets, right? Besides, this kind of information can be useful for ordinary citizens. For instance, I can see how many gun/knife/crack-pipe toting people are in a given area and make my own decision as to how safe that neighborhood is. And since I'm not the government, there's no Fourth Amendment concern.
This is like banning box cutters on planes because the 9/11 terrorists used them, as if terrorist can't figure out how to enocde their messages in other ways. Terrorism isn't the reasons for this, repression is.