Welcome Guest ( Log In | Register )

Help | Search | Members | Calendar

 
Business Overview of NP complete problems
« Next Oldest | Next Newest » Track this topic | Email this topic | Print this topic
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
 
     Top
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 smile.gif

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
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 anti-business smile.gif) Although, it depends what purposes you have wink.gif
 
     Top
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 NP-complete Problems
 
     Top
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 sad.gif 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) sad.gif
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 smile.gif)
 
     Top
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!!!
 
        Top
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).
 
     Top
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 NP-Complete 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 NP-Complete 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 NP-Complete problems.

please look to http://en.wikipedia.org/wiki/Complexity_cl...lasses_P_and_NP http://en.wikipedia.org/wiki/NP-complete

QUOTE

A decision problem C is NP-complete if it is complete for NP, meaning that:
it is in NP and
it is NP-hard, i.e. every other problem in NP is reducible to it.


--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
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?
 
     Top
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 NP-complete, 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 smile.gif 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 non-polinomial (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 smile.gif

I'm not answering other questions, as they not seem to relate to NP-complete algorithms.

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
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?
 
     Top
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 smile.gif) Unfortunately I cannot.

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
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 smile.gif
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 anti-business smile.gif)
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.

 
     Top
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 anti-business )

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 smile.gif

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) smile.gif Although I know if discrete log is NP-complete 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 non-scientifical ways... Only few of them do something smile.gif



--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
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 wink.gif
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 NP-complete 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 wink.gif
QUOTE
Nobody here cares about science

Yesterday I met someone who cares wink.gif
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 wink.gif) .
 
     Top
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 smile.gif)

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
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?
 
     Top
16 replies since May 14 2007, 10:35 Track this topic | Email this topic | Print this topic

<< Back to Mathematics

 




Arminco Global Telecommunications