
zifo 
Posted: May 14 2007, 10:35 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

Guys, I need a documentation about the business impact of solving an NP complete problem. I mean a documentation, which could answer to the following question:
1. What would be the impact of solving the problem "P=NP?" from the business point of view? 2. Which are the top business problems in software industry, which cannot be solved because of the abovementioned problem?
I understand that the impact will be very huge, but I need it in a written form (some links, presentations, etc).
Thanks in advance 

Dream_InspectoR 
Posted: May 14 2007, 12:34 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

No links. But RSA encryption is based on assumption that discrete logarithm is NP complete problem, if you solve it world most trusted encryption will blow up
 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 14 2007, 16:33 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

Yeah, there are several domains (cryptography, chip design, electronic testing, medicine, airports, etc), where definitely it will have huge impact, but there are no articles in web about it from business point of view...
Actually breaking RSA keys is like antibusiness ) Although, it depends what purposes you have 

zifo 
Posted: May 14 2007, 16:42 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

Here is an interesting list: An Annotated List of Selected NPcomplete Problems 

zifo 
Posted: May 17 2007, 17:50 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  No links. But RSA encryption is based on assumption that discrete logarithm is NP complete problem, if you solve it world most trusted encryption will blow up 
Actually after speaking with several specialists (mathematicians) and some googling I came to a decision that the business impact of solving one particular NP problem (for example 3SAT, which is always considered as the top one problem) will not be so huge The problem is that although it is proved that any NP problem can be transitioned to an NP complete problem, still such transitions are very hard to construct. For example let's take the RSA case. In order to break RSA keys we need to transition the integer factorization problem and RSA problem to 3SAT. This is not a trivial task and even more  is not solved yet (as I understand) Conclusion: Of course solving a particular NP complete problem (and thus proving that NP=P) would be a huge progress in Computer Science, but still there will remain big set of problems, which are related to transitioning of one NP complete problem to another... So the business impact will not be as huge as it is usual to imagine... unfortunately ... and I was hoping to earn these bilions ) 

Dream_InspectoR 
Posted: May 17 2007, 17:55 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

All NP complete problems are equivalent, e.g. may be you cannot bring one problem to another directly, but you can construct chain of equivalent problems from one to another. Solving (finding polynomial algorithm) one of them will solve all of them. Then is it hard or no RSA will be brought to one of them, which means that we can find polynomial algorithm which will break RSA by brute force in reasonable time.
 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 17 2007, 18:12 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  All NP complete problems are equivalent, e.g. may be you cannot bring one problem to another directly, but you can construct chain of equivalent problems from one to another 
What I'm saying is that the construction of this chain is not trivial task and more  is not solved for severals. Particularly discrete logarithm problem is not brought (transitioned) to 3SAT yet. Thus solving 3SAT (finding polynomial algorithm for this) does not mean that you can easily break RSA keys (in practice  not theoretically). 

Dream_InspectoR 
Posted: May 17 2007, 18:30 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

