?
Solved

Clique np problem

Posted on 2007-11-27
7
Medium Priority
?
289 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
  • 5
  • 2
7 Comments
 
LVL 85

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 85

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 85

Expert Comment

by:ozo
ID: 20362609
0
 The Evil-ution of Network Security Threats

What are the hacks that forever changed the security industry? To answer that question, we created an exciting new eBook that takes you on a trip through hacking history. It explores the top hacks from the 80s to 2010s, why they mattered, and how the security industry responded.

 
LVL 85

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 85

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

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

Question has a verified solution.

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

Digital marketing agencies have encountered both the opportunities and difficulties that emerge from working with a wide-ranging organizations.
Gift cards are not a new concept - it's been around for a very long time.  Undoubtedly, over the past you have received such a card or purchased one for a friend or relative.  Are you aware that you've been feeding the machine?  If not, read on :)
Where to go on the main page to find the job listings. How to apply to a job that you are interested in from the list that is featured on our Careers page.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Suggested Courses

840 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