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
    Let me introduce a question about complexity theory I came across a few days ago.

    Consider the following two problems.

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

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

    According to the handout
    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  


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