Results 1 to 1 of 1

Thread: Inapproximability Problem

  1. #1 Inapproximability Problem 
    New Member
    Join Date
    Nov 2011
    I've been trying to solve this problem for over a week now and I can't seem to get anywhere:
    "Given an optimization problem A, let the corresponding optimal solution value for A be opt(A). Prove that if deciding whether opt(A) = 0 is NP-Complete then there does not exist any approximate solution for problem A regardless of its approximation factor unless P=NP."

    I figure that I need to reduce a known inapproximable problem(like max-clique or max-independent set) to the problem of deciding whether opt(A) = 0 for any optimization problem A. But the problem is so general that I can't seem to figure it out.

    Any ideas?

    Reply With Quote  


Similar Threads

  1. Problem!!!!!!!!!!
    By ~James~ in forum Physics
    Replies: 16
    Last Post: October 23rd, 2009, 05:55 AM
  2. A problem with F=ma
    By Waveman28 in forum Physics
    Replies: 31
    Last Post: March 17th, 2009, 12:45 PM
  3. Calculus II Problem - some bridge problem!!
    By jgezau in forum Mathematics
    Replies: 11
    Last Post: August 3rd, 2008, 08:41 PM
  4. Even another problem...
    By thyristor in forum Mathematics
    Replies: 9
    Last Post: April 14th, 2008, 01:13 PM
  5. Another problem...
    By thyristor in forum Mathematics
    Replies: 2
    Last Post: April 9th, 2008, 03:24 AM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts