Solved

Clique np problem

Posted on 2007-11-27
7
284 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 500 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

Industry Leaders: 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!

Question has a verified solution.

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

Finding a job can be stressful - searches, resume tweaks, and networking events can be super boring. Luckily we're here to help you land your dream job!
An introduction to the wonderful sport of Scam Baiting.  Learn how to help fight scammers by beating them at their own game. This great pass time helps the world, while providing an endless source of entertainment. Enjoy!
Notifications on Experts Exchange help you keep track of your activity and updates in one place. Watch this video to learn how to use them on the site to quickly access the content that matters to you.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa‚Ķ

726 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