Notices
Results 1 to 5 of 5

Thread: Theory of Computation

  1. #1 Theory of Computation 
    New Member
    Join Date
    Dec 2009
    Posts
    3
    ...


    Reply With Quote  
     

  2.  
     

  3. #2  
    Veracity Vigilante inow's Avatar
    Join Date
    Oct 2009
    Location
    Austin, TX
    Posts
    3,500
    Hi Grace,

    You will probably have higher chances at success if you just go ahead and post your questions here to this thread. While I am not personally well versed in such theories, by presenting your questions up front you are more likely to get someone to read and respond to them.

    Good luck. :-)


    Reply With Quote  
     

  4. #3 Here are a couple of the questions: 
    New Member
    Join Date
    Dec 2009
    Posts
    3
    ...
    Reply With Quote  
     

  5. #4 Is Maximum Independent Set on DAG an NP-Complete problem ??? 
    New Member
    Join Date
    Dec 2009
    Posts
    2
    I am wondering if Maximum Independent Set on DAG is NP-Complete problem. I know that if the graph is undirected then it is an NP-Complete, but what about DAGs.. Please help by a proof..
    Reply With Quote  
     

  6. #5 NP-Complete 
    New Member
    Join Date
    Dec 2009
    Posts
    3
    There is a published article that claims it is but I don't know for sure.
    Reply With Quote  
     

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
  •