Jump to content

FPTAS and NP-Completeness

heliodromus
in Computer Science

Featured Replies

Hey fellas,

 

I have a Problem in understanding on how to proof the following:

 

Let Q = {max,f,L} be a NPO-Problem, where f only supports integers.

 

LQ* ={(x0,1k)|there exists x such that L(x0,x) and f(x0,x) >=k}

The instance of x0 is binary coded while the numerical parameter k is unary coded.

 

Show that if LQ* is NP-Complete, then there is no full polynomial approximation scheme for Q.

 

Normally I have so sort of idea, but this time I am really stumped

 

I would be grateful if you could show me on how to solve such issues.

 

Sincerely yours

heliodromus

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.