[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Clique np problem

Posted on 2007-11-27
7
Medium Priority
?
287 Views
Last Modified: 2008-02-01
Hi Fellow EE Experts

Looking for a quick proof here on the following. one showing it can be done and an example showing it cant.

Looking at the following NP Problem.
http://en.wikipedia.org/wiki/Clique_problem

How would I show that for one instance an example can be solved in a finite amount of time and the other an exponential?

Any Help would be grealty appreciated.

Many Thanks
Steve
0
Comment
Question by:Stephen Manderson
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 2
7 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 20362535
You can show it is in  NP-Complete  by reducing it to Independent Set
http://en.wikipedia.org/wiki/Independent_set_problem
0
 
LVL 84

Expert Comment

by:ozo
ID: 20362564
Any given instance of the problem can be solved in P time by an algorithm that knows the answer to that given instance.
But for any given algorithm there exist instances of the problem that cannot be solved in polynomial time, unless every other NP-Complete problem can also be solved in Polynomial time,
0
 
LVL 84

Expert Comment

by:ozo
ID: 20362609
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 84

Expert Comment

by:ozo
ID: 20362613
0
 
LVL 19

Author Comment

by:Stephen Manderson
ID: 20362746
Thanks for the links Ozo tryiong to understand the way to prove for one instance the graph could be P time.

You say reducing it to an independent set, but isnt an independant set the opposite of a clique ?

Hmm im pretty lost when it comes to this, just to help me along the right lines would this be correct in trying to prove a clique problem in p time?

6
  \
   4-----5----
   I       I     1
   3-----2----

The clique is formed from vertices 1,2 and 5 which could be solved in p time

However

If there was an exponential amount of vertices it would be NP to calculate if a clique is present?
0
 
LVL 84

Accepted Solution

by:
ozo earned 2000 total points
ID: 20363585
The time to solve is generally a function of the number of vertices.
If there was an algorithm that could solve any instance of the problem in a time that was a polynomial function of the number of vertices, then there would be an algorithm to solve any NP-C problem in polynomial time.
Since no one knows how to do that, no one knows how to write a deterministic algorithm that can solve any instance of clique in polynomial time.
This does not prevent there from being an algorithm that can quickly solve a particular instance of clique.

But it doesn't really make sense to say that a particular problem can be solved in exponential time,
Exponential time and polynomial time describes how the time to solve varies as function of the size of the problem.
0
 
LVL 19

Author Comment

by:Stephen Manderson
ID: 20364069
Sorry i meant that as the number of vertices increases so does the time taken to solve the problem.
0

Featured Post

Q2 2017 - Latest Malware & Internet Attacks

WatchGuard’s Threat Lab is a group of dedicated threat researchers committed to helping you stay ahead of the bad guys by providing in-depth analysis of the top security threats to your network.  Check out our latest Quarterly Internet Security Report!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

EE introduced a new rating method known as Level, which displays in your avatar as LVL. The new Level is a numeric ranking that is based on your Points. This article discusses the rationale behind the new method and provides the mathematical formula…
In this article, I’ll show how research, determination, and use of modern technology helped me solve a DNA mystery.
The Bounty Board allows you to request an article or video on any technical topic, or fulfill a bounty request to earn points. Watch this video to learn how to use the Bounty Board to get the content you want, earn points, and browse submitted bount…
Saved searches can save you time by quickly referencing commonly searched terms on any topic. Whether you are looking for questions you can answer or hoping to learn about a specific issue, a saved search can help you get the most out of your time o…
Suggested Courses

656 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question