• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Alien involvement in NP-complete algorithms

 
Ranch Foreman
Posts: 3266
19
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:

D.J. Quavern wrote:Uh, NP-hard? Wiki has a funny definition : "the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"


Let's explain this in another funny way: If aliens come down to earth and hand us a small machine that does nothing else but provide answers to the traveling salesman problem instantaneously, we can build it into our computer processors to make them able to quickly provide an answer to EVERY OTHER NP-problem, even if they seem completely unrelated to the traveling salesman problem. For instance, if you want to decrypt a secret message without knowing the key, you can write a program that states the decryption operation in terms of the traveling salesman problem, and the computer will be able to provide you the decrypted message very fast.



And I, for one, welcome our new alien overlords.
 
Saloon Keeper
Posts: 3293
146
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Whott??? Forgotten 'Mars Attacks' and 'Alien'? No thanks, I'll wait for my new 4Gqbit quantum computer, expecting it any time soon now.
 
Bartender
Posts: 20838
125
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, their only wish is to Serve Man.
 
Marshal
Posts: 24594
55
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:No thanks, I'll wait for my new 4Gqbit quantum computer, expecting it any time soon now.



Okay, but you have nobody but yourself to blame when it breaks down and sucks you into an alternative universe.
 
Mike Simmons
Ranch Foreman
Posts: 3266
19
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, we hit a little snag when the universe sort of collapsed on itself. But dad seemed cautiously optimistic.
 
Ranch Hand
Posts: 150
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think we have a representation problem with alien. The only movies we get to see are made by scarred men that believe that everything coming outside of their frontiers is a threat. I request more aliens movies before I finalize my opinion!

(and about Dijkstra... I am almost with you on that one. Just need to understand how it "stores" the possible solutions!)
 
Marshal
Posts: 64654
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Should I move this discussion to MD? Or are we going to return to its original purpose ?
 
Tim Holloway
Bartender
Posts: 20838
125
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I recommend splitting off the important question of alien interest in NP-optimal processing to its own thread. We can continue on the more mundane tracks of the travelling salesmen here.
 
Piet Souris
Saloon Keeper
Posts: 3293
146
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Objection, your Honors!

This talk about aliens is neither meaningless, nor drivel. On the contrary, much more interesting than this dull NP Salesman Dijkstra thingy... but ah well, I rest my case.    
 
D.J. Quavern
Ranch Hand
Posts: 150
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry that discussion went completely out of hand!

But now I have received Mannings bok Grokking alogorithms, it reads like a bedside story. I'll hopefully come back with more relevant questions in the future!

But yeah, since we are in MD: more alien made movies would help us to appreciate their culture and point of view on eventual earth invasion. Probably they are not even interested.
 
Tim Holloway
Bartender
Posts: 20838
125
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:I recommend splitting off the important question of alien interest in NP-optimal processing to its own thread. We can continue on the more mundane tracks of the travelling salesmen here.



In case late arrivals are puzzled by this statement, it's because it was originally made when "here" was here.

Actually, the matter of trivially solving the Traveling Salesman problem is solved by the elementary expedient of reversing the polarity of neutron flow in the affected computing device. Thereby causing quantum teleportation of the data needed to optimally arrange the weightings of the graph element by instantaneous reverse-traversal.

Quite simple really, but when you know how to do it, you can then apply it to such things as constructing a small hand-held device that scan rotate objects, slide crude iron bolts and re-arrange tumblers in sophisticated mechanical locks by the directed application of intense sonic vibrations.
 
Paul Clapham
Marshal
Posts: 24594
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:Actually, the matter of trivially solving the Traveling Salesman problem is solved by the elementary expedient of reversing the polarity of neutron flow in the affected computing device. Thereby causing quantum teleportation of the data needed to optimally arrange the weightings of the graph element by instantaneous reverse-traversal.



Ironically, when you have this technology then you don't need to have travelling salesmen any more.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!