Chain can be constructed from ANY NP complete problem to another. And it is not a trivial, but not a extra hard task. There is a graph of NP complete problems with some of proven transitions for example in "kombinator algorighmner" book of Tonoyan, the graph of NP complete problems is not COMPLETE but it is CONNECTED. Proving that some problem is NP complete, means that ANY NP problem can be brought to that. So if discrete logarithm is proved to be NP complete then, it is proved that every other NP problem including ALL NP COMPLETE problems can be brought to it, and it can be brought to any other NPComplete problem.
usually proving that some problem is NP complete is to assure that it is NP (e.g. it's answer correctness can be checked in plynomial time), after that take some NPComplete problem and bring it to your problem, then bringing your problem to any other NP complete problem, by thus adding your problem to connected grapgh of NPComplete problems.
please look to http://en.wikipedia.org/wiki/Complexity_cl...lasses_P_and_NP http://en.wikipedia.org/wiki/NPcomplete
QUOTE  A decision problem C is NPcomplete if it is complete for NP, meaning that: it is in NP and it is NPhard, i.e. every other problem in NP is reducible to it.

 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 17 2007, 21:21 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  And it is not a trivial, but not a extra hard task 
Dream_Inspector jan, what you are saying is quite true and we all know about this from university. But please think about all this from another point of view. Here is a simple question: Can you state that a task of finding an algorithm with polynomial complexity for any other problem (doesn't matter for what kind of problem) is always easier comparing with the task of finding a polynomial algorithm for NP complete problem? To me the answer is no. And I have the following reason for that: Suppose we have a theorem, which should be proved. Don't you think that the proof of this theorem is also an algorithm (with constant time), which should be found? So how many examples do you know when the proving of some theorem (finding algorithm for proof) took many many years... I think at least several.
Another point.
QUOTE  All of the above discussion has assumed that P means "easy" and "not in P" means "hard". While this is a common and reasonably accurate assumption in complexity theory, it is not always true in practice, for several reasons:
It ignores constant factors. A problem that takes time 10^1000*n is in P (it is linear time), but is completely impractical.

So if you find an algorithm, which tranforms discrete algorithm problem to 3SAT with complexity 10^1000*n, can you state that you can break RSA keys in practice? I believe no.
BTW, what means extra hard problem for you? For example is proving the Ferma's theorem extra hard or not? 

Dream_InspectoR 
Posted: May 17 2007, 22:17 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

We are talking about complexity of algorithms, not complexity of finding them. As you may know the problem of relationship of NP and P classes is not solved, as well as relationship between NP and NPcomplete, no one can STATE that "task of finding an algorithm with polynomial complexity for any other problem is always easier comparing with the task of finding a polynomial algorithm for NP complete problem".
No 10^1000*M is not reasonable time *now*. I assume that (10^1000) * M, because 10^(1000*M ) is not a polynomial, it is exponential But in distant future if you have some computer that will do 10^1000 operations per second will be able to solve this problem quick enough e.g. if you'll ever have computer which can do 10^1000 operations that computer will be able to break ANY RSA code, and in second case you just take a bigger prime and no one can even approach. While nonpolinomial (second case) seem not be ever solvable because complexifying the problem with one step you get may magnitudes bigger problem.
BTW if I can do an algorithm doing discretelog > 3sat in that time, that doesn't mean anything, because we do not have efficient 3sat solving algorithm
I'm not answering other questions, as they not seem to relate to NPcomplete algorithms.
 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 18 2007, 10:19 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  We are talking about complexity of algorithms, not complexity of finding them. 
You are talking about that and not me. Dream jan, I see you don't like to analyze posts, you are just reading them... it's not constructive ... so if you are interested to understand these postings (and believe me there is an interesting idea in them), review them carefully, if not  let us just finish the discussion, because when I'm spending time to post something, I'm expecting to have answers to my questions and not just smarty, obvious answers which are not related to my posting. Understand me correctly  I have just no time for that.
QUOTE  No 10^1000*M is not reasonable time *now*. I assume that (10^1000) * M, because 10^(1000*M ) is not a polynomial, it is exponential ........ 
It's obvious that I meant (10^1000) * N.
QUOTE  But in distant future if you have some computer that will do 10^1000 operations per second ... 
I'm not talking about distant future. I'm talking about current business impact.
QUOTE  BTW if I can do an algorithm doing discretelog > 3sat in that time, that doesn't mean anything, because we do not have efficient 3sat solving algorithm 
OK. Let me reformulate the question. If you find efficient 3sat solving algorithm what would you do? How would you promote this algorithm, this achievement? a. Coordinate mathematical seminar and prove that P=NP. The problem is that you don't want to share this idea with everybody.
b. Try to patent your idea as IP. The first problem is that you need much money for that. If I'm not mistaken  only patenting costs $50.000. The second problem is that you are not really sure that you have solved the right problem and there is a risk that you can spend this patenting money meaningful and even pay penalty for that.
c. Break RSA keys and the whole world will come to you. The problem is that you cannot transform the discrete logarithm to 3SAT.
d. Other option.
So what would you do? 

Dream_InspectoR 
Posted: May 18 2007, 11:15 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

And I'm continuously talking about that you CAN transform it, I'm not too deep indiscrete logarithm, but if it is NP then it can be brought to one of NP complete problems (i've written this before at least for 3 times). And you don't like to analyse MY posts and underlying mathematics as well. And believe me I'm wasting my time TOO. Please before analyze of business impact of something first analyze problem itself!
The business impact if you solve 3sat and discrete algorithms is that RSA will be theoretically weak, and all will try to migrate to something else, or increase key size dramatically.
If I can find a solution to 3 SAT I'll become one of the most known scientiists in the world, I'll spent my money not to seminar but for sending my proof to mathematical journals worldwide, and eventually I'll leave this damn country to have lectures in MIT ) Unfortunately I cannot.
 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 18 2007, 11:51 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  And I'm continuously talking about that you CAN transform it 
OK. How?
QUOTE  I'm not too deep indiscrete logarithm, but if it is NP then it can be brought to one of NP complete problems (i've written this before at least for 3 times). 
OK! I understand that 1000 times But, it doesn't mean that finding this algorithm is trivial. You can spend 10 years of finding such algorithm. It may be as extra hard as proving Ferma's theorem. Don't you agree?
QUOTE  The business impact if you solve 3sat and discrete algorithms is that RSA will be theoretically weak, and all will try to migrate to something else, or increase key size dramatically. 
Agree. But what will be your business benefit? That's why I'm saying that this will be more antibusiness )
QUOTE  before analyze of business impact of something first analyze problem itself! 
What I'm writing here is not only just my opinion. This opinion was constructed after talking with competent mathematicians.
QUOTE  ...and eventually I'll leave this damn country to have lectures in MIT ) Unfortunately I cannot. 
eeeeh, and I would do the opposite  using the business opportunities to bring to this damn country more investments, more business and more money.


Dream_InspectoR 
Posted: May 18 2007, 12:13 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

QUOTE  But, it doesn't mean that finding this algorithm is trivial. You can spend 10 years of finding such algorithm. It may be as extra hard as proving Ferma's theorem. Don't you agree? 
No and again NO. I think THERE IS a proven transition from discrete logarithm to another NP complete problem (thats the way how it proven whether it is NP complete), from EVERY NP COMPLETE PROBLEM I can show you algorithm how to get to ANY another (if a is equivalent to b. and b is equivalent to c then a is equivalent to c?".. Isn't it enough?
QUOTE  Agree. But what will be your business benefit? That's why I'm saying that this will be more antibusiness ) 
If someone loses, then someone gets that money. If you bet on a horse and loose, bookmaker wins. All of world will be spending money to security, and companies like HyLink will prosper
I'm not a really competent matematitian here it is not my specialization, all I have is 3 semester course and "excellent" mark on exam (a real one) Although I know if discrete log is NPcomplete then there is no problem of bringing it to 3SAT.
QUOTE  eeeeh, and I would do the opposite  using the business opportunities to bring to this damn country more investments, more business and more money. 
Nobody here cares about science, everyone cares about himself (me too), I've worked in organization that was giving grants to scientists. Most of them doesn't care about science too, they buy notebooks for themselves, spend money on nonscientifical ways... Only few of them do something
 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 18 2007, 12:36 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  from EVERY NP COMPLETE PROBLEM I can show you algorithm how to get to ANY another 
Ok, please show for discrete log>3SAT.
QUOTE  and companies like HyLink will prosper 
I like that
QUOTE  I'm not a really competent matematitian here it is not my specialization, all I have is 3 semester course and "excellent" mark on exam (a real one) Although I know if discrete log is NPcomplete then there is no problem of bringing it to 3SAT. 
But before trying to bring discrete log>3SAT wait a moment and think, why these lecturures, who gave you "excellent" mark, would say that this is not a trivial task
QUOTE  Nobody here cares about science 
Yesterday I met someone who cares
QUOTE  Only few of them do something 
I think investments will bring more interest for science. Money and science are strongly connected. But this is another story.
BTW, I will really appreciate if you solve this problem (appreciate not only by words ) . 

Dream_InspectoR 
Posted: May 18 2007, 13:53 


Eye of the Vision
Group: Moderator
Member No.: 614
Joined: February 10, 2004

I'm not going to show anything here. Read the books, Tonoyan "KOmbinator algorithmner" for example. (hint first find proof that log is np complete then look at already proven graph)
It is not a trivial task as well as calculating by hand PI number to 1000th decimal sign. Is it trivial or no? Evry one knows how, but no one wants to.
Appreciacion shall be expressed in my bank account, with lot's of zeroes, otherwise I have more profitable job )
 Kill'em!!! Kill'em ALL!!! 

zifo 
Posted: May 18 2007, 14:47 


Word Thrower
Group: Member
Member No.: 900
Joined: August 19, 2004

QUOTE  I'm not going to show anything here.  Ok.
Other opinions? 
