Doubt in Algorithm?

Hi Friends,

What is NP-Complete problem?

Is it true to say that a problem which is solvable in polynomial time that are verifiable in polynomial time?

Replies

  • vishnu priya
    vishnu priya
    If a problem isComplexity Theorynp complete, it can be solved quickly by a non deterministic computer, which only needs to verify its lucky guess; but the problem is exponentially difficult to solve on a deterministic machine, which has to try every possibility in search of an answer. Consider the factorization of a large number n into two primes p and q. If you make a lucky guess, and you stumble upon p and q, it is easy to verify that p×q = n. It hardly takes any time at all, even if p and q are thousands of digits. However, if you don't know p and q, and you have to guess, you could be computing until our sun grows dim. This is the basis of rsa encryption, which is used to keep your electronic transactions secure.
    Although this example is easy to understand, it isn't a very good example, because factoring may not be an np complete problem. (We haven't proven it to be in any case.) The classic example of an np complete problem is satisfy ably, which attempts to "satisfy" a boolean expression by setting its inputs to true or false in just the right way. This is np complete because an algorithm that solves this problem solves all the other np problems, such as factoring, all in one go. You can almost see how this would work. Write p and q in binary, with boolean variables acting as the bits. Write a large boolean expression that implements p×q = n. Solve the boolean expression, and read p and q in binary, thereby factoring n. It's that easy.
  • devQuotidian
    devQuotidian
    Given the style of the question, I suggest reading something not-so-intimidating on NP-complete problems. May I therefore be so bold as to direct you to a short note I wrote some time ago, that also contains further references: #-Link-Snipped-#
    Cheers,

You are reading an archived discussion.

Related Posts

hi friends, anybody have idea about what is ipv6 and ipv4? 😒
hi friends, some day's ago i watched MI(mission impossible) a hollywood film by tom cruise in that film somebody send email to tom cruise.And after reading that email,email is vanished...
CEans, Here's a new project idea that stuck my mind today, after looking at a surveillance camera in my GYM 😲 . However, I think it can be really useful...
If you haven't yet watched the man running on water video yet, you SHOULD watch it. The company named 'Hi-Tech Sports' introduced a video on YouTube that showed an athlete...
Alright, here comes the declaration: I'm a big zero when it comes to telecommunication engineering. But since my phone has both the SIM card and the MicroSD card, I was...