Solved

Clique np problem

Posted on 2007-11-27
7
279 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 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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

CSS is a visual language used to classify objects and define rules about how they should be displayed. CSS skills aren’t restricted to developers anymore, there is a big benefit to having a basic understanding of the language, regardless of your occ…
Whether you believe the “gig economy,” as it has been dubbed, is the next big economic paradigm shift (https://www.theguardian.com/commentisfree/2015/jul/26/will-we-get-by-gig-economy) or an overstated trend (http://www.wsj.com/articles/proof-of-a-g…
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…
Articles on a wide range of technology and professional topics are available on Experts Exchange. These resources are written by members, for members, and can be written about any topic you feel passionate about. Learn how to best write an article t…

744 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now