Notices
Results 1 to 1 of 1

Thread: relation between QLIQUE and 3-QLIQUE

  1. #1 relation between QLIQUE and 3-QLIQUE 
    New Member
    Join Date
    Oct 2009
    Posts
    1
    Let me introduce a question about complexity theory I came across a few days ago.

    Consider the following two problems.

    <QLIQUE>
    INSTANCE: Graph G, positive integer K
    QUESTION: Does G conatin a qlique of size K or more?

    <3-QLIQUE>
    INSTANCE: Graph G
    QUESTION: Does G conatin a 3-qlique?

    According to the handout http://www.cs.bris.ac.uk/Teaching/Re...0126probs2.pdf
    QLIQUE is NP complete and 3-QLIQUE is in P(furthermore, k-QLIQUE is in P for any other fixed value of k).
    My question is, isn't it a contradiction(under the condition that NP and P are not identical)? That is, if k-QLIQUE(k is a cocrete number) can be solved in P, QLIQUE seems to be solved also in P using the algorithm for k-QLIQUE.

    Would anyone explain the above? Please help me!


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •