Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Complexity theory {Hamiltonian, DHC, IND}

  1. Mar 5, 2010 #1

    I need help with a couple of questions.
    (The answers haven't come up properly and are too cryptic and I'm having some difficulty).
    I'm trying really hard to learn this, so could you explain it as fully and clearly as possible - that would be of great help.
    (I find there are some intuitive leaps, or pieces of insight in complexity theory that I don't always see).

    1. The problem statement, all variables and given/known data

    a) How do you show that the Hamiltonian Circuit problem is NP-Complete

    (do you use gadgets? tsp? I think there is a 'clean' way to do it)

    b) If Directed Hamiltonian Circuit is HC but for directed graphs, then how do you show that DHC is NP-Complete
    (some how reduce DHC to HC).

    2) An independent set I is a subset of the nodes of a graph G where: no 2 nodes in I are adjacent in G. For natural number k, the problem k-IND asks if there is an independent set of size k. The problem: How do you show k-IND is in Logspace.

    2. Relevant equations

    Notion of '<' reduction; intuition?

    3. The attempt at a solution

    I've stated by thoughts in brackets.

    Like I've said, I am have difficulty in grip into this topic. If I have some solid foundation that I understand (ie: these questions) then I think I will improve my chances for the looming exam. :(

    Please help. Thank you very much
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted